Scippy

SCIP

Solving Constraint Integer Programs

heur_listscheduling.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_listscheduling.c
17  * @brief scheduling specific primal heuristic which is based on bidirectional serial generation scheme.
18  * @author Jens Schulz
19  *
20  * @page LISTHEUR List scheduling heuristic
21  *
22  * The heuristic performs a serial SGS (schedule generation scheme), see Kolisch and Hartmann 2006.
23  * Therefore, the jobs are considered in a topological order (e.g., sorted by their earliest start) and are scheduled
24  * according to that order as early as possible respecting the precedence and resource constraints.
25  *
26  * The serial generation scheme is extended to bidirectional SGS; see Li and Willis 1992. The first obtained
27  * schedule is the so-called forward schedule. Then, all jobs are sorted in non-increasing order of their completion
28  * times in the forward schedule. According to that ordering, a backward schedule is created by scheduling all jobs as
29  * late as possible again with respect to precedence and resource constraints. It gets clear from the way the algorithm
30  * works, that if a feasible forward schedule has been found, a feasible backward schedule can be obtained, since no job
31  * needs to be scheduled earlier as in the forward schedule. Recreating a forward schedule by sorting the jobs
32  * according to their start times in the backward schedule leads to a makespan not larger than the one in the first
33  * forward schedule.
34  *
35  * @section REFERENCES References
36  *
37  * -# Rainer Kolisch and Sönke Hartmann. Experimental investigation of heuristics for resource-constrained
38  * project scheduling: An update. <em>European Journal of Operational Research</em>, 174(1):23&ndash;37, 2006.
39  * -# K.Y. Li and R.J. Willis. An iterative scheduling technique for resource-constrained project
40  * scheduling. <em>European Journal of Operational Research</em>, 56(3):370&ndash;379, 1992.
41  */
42 
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 
45 #include <assert.h>
46 #include <string.h>
47 
48 #include "heur_listscheduling.h"
49 #include "scip/pub_misc.h"
50 
51 /**@name Properties of the heuristic
52  *
53  * @{
54  */
55 
56 #define HEUR_NAME "listscheduling"
57 #define HEUR_DESC "scheduling specific primal heuristic which is based on bidirectional serial generation scheme"
58 #define HEUR_DISPCHAR 'x'
59 #define HEUR_PRIORITY 10000
60 #define HEUR_FREQ 0
61 #define HEUR_FREQOFS 0
62 #define HEUR_MAXDEPTH -1
63 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_BEFOREPRESOL
64 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
65 
66 /**@} */
67 
68 /*
69  * Data structures
70  */
71 
72 
73 /** primal heuristic data */
74 struct SCIP_HeurData
75 {
76  SCIP_DIGRAPH* precedencegraph; /**< precedence graph of the jobs */
77  int** resourcedemands; /**< resource demands matrix (job i needs resourcedemands[i][j] units of resource j) */
78  SCIP_VAR** vars; /**< array of start time variables */
79  int* durations; /**< array of duration for each job */
80  int* capacities; /**< array to store the capacities of all cum constraints */
81  int njobs; /**< number of jobs */
82  int nresources; /**< number of resources */
83  SCIP_Bool initialized; /**< stores if initialization has already occurred */
84 };
85 
86 /**@name Local methods
87  *
88  * @{
89  */
90 
91 /** initializes heuristic data structures */
92 static
94  SCIP* scip, /**< SCIP data structure */
95  SCIP_HEURDATA* heurdata, /**< heuristic data structure */
96  SCIP_DIGRAPH* precedencegraph, /**< precedence graph */
97  SCIP_VAR** vars, /**< start time variables */
98  int* durations, /**< duration of the jobs independent of the resources */
99  int** resourcedemands, /**< resource demand matrix */
100  int* capacities, /**< capacities of the resources */
101  int njobs, /**< number if jobs */
102  int nresources /**< number of resources */
103  )
104 {
105  int j;
106 
107  assert(scip != NULL);
108  assert(heurdata != NULL);
109  assert(!heurdata->initialized);
110 
111  heurdata->nresources = nresources;
112  heurdata->njobs = njobs;
113 
114  if( njobs == 0 )
115  {
116  heurdata->resourcedemands = NULL;
117  heurdata->capacities = NULL;
118  heurdata->precedencegraph = NULL;
119  }
120  else
121  {
122  /* copy precedence graph */
123  SCIP_CALL( SCIPcopyDigraph(scip, &heurdata->precedencegraph, precedencegraph) );
124 
125  /* topological sort the precedence graph */
126  SCIP_CALL( SCIPdigraphComputeUndirectedComponents(heurdata->precedencegraph, -1, NULL, NULL) );
127  assert(SCIPdigraphGetNComponents(heurdata->precedencegraph) == 1);
128 
129  /* use the topological sorted for the variables */
130  SCIP_CALL( SCIPdigraphTopoSortComponents(heurdata->precedencegraph) );
131  SCIPdebug( SCIPdigraphPrintComponents(heurdata->precedencegraph, SCIPgetMessagehdlr(scip), NULL) );
132 
133  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->capacities, capacities, nresources) );
134  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->vars, vars, njobs) );
135  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->durations, durations, njobs) );
136 
137  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->resourcedemands, njobs) );
138  for( j = 0; j < njobs; ++j )
139  {
140  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->resourcedemands[j], resourcedemands[j], nresources) );/*lint !e866*/
141  }
142 
143  heurdata->initialized = TRUE;
144  }
145 
146  return SCIP_OKAY;
147 }
148 
149 /* frees heuristic data structures */
150 static
152  SCIP* scip, /**< SCIP data structure */
153  SCIP_HEURDATA* heurdata /**< heuristic data structure */
154  )
155 {
156  int njobs;
157 
158  assert(scip != NULL);
159  assert(heurdata != NULL);
160 
161  njobs = heurdata->njobs;
162 
163  if( njobs > 0 )
164  {
165  int j;
166 
167  for( j = 0; j < njobs; ++j )
168  {
169  SCIPfreeBlockMemoryArray(scip, &heurdata->resourcedemands[j], heurdata->nresources);
170  }
171 
172  SCIPfreeBlockMemoryArray(scip, &heurdata->resourcedemands, njobs);
173  SCIPfreeBlockMemoryArray(scip, &heurdata->capacities, heurdata->nresources);
174  SCIPfreeBlockMemoryArray(scip, &heurdata->vars, njobs);
175  SCIPfreeBlockMemoryArray(scip, &heurdata->durations, njobs);
176  SCIPdigraphFree(&heurdata->precedencegraph);
177  }
178 
179  heurdata->initialized = FALSE;
180  heurdata->njobs = 0;
181 
182  return SCIP_OKAY;
183 }
184 
185 /** constructs a solution with the given start values for the integer start variables */
186 static
188  SCIP* scip, /**< SCIP data structure */
189  SCIP_SOL* sol, /**< solution to be constructed */
190  SCIP_VAR** vars, /**< integer start variables */
191  int* starttimes, /**< start times for the integer start variables */
192  int nvars /**< number of integer start variables */
193  )
194 {
195  SCIP_VAR* var;
196  SCIP_Real val;
197  int v;
198 
199  /* set start time variables */
200  for( v = 0; v < nvars; ++v )
201  {
202  /* get some values */
203  var = vars[v];
204  val = (SCIP_Real)starttimes[v];
205 
206  SCIP_CALL( SCIPsetSolVal(scip, sol, var, val) );
207  }
208 
209  return SCIP_OKAY;
210 }
211 
212 /** insert given job into the profiles */
213 static
215  SCIP* scip, /**< SCIP data structure */
216  SCIP_PROFILE** profiles, /**< array of resource profiles */
217  int nprofiles, /**< number of profiles */
218  int starttime, /**< start time of the job */
219  int duration, /**< duration of the job */
220  int* demands, /**< profile depending demands */
221  SCIP_Bool* infeasible /**< pointer to store if the insertion is infeasible */
222  )
223 {
224  int pos;
225  int p;
226 
227  /* found a feasible start time, insert the job into all profiles */
228  for( p = 0; p < nprofiles && !(*infeasible); ++p )
229  {
230  /* add job to resource profile */
231  SCIP_CALL( SCIPprofileInsertCore(profiles[p], starttime, starttime + duration, demands[p], &pos, infeasible) );
232  }
233 
234  return SCIP_OKAY;
235 }
236 
237 
238 /** retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles */
239 static
241  SCIP_PROFILE** profiles, /**< array of resource profiles */
242  int nprofiles, /**< number of profiles */
243  int est, /**< earliest start time */
244  int lst, /**< latest start time */
245  int duration, /**< duration of the job */
246  int* demands, /**< profile depending demands */
247  SCIP_Bool* infeasible /**< pointer to store if it is infeasible to do */
248  )
249 {
250  SCIP_Bool changed;
251  int start;
252  int r;
253 
254  assert(!(*infeasible));
255 
256  do
257  {
258  changed = FALSE;
259 
260  for( r = 0; r < nprofiles; ++r )
261  {
262  assert(est >= 0);
263 
264  /* get next possible time to start from the current earliest starting time */
265  start = SCIPprofileGetEarliestFeasibleStart(profiles[r], est, lst, duration, demands[r], infeasible);
266 
267  /* stop if job cannot be inserted */
268  if( *infeasible )
269  {
270  SCIPdebugMessage("Terminate after start: resource %d, est %d, duration %d, demand %d\n",
271  r, est, duration, demands[r]);
272  return -1;
273  }
274 
275  /* check if the earliest start time changes */
276  if( r > 0 && start > est )
277  changed = TRUE;
278 
279  est = start;
280  }
281  }
282  while( changed );
283 
284  SCIPdebugMessage("earliest feasible start time: %d\n", est);
285 
286  return est;
287 }
288 
289 /** retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles */
290 static
292  SCIP_PROFILE** profiles, /**< array of resource profiles */
293  int nprofiles, /**< number of profiles */
294  int lst, /**< latest start time */
295  int duration, /**< duration of the job */
296  int* demands, /**< profile depending demands */
297  SCIP_Bool* infeasible /**< pointer to store if it is infeasible to do */
298  )
299 {
300  SCIP_Bool changed;
301  int start;
302  int r;
303 
304  do
305  {
306  changed = FALSE;
307 
308  for( r = 0; r < nprofiles; ++r )
309  {
310  /* get next latest possible time to start from */
311  start = SCIPprofileGetLatestFeasibleStart(profiles[r], 0, lst, duration, demands[r], infeasible);
312 
313  if( *infeasible )
314  {
315  SCIPdebugMessage("Terminate after start: resource %d, lst %d, duration %d, demand %d\n",
316  r, lst, duration, demands[r]);
317  return -1;
318  }
319 
320  assert(start <= lst);
321 
322  /* check if the earliest start time changes */
323  if( r > 0 && start < lst )
324  changed = TRUE;
325 
326  lst = start;
327  }
328  }
329  while( changed );
330 
331  return lst;
332 }
333 
334 /** collect earliest and latest start times for all variables in the order given in the variables array */
335 static
337  SCIP* scip, /**< SCIP data structure */
338  SCIP_VAR** vars, /**< array of start time variables */
339  int* ests, /**< array to store the earliest start times */
340  int* lsts, /**< array to store the latest start times */
341  int nvars /**< number of variables */
342  )
343 {
344  SCIP_VAR* var;
345  int j;
346 
347  assert(ests != NULL);
348  assert(lsts != NULL);
349 
350  /* initialize earliest and latest start times */
351  for( j = 0; j < nvars; ++j )
352  {
353  var = vars[j];
354  assert(var != NULL);
355 
357  {
358  ests[j] = (int)(SCIPgetSolVal(scip, NULL, var) + 0.5);
359  }
360  else
361  {
362  ests[j] = (int)(SCIPvarGetLbLocal(var) + 0.5);
363  }
364  lsts[j] = (int)(SCIPvarGetUbGlobal(var) + 0.5);
365  assert(ests[j] <= lsts[j]);
366  }
367 }
368 
369 /** propagate the earliest start time of the given job via the precedence graph to all successors jobs*/
370 static
372  SCIP_DIGRAPH* precedencegraph, /**< precedence graph */
373  int* ests, /**< array of earliest start time for each job */
374  int* lsts, /**< array of latest start times for each job */
375  int pred, /**< index of the job which earliest start time showed propagated */
376  int duration, /**< duration of the job */
377  SCIP_Bool* infeasible /**< pointer to store if the propagate detected an infeasibility */
378  )
379 {
380  int* successors;
381  int nsuccessors;
382  int succ;
383  int ect;
384  int s;
385 
386  nsuccessors = SCIPdigraphGetNSuccessors(precedencegraph, pred);
387  successors = SCIPdigraphGetSuccessors(precedencegraph, pred);
388 
389  /* compute earliest completion time */
390  ect = ests[pred] + duration;
391 
392  for( s = 0; s < nsuccessors && !(*infeasible); ++s )
393  {
394  succ = successors[s];
395 
396  /* check if the new earliest start time is smaller than the latest start time of the job */
397  if( ect > lsts[succ] )
398  *infeasible = TRUE;
399  else
400  ests[succ] = MAX(ests[succ], ect);
401  }
402 }
403 
404 /** propagate the latest start time of the given job via the precedence graph w.r.t. all successors jobs */
405 static
407  SCIP_DIGRAPH* precedencegraph, /**< precedence graph */
408  int* lsts, /**< array of latest start times for each job */
409  int pred, /**< index of the job which earliest start time showed propagated */
410  int duration /**< duration of the job */
411  )
412 {
413  int* successors;
414  int nsuccessors;
415  int succ;
416  int s;
417 
418  nsuccessors = SCIPdigraphGetNSuccessors(precedencegraph, pred);
419  successors = SCIPdigraphGetSuccessors(precedencegraph, pred);
420 
421  for( s = 0; s < nsuccessors; ++s )
422  {
423  succ = successors[s];
424  lsts[pred] = MIN(lsts[pred], lsts[succ] - duration);
425  }
426 }
427 
428 /** perform forward scheduling, that is, assigned jobs (in the given ordering) to their earliest start time, propagate
429  * w.r.t. the precedence graph and resource profiles
430  */
431 static
433  SCIP* scip, /**< SCIP data structure */
434  SCIP_HEURDATA* heurdata, /**< heuristic data */
435  int* starttimes, /**< array to store the start times for each job */
436  int* lsts, /**< array of latest start times for each job */
437  int* perm, /**< permutation defining the order of the jobs */
438  int* makespan, /**< pointer to store the makespan of the forward scheduling solution */
439  SCIP_Bool* infeasible /**< pointer to store if an infeasibility was detected */
440  )
441 {
442  SCIP_PROFILE** profiles;
443  int nresources;
444  int njobs;
445  int j;
446 
447  nresources = heurdata->nresources;
448  njobs = heurdata->njobs;
449  *makespan = 0;
450 
451  assert(*infeasible == FALSE);
452 
453  SCIPdebugMessage("perform forward scheduling\n");
454 
455  /* create resource profiles for checking the resource requirements */
456  SCIP_CALL( SCIPallocBufferArray(scip, &profiles, nresources) );
457  for( j = 0; j < nresources; ++j )
458  {
459  assert(heurdata->capacities[j] > 0);
460  SCIP_CALL( SCIPprofileCreate(&profiles[j], heurdata->capacities[j]) );
461  }
462 
463  for( j = 0; j < njobs && !(*infeasible); ++j )
464  {
465  int* demands;
466  int duration;
467  int idx;
468 
469  idx = perm[j];
470  assert(idx >= 0 && idx < njobs);
471 
472  duration = heurdata->durations[idx];
473  demands = heurdata->resourcedemands[idx];
474  assert(demands != NULL);
475 
476  /* skip jobs which have a duration of zero */
477  if( duration > 0 )
478  {
479  /* find earliest start time w.r.t to all resource profiles */
480  starttimes[idx] = profilesFindEarliestFeasibleStart(profiles, nresources, starttimes[idx], lsts[idx], duration, demands, infeasible);
481 
482  if( *infeasible )
483  break;
484 
485  /* adjust makespan */
486  (*makespan) = MAX(*makespan, starttimes[idx] + duration);
487 
488  /* insert the job into the profiles */
489  SCIP_CALL( profilesInsertJob(scip, profiles, nresources, starttimes[idx], duration, demands, infeasible) );
490  if( *infeasible )
491  break;
492 
493  /* propagate the new earliest start time of the job */
494  propagateEst(heurdata->precedencegraph, starttimes, lsts, idx, duration, infeasible);
495  }
496  SCIPdebugMessage("job %d -> est %d\n", idx, starttimes[idx]);
497  }
498 
499  /* free resource profiles */
500  for( j = 0; j < nresources; ++j )
501  {
502  SCIPprofileFree(&profiles[j]);
503  }
504  SCIPfreeBufferArray(scip, &profiles);
505 
506  SCIPdebugMessage("forward scheduling: makespan %d, feasible %d\n", *makespan, !(*infeasible));
507 
508  return SCIP_OKAY;
509 }
510 
511 /** perform backward scheduling, that is, schedule jobs (in the ordering of their latest completion time) to their and
512  * propagate w.r.t. the precedence graph and resource profiles
513  */
514 static
516  SCIP* scip, /**< SCIP data structure */
517  SCIP_HEURDATA* heurdata, /**< heuristic data */
518  int* starttimes, /**< array of latest start times for each job */
519  int* perm, /**< permutation defining the order of jobs */
520  SCIP_Bool* infeasible /**< pointer to store if an infeasibility was detected */
521  )
522 {
523  SCIP_PROFILE** profiles;
524  int* durations;
525  int* demands;
526  int duration;
527  int nresources;
528  int njobs;
529  int idx;
530  int j;
531 
532  nresources = heurdata->nresources;
533  njobs = heurdata->njobs;
534  durations = heurdata->durations;
535 
536  SCIPdebugMessage("perform forward scheduling\n");
537 
538  /* create resource profiles for checking the resource requirements */
539  SCIP_CALL( SCIPallocBufferArray(scip, &profiles, nresources) );
540  for( j = 0; j < nresources; ++j )
541  {
542  assert(heurdata->capacities[j] > 0);
543  SCIP_CALL( SCIPprofileCreate(&profiles[j], heurdata->capacities[j]) );
544  }
545 
546  for( j = 0; j < njobs; ++j )
547  {
548  idx = perm[j];
549  assert(idx >= 0 && idx < njobs);
550 
551  duration = durations[idx];
552  demands = heurdata->resourcedemands[idx];
553  assert(demands != NULL);
554 
555  /* propagate the new latest start time */
556  propagateLst(heurdata->precedencegraph, starttimes, idx, duration);
557 
558  /* check against the resource profiles if the duration is greater than zero */
559  if( duration > 0 )
560  {
561  /* find earliest start time w.r.t to all resource profiles */
562  starttimes[idx] = profilesFindLatestFeasibleStart(profiles, nresources, starttimes[idx], duration, demands, infeasible);
563  if( *infeasible )
564  break;
565 
566  /* insert the job into the profiles */
567  SCIP_CALL( profilesInsertJob(scip, profiles, nresources, starttimes[idx], duration, demands, infeasible) );
568  if( *infeasible )
569  break;
570  }
571 
572  SCIPdebugMessage("job %d -> est %d\n", idx, starttimes[idx]);
573 
574  }
575 
576  /* free resource profiles */
577  for( j = 0; j < nresources; ++j )
578  {
579  SCIPprofileFree(&profiles[j]);
580  }
581  SCIPfreeBufferArray(scip, &profiles);
582 
583  return SCIP_OKAY;
584 }
585 
586 /** creates a permutation of the job w.r.t. earliest start time */
587 static
589  SCIP* scip, /**< SCIP data structure */
590  int* starttimes, /**< array of start times for each job */
591  int* ests, /**< earliest start times */
592  int* perm, /**< array to store the permutation w.r.t. earliest start time */
593  int njobs /**< number of jobs */
594  )
595 {
596  int* sortingkeys;
597  int j;
598 
599  SCIP_CALL( SCIPallocBufferArray(scip, &sortingkeys, njobs) );
600 
601  for( j = 0; j < njobs; ++j )
602  {
603  perm[j] = j;
604  sortingkeys[j] = starttimes[j];
605  starttimes[j] = ests[j];
606  }
607  SCIPsortIntInt(sortingkeys, perm, njobs);
608 
609  SCIPfreeBufferArray(scip, &sortingkeys);
610 
611  return SCIP_OKAY;
612 }
613 
614 /** creates a permutation of the job w.r.t. latest completion time */
615 static
617  SCIP* scip, /**< SCIP data structure */
618  int* starttimes, /**< array of start times for each job */
619  int* durations, /**< array of durations */
620  int* perm, /**< array to store the permutation w.r.t. latest completion time */
621  int njobs /**< number of jobs */
622  )
623 {
624  int* sortingkeys;
625  int j;
626 
627  SCIP_CALL( SCIPallocBufferArray(scip, &sortingkeys, njobs) );
628 
629  for( j = 0; j < njobs; ++j )
630  {
631  perm[j] = j;
632  sortingkeys[j] = starttimes[j] + durations[j];
633  }
634  SCIPsortDownIntInt(sortingkeys, perm, njobs);
635 
636  SCIPfreeBufferArray(scip, &sortingkeys);
637 
638  return SCIP_OKAY;
639 }
640 
641 
642 /** execution method of heuristic */
643 static
645  SCIP* scip, /**< SCIP data structure */
646  SCIP_HEUR* heur, /**< Heuristic data structure */
647  SCIP_RESULT* result /**< pointer to store whether solution is found or not */
648  )
649 {
650  SCIP_HEURDATA* heurdata;
651  SCIP_VAR** vars;
652  int* starttimes;
653  int* ests;
654  int* lsts;
655  int* perm;
656  SCIP_Bool infeasible;
657  SCIP_Bool stored;
658  int makespan;
659  int njobs;
660 
661  /* get heuristic data */
662  heurdata = SCIPheurGetData(heur);
663  assert(heurdata != NULL);
664  assert(heurdata->initialized);
665 
666  vars = heurdata->vars;
667  njobs = heurdata->njobs;
668  infeasible = FALSE;
669 
670  /* create initialized permutation */
672  {
673  SCIP_Real* solvals;
674  int v;
675 
676  SCIP_CALL( SCIPallocBufferArray(scip, &perm, njobs) );
677  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, njobs) );
678 
679  /* in case the LP relaxation was solved to optimality we use the LP solution as initialized permutation */
680  for( v = 0; v < njobs; ++v )
681  {
682  solvals[v] = SCIPgetSolVal(scip, NULL, vars[v]);
683  perm[v] = v;
684  }
685  SCIPsortRealInt(solvals, perm, njobs);
686 
687  SCIPfreeBufferArray(scip, &solvals);
688  }
689  else
690  {
691  int* component;
692 
693  /* in case the LP was not solved we use the topologically sorted variables w.r.t. precedences graph */
694  SCIPdigraphGetComponent(heurdata->precedencegraph, 0, &component, NULL);
695  SCIP_CALL( SCIPduplicateBufferArray(scip, &perm, component, njobs) );
696  }
697 
698  /* collect earliest and latest start times for all variables in the order given in the variables array */
699  SCIP_CALL( SCIPallocBufferArray(scip, &ests, njobs) );
700  SCIP_CALL( SCIPallocBufferArray(scip, &lsts, njobs) );
701  collectEstLst(scip, vars, ests, lsts, njobs);
702 
703  /* initialize the start times with the earliest start times */
704  SCIP_CALL( SCIPduplicateBufferArray(scip, &starttimes, ests, njobs) );
705 
706  /* LIST schedule:
707  *
708  * STEP 1: perform forward scheduling, that is, shift all jobs to the left as much as possible in the given ordering
709  */
710  SCIP_CALL( performForwardScheduling(scip, heurdata, starttimes, lsts, perm, &makespan, &infeasible) );
711 
712  if( !infeasible )
713  {
714  SCIP_SOL* sol;
715 
716  /* get permutation w.r.t. latest completion time given by start times */
717  SCIP_CALL( getLctPermuataion(scip, starttimes, heurdata->durations, perm, njobs) );
718 
719  /* backward scheduling w.r.t. latest completion time */
720  SCIP_CALL( performBackwardScheduling(scip, heurdata, starttimes, perm, &infeasible) );
721 
722  if( !infeasible )
723  {
724  /* get permutation w.r.t. earliest start time given by the starttimes and reset the start time to the earliest start time */
725  SCIP_CALL( getEstPermutation(scip, starttimes, ests, perm, njobs) );
726 
727  SCIP_CALL( performForwardScheduling(scip, heurdata, starttimes, lsts, perm, &makespan, &infeasible) );
728 
729  SCIP_CALL( SCIPcreateOrigSol(scip, &sol, heur) );
730 
731  SCIP_CALL( constructSolution(scip, sol, vars, starttimes, njobs) );
732 
733  SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &stored) );
734 
735  if( stored )
736  *result = SCIP_FOUNDSOL;
737  }
738  }
739 
740  SCIPfreeBufferArray(scip, &starttimes);
741  SCIPfreeBufferArray(scip, &lsts);
742  SCIPfreeBufferArray(scip, &ests);
743 
744  SCIPfreeBufferArray(scip, &perm);
745 
746  return SCIP_OKAY;
747 }
748 
749 /**@} */
750 
751 /**@name Callback methods
752  *
753  * @{
754  */
755 
756 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
757 static
758 SCIP_DECL_HEURFREE(heurFreeListScheduling)
759 { /*lint --e{715}*/
760  SCIP_HEURDATA* heurdata;
761 
762  assert(scip != NULL);
763  assert(heur != NULL);
764 
765  /* get heuristic data */
766  heurdata = SCIPheurGetData(heur);
767  assert(heurdata != NULL);
768 
769  SCIP_CALL( heurdataFree(scip, heurdata) );
770 
771  /* free heuristic data */
772  SCIPfreeBlockMemory(scip, &heurdata);
773  SCIPheurSetData(heur, NULL);
774 
775  return SCIP_OKAY;
776 }
777 
778 #ifdef SCIP_DISABLED_CODE
779 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
780 #define heurCopyListScheduling NULL
781 
782 /** initialization method of primal heuristic (called after problem was transformed) */
783 #define heurInitListScheduling NULL
784 
785 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
786 #define heurExitListScheduling NULL
787 
788 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
789 #define heurInitsolListScheduling NULL
790 
791 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
792 #define heurExitsolListScheduling NULL
793 #endif
794 
795 /** execution method of primal heuristic */
796 static
797 SCIP_DECL_HEUREXEC(heurExecListScheduling)
798 { /*lint --e{715}*/
799  SCIP_HEURDATA* heurdata; /* Primal heuristic data */
800 
801  assert(heur != NULL);
802  assert(scip != NULL);
803  assert(result != NULL);
804 
805  (*result) = SCIP_DIDNOTRUN;
806 
807  heurdata = SCIPheurGetData(heur);
808  assert(heurdata != NULL);
809 
810  if( !heurdata->initialized )
811  return SCIP_OKAY;
812 
813  SCIPdebugMessage("execute heuristic <"HEUR_NAME">\n");
814 
815  if( heurdata->njobs == 0 )
816  return SCIP_OKAY;
817 
818  (*result) = SCIP_DIDNOTFIND;
819 
820  SCIP_CALL( executeHeuristic(scip, heur, result) );
821 
822  return SCIP_OKAY;
823 }
824 
825 /**@} */
826 
827 /**@name Interface methods
828  *
829  * @{
830  */
831 
832 /** creates the list scheduling primal heuristic and includes it in SCIP */
834  SCIP* scip /**< SCIP data structure */
835  )
836 {
837  SCIP_HEURDATA* heurdata;
838  SCIP_HEUR* heur = NULL;
839 
840  /* create list scheduling primal heuristic data */
841  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
842 
843  heurdata->resourcedemands = NULL;
844  heurdata->vars = NULL;
845  heurdata->njobs = 0;
846  heurdata->initialized = FALSE;
847 
848  /* include primal heuristic */
851  heurExecListScheduling, heurdata) );
852  assert(heur != NULL);
853 
854  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeListScheduling) );
855 
856  return SCIP_OKAY;
857 }
858 
859 /** initialize heuristic */
861  SCIP* scip, /**< SCIP data structure */
862  SCIP_DIGRAPH* precedencegraph, /**< precedence graph */
863  SCIP_VAR** vars, /**< start time variables */
864  int* durations, /**< duration of the jobs independent of the resources */
865  int** resourcedemands, /**< resource demand matrix */
866  int* capacities, /**< resource capacities */
867  int njobs, /**< number if jobs */
868  int nresources /**< number of resources */
869  )
870 {
871  SCIP_HEURDATA* heurdata;
872  SCIP_HEUR* heur;
873 
874  heur = SCIPfindHeur(scip, HEUR_NAME);
875  assert(heur != NULL);
876 
877  heurdata = SCIPheurGetData(heur);
878  assert(heurdata != NULL);
879 
880  if( heurdata->initialized )
881  {
882  /* free old heuristic data structure */
883  SCIP_CALL( heurdataFree(scip, heurdata) );
884  }
885 
886  /* initialize the heuristic data structure */
887  SCIP_CALL( heurdataInit(scip, heurdata, precedencegraph, vars, durations, resourcedemands, capacities, njobs, nresources) );
888 
889  return SCIP_OKAY;
890 }
891 
892 /**@} */
int SCIPprofileGetEarliestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7031
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
static SCIP_RETCODE executeHeuristic(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result)
#define HEUR_PRIORITY
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:557
static SCIP_DECL_HEURFREE(heurFreeListScheduling)
#define HEUR_NAME
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8172
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define HEUR_FREQOFS
#define HEUR_DISPCHAR
SCIP_EXPORT void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
static SCIP_RETCODE performBackwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *perm, SCIP_Bool *infeasible)
static SCIP_RETCODE heurdataInit(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources)
#define HEUR_MAXDEPTH
#define HEUR_USESSUBSCIP
static SCIP_RETCODE heurdataFree(SCIP *scip, SCIP_HEURDATA *heurdata)
#define FALSE
Definition: def.h:73
static SCIP_RETCODE getEstPermutation(SCIP *scip, int *starttimes, int *ests, int *perm, int njobs)
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7695
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7459
static SCIP_RETCODE constructSolution(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, int *starttimes, int nvars)
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
#define SCIPdebugMessage
Definition: pub_message.h:87
static SCIP_RETCODE performForwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *lsts, int *perm, int *makespan, SCIP_Bool *infeasible)
void SCIPdigraphPrintComponents(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8511
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
static void propagateEst(SCIP_DIGRAPH *precedencegraph, int *ests, int *lsts, int pred, int duration, SCIP_Bool *infeasible)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
static SCIP_DECL_HEUREXEC(heurExecListScheduling)
SCIP_RETCODE SCIPincludeHeurListScheduling(SCIP *scip)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:7977
#define HEUR_FREQ
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
static int profilesFindEarliestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int est, int lst, int duration, int *demands, SCIP_Bool *infeasible)
#define NULL
Definition: lpi_spx1.cpp:155
static int profilesFindLatestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int lst, int duration, int *demands, SCIP_Bool *infeasible)
#define SCIP_CALL(x)
Definition: def.h:364
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8185
SCIP_RETCODE SCIPcopyDigraph(SCIP *scip, SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
public data structures and miscellaneous methods
SCIP_EXPORT void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17672
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7710
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:91
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
SCIP_Real * r
Definition: circlepacking.c:50
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7180
#define HEUR_DESC
#define HEUR_TIMING
void SCIPprofileFree(SCIP_PROFILE **profile)
Definition: misc.c:6660
SCIP_RETCODE SCIPinitializeHeurListScheduling(SCIP *scip, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources)
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8106
static SCIP_RETCODE getLctPermuataion(SCIP *scip, int *starttimes, int *durations, int *perm, int njobs)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
static void collectEstLst(SCIP *scip, SCIP_VAR **vars, int *ests, int *lsts, int nvars)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:6911
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6646
scheduling specific primal heuristic which is based on bidirectional serial generation scheme...
static SCIP_RETCODE profilesInsertJob(SCIP *scip, SCIP_PROFILE **profiles, int nprofiles, int starttime, int duration, int *demands, SCIP_Bool *infeasible)
static void propagateLst(SCIP_DIGRAPH *precedencegraph, int *lsts, int pred, int duration)