scheduling specific primal heuristic which is based on bidirectional serial generation scheme.
Definition in file heur_listscheduling.c.
Go to the source code of this file.
Macros | |
Properties of the heuristic | |
#define | HEUR_NAME "listscheduling" |
#define | HEUR_DESC "scheduling specific primal heuristic which is based on bidirectional serial generation scheme" |
#define | HEUR_DISPCHAR 'x' |
#define | HEUR_PRIORITY 10000 |
#define | HEUR_FREQ 0 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_BEFOREPRESOL |
#define | HEUR_USESSUBSCIP FALSE |
Functions | |
Local methods | |
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 | heurdataFree (SCIP *scip, SCIP_HEURDATA *heurdata) |
static SCIP_RETCODE | constructSolution (SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, int *starttimes, int nvars) |
static SCIP_RETCODE | profilesInsertJob (SCIP *scip, SCIP_PROFILE **profiles, int nprofiles, int starttime, int duration, int *demands, SCIP_Bool *infeasible) |
static int | profilesFindEarliestFeasibleStart (SCIP_PROFILE **profiles, int nprofiles, int est, int lst, int duration, int *demands, SCIP_Bool *infeasible) |
static int | profilesFindLatestFeasibleStart (SCIP_PROFILE **profiles, int nprofiles, int lst, int duration, int *demands, SCIP_Bool *infeasible) |
static void | collectEstLst (SCIP *scip, SCIP_VAR **vars, int *ests, int *lsts, int nvars) |
static void | propagateEst (SCIP_DIGRAPH *precedencegraph, int *ests, int *lsts, int pred, int duration, SCIP_Bool *infeasible) |
static void | propagateLst (SCIP_DIGRAPH *precedencegraph, int *lsts, int pred, int duration) |
static SCIP_RETCODE | performForwardScheduling (SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *lsts, int *perm, int *makespan, SCIP_Bool *infeasible) |
static SCIP_RETCODE | performBackwardScheduling (SCIP *scip, SCIP_HEURDATA *heurdata, int *starttimes, int *perm, SCIP_Bool *infeasible) |
static SCIP_RETCODE | getEstPermutation (SCIP *scip, int *starttimes, int *ests, int *perm, int njobs) |
static SCIP_RETCODE | getLctPermuataion (SCIP *scip, int *starttimes, int *durations, int *perm, int njobs) |
static SCIP_RETCODE | executeHeuristic (SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result) |
Callback methods | |
static | SCIP_DECL_HEURFREE (heurFreeListScheduling) |
static | SCIP_DECL_HEUREXEC (heurExecListScheduling) |
Interface methods | |
SCIP_RETCODE | SCIPincludeHeurListScheduling (SCIP *scip) |
SCIP_RETCODE | SCIPinitializeHeurListScheduling (SCIP *scip, SCIP_DIGRAPH *precedencegraph, SCIP_VAR **vars, int *durations, int **resourcedemands, int *capacities, int njobs, int nresources) |
#define HEUR_NAME "listscheduling" |
Definition at line 66 of file heur_listscheduling.c.
#define HEUR_DESC "scheduling specific primal heuristic which is based on bidirectional serial generation scheme" |
Definition at line 67 of file heur_listscheduling.c.
#define HEUR_DISPCHAR 'x' |
Definition at line 68 of file heur_listscheduling.c.
#define HEUR_PRIORITY 10000 |
Definition at line 69 of file heur_listscheduling.c.
#define HEUR_FREQ 0 |
Definition at line 70 of file heur_listscheduling.c.
#define HEUR_FREQOFS 0 |
Definition at line 71 of file heur_listscheduling.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 72 of file heur_listscheduling.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_BEFOREPRESOL |
Definition at line 73 of file heur_listscheduling.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 74 of file heur_listscheduling.c.
|
static |
initializes heuristic data structures
scip | SCIP data structure |
heurdata | heuristic data structure |
precedencegraph | precedence graph |
vars | start time variables |
durations | duration of the jobs independent of the resources |
resourcedemands | resource demand matrix |
capacities | capacities of the resources |
njobs | number if jobs |
nresources | number of resources |
Definition at line 103 of file heur_listscheduling.c.
References assert(), heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcopyDigraph(), SCIPdebug, SCIPdigraphComputeUndirectedComponents(), SCIPdigraphGetNComponents(), SCIPdigraphPrintComponents(), SCIPdigraphTopoSortComponents(), SCIPduplicateBlockMemoryArray, SCIPgetMessagehdlr(), TRUE, and vars.
Referenced by SCIPinitializeHeurListScheduling().
|
static |
scip | SCIP data structure |
heurdata | heuristic data structure |
Definition at line 161 of file heur_listscheduling.c.
References assert(), FALSE, heurdata, NULL, SCIP_OKAY, SCIPdigraphFree(), and SCIPfreeBlockMemoryArray.
Referenced by SCIP_DECL_HEURFREE(), and SCIPinitializeHeurListScheduling().
|
static |
constructs a solution with the given start values for the integer start variables
scip | SCIP data structure |
sol | solution to be constructed |
vars | integer start variables |
starttimes | start times for the integer start variables |
nvars | number of integer start variables |
Definition at line 197 of file heur_listscheduling.c.
References nvars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPsetSolVal(), sol, var, and vars.
Referenced by executeHeuristic().
|
static |
insert given job into the profiles
scip | SCIP data structure |
profiles | array of resource profiles |
nprofiles | number of profiles |
starttime | start time of the job |
duration | duration of the job |
demands | profile depending demands |
infeasible | pointer to store if the insertion is infeasible |
Definition at line 224 of file heur_listscheduling.c.
References SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SCIPprofileInsertCore().
Referenced by performBackwardScheduling(), and performForwardScheduling().
|
static |
retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles
profiles | array of resource profiles |
nprofiles | number of profiles |
est | earliest start time |
lst | latest start time |
duration | duration of the job |
demands | profile depending demands |
infeasible | pointer to store if it is infeasible to do |
Definition at line 250 of file heur_listscheduling.c.
References assert(), FALSE, r, SCIP_Bool, SCIPdebugMessage, SCIPprofileGetEarliestFeasibleStart(), and TRUE.
Referenced by performForwardScheduling().
|
static |
retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles
profiles | array of resource profiles |
nprofiles | number of profiles |
lst | latest start time |
duration | duration of the job |
demands | profile depending demands |
infeasible | pointer to store if it is infeasible to do |
Definition at line 301 of file heur_listscheduling.c.
References assert(), FALSE, r, SCIP_Bool, SCIPdebugMessage, SCIPprofileGetLatestFeasibleStart(), and TRUE.
Referenced by performBackwardScheduling().
collect earliest and latest start times for all variables in the order given in the variables array
scip | SCIP data structure |
vars | array of start time variables |
ests | array to store the earliest start times |
lsts | array to store the latest start times |
nvars | number of variables |
Definition at line 346 of file heur_listscheduling.c.
References assert(), NULL, nvars, SCIP_LPSOLSTAT_OPTIMAL, SCIP_STAGE_SOLVING, SCIPgetLPSolstat(), SCIPgetSolVal(), SCIPgetStage(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), var, and vars.
Referenced by executeHeuristic().
|
static |
propagate the earliest start time of the given job via the precedence graph to all successors jobs
precedencegraph | precedence graph |
ests | array of earliest start time for each job |
lsts | array of latest start times for each job |
pred | index of the job which earliest start time showed propagated |
duration | duration of the job |
infeasible | pointer to store if the propagate detected an infeasibility |
Definition at line 381 of file heur_listscheduling.c.
References MAX, SCIP_Bool, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE.
Referenced by performForwardScheduling().
|
static |
propagate the latest start time of the given job via the precedence graph w.r.t. all successors jobs
precedencegraph | precedence graph |
lsts | array of latest start times for each job |
pred | index of the job which earliest start time showed propagated |
duration | duration of the job |
Definition at line 416 of file heur_listscheduling.c.
References MIN, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().
Referenced by performBackwardScheduling().
|
static |
perform forward scheduling, that is, assigned jobs (in the given ordering) to their earliest start time, propagate w.r.t. the precedence graph and resource profiles
scip | SCIP data structure |
heurdata | heuristic data |
starttimes | array to store the start times for each job |
lsts | array of latest start times for each job |
perm | permutation defining the order of the jobs |
makespan | pointer to store the makespan of the forward scheduling solution |
infeasible | pointer to store if an infeasibility was detected |
Definition at line 442 of file heur_listscheduling.c.
References assert(), FALSE, heurdata, MAX, NULL, profilesFindEarliestFeasibleStart(), profilesInsertJob(), propagateEst(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPprofileCreate(), and SCIPprofileFree().
Referenced by executeHeuristic().
|
static |
perform backward scheduling, that is, schedule jobs (in the ordering of their latest completion time) to their and propagate w.r.t. the precedence graph and resource profiles
scip | SCIP data structure |
heurdata | heuristic data |
starttimes | array of latest start times for each job |
perm | permutation defining the order of jobs |
infeasible | pointer to store if an infeasibility was detected |
Definition at line 525 of file heur_listscheduling.c.
References assert(), heurdata, NULL, profilesFindLatestFeasibleStart(), profilesInsertJob(), propagateLst(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPprofileCreate(), and SCIPprofileFree().
Referenced by executeHeuristic().
|
static |
creates a permutation of the job w.r.t. earliest start time
scip | SCIP data structure |
starttimes | array of start times for each job |
ests | earliest start times |
perm | array to store the permutation w.r.t. earliest start time |
njobs | number of jobs |
Definition at line 598 of file heur_listscheduling.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortIntInt().
Referenced by executeHeuristic().
|
static |
creates a permutation of the job w.r.t. latest completion time
scip | SCIP data structure |
starttimes | array of start times for each job |
durations | array of durations |
perm | array to store the permutation w.r.t. latest completion time |
njobs | number of jobs |
Definition at line 626 of file heur_listscheduling.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownIntInt().
Referenced by executeHeuristic().
|
static |
execution method of heuristic
scip | SCIP data structure |
heur | Heuristic data structure |
result | pointer to store whether solution is found or not |
Definition at line 654 of file heur_listscheduling.c.
References assert(), collectEstLst(), constructSolution(), FALSE, getEstPermutation(), getLctPermuataion(), heurdata, NULL, performBackwardScheduling(), performForwardScheduling(), result, SCIP_Bool, SCIP_CALL, SCIP_FOUNDSOL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIPallocBufferArray, SCIPcreateOrigSol(), SCIPdigraphGetComponent(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetLPSolstat(), SCIPgetSolVal(), SCIPgetStage(), SCIPheurGetData(), SCIPsortRealInt(), SCIPtrySolFree(), sol, TRUE, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 768 of file heur_listscheduling.c.
References assert(), heurdata, heurdataFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
|
static |
execution method of primal heuristic
Definition at line 807 of file heur_listscheduling.c.
References assert(), executeHeuristic(), HEUR_NAME, heurdata, NULL, result, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPdebugMessage, and SCIPheurGetData().
SCIP_RETCODE SCIPincludeHeurListScheduling | ( | SCIP * | scip | ) |
creates the list scheduling primal heuristic and includes it in SCIP
scip | SCIP data structure |
Definition at line 843 of file heur_listscheduling.c.
References assert(), FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPincludeHeurBasic(), and SCIPsetHeurFree().
Referenced by runShell().
SCIP_RETCODE SCIPinitializeHeurListScheduling | ( | SCIP * | scip, |
SCIP_DIGRAPH * | precedencegraph, | ||
SCIP_VAR ** | vars, | ||
int * | durations, | ||
int ** | resourcedemands, | ||
int * | capacities, | ||
int | njobs, | ||
int | nresources ) |
initialize heuristic
scip | SCIP data structure |
precedencegraph | precedence graph |
vars | start time variables |
durations | duration of the jobs independent of the resources |
resourcedemands | resource demand matrix |
capacities | resource capacities |
njobs | number if jobs |
nresources | number of resources |
Definition at line 870 of file heur_listscheduling.c.
References assert(), HEUR_NAME, heurdata, heurdataFree(), heurdataInit(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfindHeur(), SCIPheurGetData(), and vars.
Referenced by SCIPcreateSchedulingProblem().