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-2024 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 */
84struct 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 */
102static
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 */
160static
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 */
196static
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 */
223static
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 */
249static
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 */
300static
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 */
345static
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*/
380static
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 */
415static
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 */
441static
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 */
524static
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 */
597static
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 */
625static
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 */
653static
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);
753
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) */
767static
768SCIP_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 */
806static
807SCIP_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/**@} */
SCIP_Real * r
Definition: circlepacking.c:59
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_CALL(x)
Definition: def.h:374
void SCIPdigraphPrintComponents(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8624
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:8089
SCIP_RETCODE SCIPcopyDigraph(SCIP *scip, SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8298
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8219
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7568
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:88
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:258
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:421
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:3050
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7289
void SCIPprofileFree(SCIP_PROFILE **profile)
Definition: misc.c:6769
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6755
int SCIPprofileGetEarliestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7140
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:7020
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPinitializeHeurListScheduling(SCIP *scip, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources)
#define HEUR_TIMING
#define HEUR_FREQOFS
static void propagateLst(SCIP_DIGRAPH *precedencegraph, int *lsts, int pred, int duration)
#define HEUR_DESC
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)
static SCIP_DECL_HEUREXEC(heurExecListScheduling)
static SCIP_RETCODE performForwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *lsts, int *perm, int *makespan, SCIP_Bool *infeasible)
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
static SCIP_RETCODE profilesInsertJob(SCIP *scip, SCIP_PROFILE **profiles, int nprofiles, int starttime, int duration, int *demands, SCIP_Bool *infeasible)
static SCIP_RETCODE executeHeuristic(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result)
static SCIP_RETCODE constructSolution(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, int *starttimes, int nvars)
static void propagateEst(SCIP_DIGRAPH *precedencegraph, int *ests, int *lsts, int pred, int duration, SCIP_Bool *infeasible)
#define HEUR_NAME
static SCIP_RETCODE getEstPermutation(SCIP *scip, int *starttimes, int *ests, int *perm, int njobs)
static SCIP_DECL_HEURFREE(heurFreeListScheduling)
static void collectEstLst(SCIP *scip, SCIP_VAR **vars, int *ests, int *lsts, int nvars)
static SCIP_RETCODE getLctPermuataion(SCIP *scip, int *starttimes, int *durations, int *perm, int njobs)
static int profilesFindEarliestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int est, int lst, int duration, int *demands, SCIP_Bool *infeasible)
#define HEUR_FREQ
#define HEUR_USESSUBSCIP
static SCIP_RETCODE performBackwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *perm, SCIP_Bool *infeasible)
static int profilesFindLatestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int lst, int duration, int *demands, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPincludeHeurListScheduling(SCIP *scip)
static SCIP_RETCODE heurdataFree(SCIP *scip, SCIP_HEURDATA *heurdata)
scheduling specific primal heuristic which is based on bidirectional serial generation scheme.
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugMessage
Definition: pub_message.h:96
public data structures and miscellaneous methods
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53