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;
93 SCIP_Bool initialized;
109 int** resourcedemands,
148 for(
j = 0;
j < njobs; ++
j )
177 for(
j = 0;
j < njobs; ++
j )
210 for( v = 0; v <
nvars; ++v )
231 SCIP_Bool* infeasible
257 SCIP_Bool* infeasible
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 )
307 SCIP_Bool* infeasible
325 SCIPdebugMessage(
"Terminate after start: resource %d, lst %d, duration %d, demand %d\n",
326 r,
lst, duration, demands[
r]);
387 SCIP_Bool* infeasible
402 for( s = 0; s < nsuccessors && !(*infeasible); ++s )
404 succ = successors[s];
431 for( s = 0; s < nsuccessors; ++s )
433 succ = successors[s];
449 SCIP_Bool* infeasible
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];
510 for(
j = 0;
j < nresources; ++
j )
530 SCIP_Bool* 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 )
639 for(
j = 0;
j < njobs; ++
j )
666 SCIP_Bool infeasible;
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
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
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE