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