heur_listscheduling.c
Go to the documentation of this file.
17 * @brief scheduling specific primal heuristic which is based on bidirectional serial generation scheme.
22 * The heuristic performs a serial SGS (schedule generation scheme), see Kolisch and Hartmann 2006.
23 * Therefore, the jobs are considered in a topological order (e.g., sorted by their earliest start) and are scheduled
24 * according to that order as early as possible respecting the precedence and resource constraints.
26 * The serial generation scheme is extended to bidirectional SGS; see Li and Willis 1992. The first obtained
27 * schedule is the so-called forward schedule. Then, all jobs are sorted in non-increasing order of their completion
28 * times in the forward schedule. According to that ordering, a backward schedule is created by scheduling all jobs as
29 * late as possible again with respect to precedence and resource constraints. It gets clear from the way the algorithm
30 * works, that if a feasible forward schedule has been found, a feasible backward schedule can be obtained, since no job
31 * needs to be scheduled earlier as in the forward schedule. Recreating a forward schedule by sorting the jobs
32 * according to their start times in the backward schedule leads to a makespan not larger than the one in the first
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–37, 2006.
43 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
57 #define HEUR_DESC "scheduling specific primal heuristic which is based on bidirectional serial generation scheme"
77 int** resourcedemands; /**< resource demands matrix (job i needs resourcedemands[i][j] units of resource j) */
131 SCIPdebug( SCIPdigraphPrintComponents(heurdata->precedencegraph, SCIPgetMessagehdlr(scip), NULL) );
133 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->capacities, capacities, nresources) );
140 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->resourcedemands[j], resourcedemands[j], nresources) );/*lint !e866*/
231 SCIP_CALL( SCIPprofileInsertCore(profiles[p], starttime, starttime + duration, demands[p], &pos, infeasible) );
238 /** retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles */
265 start = SCIPprofileGetEarliestFeasibleStart(profiles[r], est, lst, duration, demands[r], infeasible);
289 /** retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles */
311 start = SCIPprofileGetLatestFeasibleStart(profiles[r], 0, lst, duration, demands[r], infeasible);
334 /** collect earliest and latest start times for all variables in the order given in the variables array */
356 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
369 /** propagate the earliest start time of the given job via the precedence graph to all successors jobs*/
404 /** propagate the latest start time of the given job via the precedence graph w.r.t. all successors jobs */
428 /** perform forward scheduling, that is, assigned jobs (in the given ordering) to their earliest start time, propagate
480 starttimes[idx] = profilesFindEarliestFeasibleStart(profiles, nresources, starttimes[idx], lsts[idx], duration, demands, infeasible);
489 SCIP_CALL( profilesInsertJob(scip, profiles, nresources, starttimes[idx], duration, demands, infeasible) );
511 /** perform backward scheduling, that is, schedule jobs (in the ordering of their latest completion time) to their and
562 starttimes[idx] = profilesFindLatestFeasibleStart(profiles, nresources, starttimes[idx], duration, demands, infeasible);
567 SCIP_CALL( profilesInsertJob(scip, profiles, nresources, starttimes[idx], duration, demands, infeasible) );
671 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
679 /* in case the LP relaxation was solved to optimality we use the LP solution as initialized permutation */
693 /* in case the LP was not solved we use the topologically sorted variables w.r.t. precedences graph */
698 /* collect earliest and latest start times for all variables in the order given in the variables array */
708 * STEP 1: perform forward scheduling, that is, shift all jobs to the left as much as possible in the given ordering
710 SCIP_CALL( performForwardScheduling(scip, heurdata, starttimes, lsts, perm, &makespan, &infeasible) );
724 /* get permutation w.r.t. earliest start time given by the starttimes and reset the start time to the earliest start time */
727 SCIP_CALL( performForwardScheduling(scip, heurdata, starttimes, lsts, perm, &makespan, &infeasible) );
788 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
791 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
849 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY,
887 SCIP_CALL( heurdataInit(scip, heurdata, precedencegraph, vars, durations, resourcedemands, capacities, njobs, nresources) );
int SCIPprofileGetEarliestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7031
static SCIP_RETCODE executeHeuristic(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result)
Definition: heur_listscheduling.c:644
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:557
static SCIP_DECL_HEURFREE(heurFreeListScheduling)
Definition: heur_listscheduling.c:758
Definition: type_result.h:33
Definition: type_result.h:47
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8172
Definition: struct_scip.h:59
SCIP_EXPORT void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
static SCIP_RETCODE performBackwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *perm, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:515
Definition: struct_var.h:198
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)
Definition: heur_listscheduling.c:93
static SCIP_RETCODE heurdataFree(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_listscheduling.c:151
static SCIP_RETCODE getEstPermutation(SCIP *scip, int *starttimes, int *ests, int *perm, int njobs)
Definition: heur_listscheduling.c:588
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7695
static SCIP_RETCODE constructSolution(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, int *starttimes, int nvars)
Definition: heur_listscheduling.c:187
static SCIP_RETCODE performForwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *lsts, int *perm, int *makespan, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:432
void SCIPdigraphPrintComponents(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
Definition: misc.c:8511
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
static void propagateEst(SCIP_DIGRAPH *precedencegraph, int *ests, int *lsts, int pred, int duration, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:371
Definition: struct_sol.h:64
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
static SCIP_DECL_HEUREXEC(heurExecListScheduling)
Definition: heur_listscheduling.c:797
SCIP_RETCODE SCIPincludeHeurListScheduling(SCIP *scip)
Definition: heur_listscheduling.c:833
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:92
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
Definition: misc.c:7977
Definition: type_result.h:35
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
static int profilesFindEarliestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int est, int lst, int duration, int *demands, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:240
static int profilesFindLatestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int lst, int duration, int *demands, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:291
Definition: type_retcode.h:33
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
Definition: misc.c:8185
Definition: struct_heur.h:88
SCIP_RETCODE SCIPcopyDigraph(SCIP *scip, SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
Definition: scip_datastructures.c:629
Definition: type_lp.h:34
public data structures and miscellaneous methods
SCIP_EXPORT void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_EXPORT void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7710
Definition: struct_misc.h:200
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7180
SCIP_RETCODE SCIPinitializeHeurListScheduling(SCIP *scip, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources)
Definition: heur_listscheduling.c:860
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8106
static SCIP_RETCODE getLctPermuataion(SCIP *scip, int *starttimes, int *durations, int *perm, int njobs)
Definition: heur_listscheduling.c:616
Definition: type_set.h:44
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
static void collectEstLst(SCIP *scip, SCIP_VAR **vars, int *ests, int *lsts, int nvars)
Definition: heur_listscheduling.c:336
Definition: objbenders.h:33
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
Definition: struct_misc.h:210
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
Definition: misc.c:6911
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
Definition: misc.c:6646
scheduling specific primal heuristic which is based on bidirectional serial generation scheme...
static SCIP_RETCODE profilesInsertJob(SCIP *scip, SCIP_PROFILE **profiles, int nprofiles, int starttime, int duration, int *demands, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:214
static void propagateLst(SCIP_DIGRAPH *precedencegraph, int *lsts, int pred, int duration)
Definition: heur_listscheduling.c:406