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
72#define HEUR_MAXDEPTH -1
73#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_BEFOREPRESOL
74#define HEUR_USESSUBSCIP FALSE
87 int** resourcedemands;
109 int** resourcedemands,
148 for( j = 0; j < njobs; ++j )
177 for( j = 0; j < njobs; ++j )
210 for( v = 0; v <
nvars; ++v )
238 for( p = 0; p < nprofiles && !(*infeasible); ++p )
270 for(
r = 0;
r < nprofiles; ++
r )
280 SCIPdebugMessage(
"Terminate after start: resource %d, est %d, duration %d, demand %d\n",
281 r, est, duration, demands[
r]);
286 if(
r > 0 && start > est )
318 for(
r = 0;
r < nprofiles; ++
r )
325 SCIPdebugMessage(
"Terminate after start: resource %d, lst %d, duration %d, demand %d\n",
326 r, lst, duration, demands[
r]);
333 if(
r > 0 && start < lst )
361 for( j = 0; j <
nvars; ++j )
375 assert(ests[j] <= lsts[j]);
400 ect = ests[pred] + duration;
402 for( s = 0; s < nsuccessors && !(*infeasible); ++s )
404 succ = successors[s];
407 if( ect > lsts[succ] )
410 ests[succ] =
MAX(ests[succ], ect);
431 for( s = 0; s < nsuccessors; ++s )
433 succ = successors[s];
434 lsts[pred] =
MIN(lsts[pred], lsts[succ] - duration);
467 for( j = 0; j < nresources; ++j )
473 for( j = 0; j < njobs && !(*infeasible); ++j )
480 assert(idx >= 0 && idx < njobs);
482 duration =
heurdata->durations[idx];
483 demands =
heurdata->resourcedemands[idx];
496 (*makespan) =
MAX(*makespan, starttimes[idx] + duration);
510 for( j = 0; j < nresources; ++j )
516 SCIPdebugMessage(
"forward scheduling: makespan %d, feasible %d\n", *makespan, !(*infeasible));
550 for( j = 0; j < nresources; ++j )
556 for( j = 0; j < njobs; ++j )
559 assert(idx >= 0 && idx < njobs);
561 duration = durations[idx];
562 demands =
heurdata->resourcedemands[idx];
587 for( j = 0; j < nresources; ++j )
611 for( j = 0; j < njobs; ++j )
614 sortingkeys[j] = starttimes[j];
615 starttimes[j] = ests[j];
639 for( j = 0; j < njobs; ++j )
642 sortingkeys[j] = starttimes[j] + durations[j];
690 for( v = 0; v < njobs; ++v )
788#ifdef SCIP_DISABLED_CODE
790#define heurCopyListScheduling NULL
793#define heurInitListScheduling NULL
796#define heurExitListScheduling NULL
799#define heurInitsolListScheduling NULL
802#define heurExitsolListScheduling NULL
861 heurExecListScheduling,
heurdata) );
875 int** resourcedemands,
void SCIPdigraphPrintComponents(SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents(SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
SCIP_RETCODE SCIPcopyDigraph(SCIP *scip, SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
void SCIPdigraphGetComponent(SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
SCIP_RETCODE SCIPdigraphTopoSortComponents(SCIP_DIGRAPH *digraph)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
int SCIPdigraphGetNComponents(SCIP_DIGRAPH *digraph)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
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)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
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)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
int SCIPprofileGetLatestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
void SCIPprofileFree(SCIP_PROFILE **profile)
SCIP_RETCODE SCIPprofileCreate(SCIP_PROFILE **profile, int capacity)
int SCIPprofileGetEarliestFeasibleStart(SCIP_PROFILE *profile, int est, int lst, int duration, int demand, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPprofileInsertCore(SCIP_PROFILE *profile, int left, int right, int demand, int *pos, SCIP_Bool *infeasible)
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)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_RETCODE SCIPinitializeHeurListScheduling(SCIP *scip, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources)
static void propagateLst(SCIP_DIGRAPH *precedencegraph, int *lsts, int pred, int duration)
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_RETCODE performForwardScheduling(SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *lsts, int *perm, int *makespan, SCIP_Bool *infeasible)
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)
static SCIP_RETCODE getEstPermutation(SCIP *scip, int *starttimes, int *ests, int *perm, int njobs)
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)
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.
public data structures and miscellaneous methods
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
struct SCIP_Digraph SCIP_DIGRAPH
struct SCIP_Profile SCIP_PROFILE
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE