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