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