heur_listscheduling.c
Go to the documentation of this file.
27 * @brief scheduling specific primal heuristic which is based on bidirectional serial generation scheme.
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.
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
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–37, 2006.
53/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
67#define HEUR_DESC "scheduling specific primal heuristic which is based on bidirectional serial generation scheme"
87 int** resourcedemands; /**< resource demands matrix (job i needs resourcedemands[i][j] units of resource j) */
141 SCIPdebug( SCIPdigraphPrintComponents(heurdata->precedencegraph, SCIPgetMessagehdlr(scip), NULL) );
143 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->capacities, capacities, nresources) );
150 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &heurdata->resourcedemands[j], resourcedemands[j], nresources) );/*lint !e866*/
241 SCIP_CALL( SCIPprofileInsertCore(profiles[p], starttime, starttime + duration, demands[p], &pos, infeasible) );
248/** retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles */
275 start = SCIPprofileGetEarliestFeasibleStart(profiles[r], est, lst, duration, demands[r], infeasible);
299/** retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles */
321 start = SCIPprofileGetLatestFeasibleStart(profiles[r], 0, lst, duration, demands[r], infeasible);
344/** collect earliest and latest start times for all variables in the order given in the variables array */
366 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
379/** propagate the earliest start time of the given job via the precedence graph to all successors jobs*/
414/** propagate the latest start time of the given job via the precedence graph w.r.t. all successors jobs */
438/** perform forward scheduling, that is, assigned jobs (in the given ordering) to their earliest start time, propagate
490 starttimes[idx] = profilesFindEarliestFeasibleStart(profiles, nresources, starttimes[idx], lsts[idx], duration, demands, infeasible);
499 SCIP_CALL( profilesInsertJob(scip, profiles, nresources, starttimes[idx], duration, demands, infeasible) );
521/** perform backward scheduling, that is, schedule jobs (in the ordering of their latest completion time) to their and
572 starttimes[idx] = profilesFindLatestFeasibleStart(profiles, nresources, starttimes[idx], duration, demands, infeasible);
577 SCIP_CALL( profilesInsertJob(scip, profiles, nresources, starttimes[idx], duration, demands, infeasible) );
681 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL )
689 /* in case the LP relaxation was solved to optimality we use the LP solution as initialized permutation */
703 /* in case the LP was not solved we use the topologically sorted variables w.r.t. precedences graph */
708 /* collect earliest and latest start times for all variables in the order given in the variables array */
718 * STEP 1: perform forward scheduling, that is, shift all jobs to the left as much as possible in the given ordering
720 SCIP_CALL( performForwardScheduling(scip, heurdata, starttimes, lsts, perm, &makespan, &infeasible) );
734 /* get permutation w.r.t. earliest start time given by the starttimes and reset the start time to the earliest start time */
737 SCIP_CALL( performForwardScheduling(scip, heurdata, starttimes, lsts, perm, &makespan, &infeasible) );
798/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
801/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
859 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY,
897 SCIP_CALL( heurdataInit(scip, heurdata, precedencegraph, vars, durations, resourcedemands, capacities, njobs, nresources) );
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)
Definition: scip_datastructures.c:638
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
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8285
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
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#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
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
Definition: misc.c:7289
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)
Definition: heur_listscheduling.c:870
static void propagateLst(SCIP_DIGRAPH *precedencegraph, int *lsts, int pred, int duration)
Definition: heur_listscheduling.c:416
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:103
static SCIP_DECL_HEUREXEC(heurExecListScheduling)
Definition: heur_listscheduling.c:807
static SCIP_RETCODE performForwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *lsts, int *perm, int *makespan, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:442
static SCIP_RETCODE profilesInsertJob(SCIP *scip, SCIP_PROFILE **profiles, int nprofiles, int starttime, int duration, int *demands, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:224
static SCIP_RETCODE executeHeuristic(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result)
Definition: heur_listscheduling.c:654
static SCIP_RETCODE constructSolution(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, int *starttimes, int nvars)
Definition: heur_listscheduling.c:197
static void propagateEst(SCIP_DIGRAPH *precedencegraph, int *ests, int *lsts, int pred, int duration, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:381
static SCIP_RETCODE getEstPermutation(SCIP *scip, int *starttimes, int *ests, int *perm, int njobs)
Definition: heur_listscheduling.c:598
static SCIP_DECL_HEURFREE(heurFreeListScheduling)
Definition: heur_listscheduling.c:768
static void collectEstLst(SCIP *scip, SCIP_VAR **vars, int *ests, int *lsts, int nvars)
Definition: heur_listscheduling.c:346
static SCIP_RETCODE getLctPermuataion(SCIP *scip, int *starttimes, int *durations, int *perm, int njobs)
Definition: heur_listscheduling.c:626
static int profilesFindEarliestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int est, int lst, int duration, int *demands, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:250
static SCIP_RETCODE performBackwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *perm, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:525
static int profilesFindLatestFeasibleStart(SCIP_PROFILE **profiles, int nprofiles, int lst, int duration, int *demands, SCIP_Bool *infeasible)
Definition: heur_listscheduling.c:301
SCIP_RETCODE SCIPincludeHeurListScheduling(SCIP *scip)
Definition: heur_listscheduling.c:843
static SCIP_RETCODE heurdataFree(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_listscheduling.c:161
scheduling specific primal heuristic which is based on bidirectional serial generation scheme.
Definition: objbenders.h:44
public data structures and miscellaneous methods
Definition: struct_misc.h:220
Definition: struct_heur.h:98
Definition: struct_misc.h:210
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70