Detailed Description
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) |
Macro Definition Documentation
◆ HEUR_NAME
#define HEUR_NAME "listscheduling" |
Definition at line 57 of file heur_listscheduling.c.
Referenced by SCIP_DECL_HEUREXEC(), SCIPincludeHeurListScheduling(), and SCIPinitializeHeurListScheduling().
◆ HEUR_DESC
#define HEUR_DESC "scheduling specific primal heuristic which is based on bidirectional serial generation scheme" |
Definition at line 58 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_DISPCHAR
#define HEUR_DISPCHAR 'x' |
Definition at line 59 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_PRIORITY
#define HEUR_PRIORITY 10000 |
Definition at line 60 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_FREQ
#define HEUR_FREQ 0 |
Definition at line 61 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_FREQOFS
#define HEUR_FREQOFS 0 |
Definition at line 62 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_MAXDEPTH
#define HEUR_MAXDEPTH -1 |
Definition at line 63 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_TIMING
#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_BEFOREPRESOL |
Definition at line 64 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
◆ HEUR_USESSUBSCIP
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 65 of file heur_listscheduling.c.
Referenced by SCIPincludeHeurListScheduling().
Function Documentation
◆ heurdataInit()
|
static |
initializes heuristic data structures
- Parameters
-
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 94 of file heur_listscheduling.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcopyDigraph(), SCIPdebug, SCIPdigraphComputeUndirectedComponents(), SCIPdigraphGetNComponents(), SCIPdigraphPrintComponents(), SCIPdigraphTopoSortComponents(), SCIPduplicateBlockMemoryArray, SCIPgetMessagehdlr(), and TRUE.
Referenced by SCIPinitializeHeurListScheduling().
◆ heurdataFree()
|
static |
- Parameters
-
scip SCIP data structure heurdata heuristic data structure
Definition at line 152 of file heur_listscheduling.c.
References FALSE, NULL, SCIP_OKAY, SCIPdigraphFree(), and SCIPfreeBlockMemoryArray.
Referenced by SCIP_DECL_HEURFREE(), and SCIPinitializeHeurListScheduling().
◆ constructSolution()
|
static |
constructs a solution with the given start values for the integer start variables
- Parameters
-
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 188 of file heur_listscheduling.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPsetSolVal().
Referenced by executeHeuristic().
◆ profilesInsertJob()
|
static |
insert given job into the profiles
- Parameters
-
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 215 of file heur_listscheduling.c.
References SCIP_CALL, SCIP_OKAY, and SCIPprofileInsertCore().
Referenced by performBackwardScheduling(), and performForwardScheduling().
◆ profilesFindEarliestFeasibleStart()
|
static |
retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles
- Parameters
-
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 241 of file heur_listscheduling.c.
References FALSE, r, SCIP_Bool, SCIPdebugMessage, SCIPprofileGetEarliestFeasibleStart(), and TRUE.
Referenced by performForwardScheduling().
◆ profilesFindLatestFeasibleStart()
|
static |
retruns for the given job (duration and demands) the earliest feasible start time w.r.t. all profiles
- Parameters
-
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 292 of file heur_listscheduling.c.
References FALSE, r, SCIP_Bool, SCIPdebugMessage, SCIPprofileGetLatestFeasibleStart(), and TRUE.
Referenced by performBackwardScheduling().
◆ collectEstLst()
|
static |
collect earliest and latest start times for all variables in the order given in the variables array
- Parameters
-
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 337 of file heur_listscheduling.c.
References NULL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_STAGE_SOLVING, SCIPgetLPSolstat(), SCIPgetSolVal(), SCIPgetStage(), SCIPvarGetLbLocal(), and SCIPvarGetUbGlobal().
Referenced by executeHeuristic().
◆ propagateEst()
|
static |
propagate the earliest start time of the given job via the precedence graph to all successors jobs
- Parameters
-
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 372 of file heur_listscheduling.c.
References MAX, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE.
Referenced by performForwardScheduling().
◆ propagateLst()
|
static |
propagate the latest start time of the given job via the precedence graph w.r.t. all successors jobs
- Parameters
-
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 407 of file heur_listscheduling.c.
References SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().
Referenced by performBackwardScheduling().
◆ performForwardScheduling()
|
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
- Parameters
-
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 433 of file heur_listscheduling.c.
References FALSE, MAX, NULL, profilesFindEarliestFeasibleStart(), profilesInsertJob(), propagateEst(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPprofileCreate(), and SCIPprofileFree().
Referenced by executeHeuristic().
◆ performBackwardScheduling()
|
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
- Parameters
-
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 516 of file heur_listscheduling.c.
References NULL, profilesFindLatestFeasibleStart(), profilesInsertJob(), propagateLst(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPprofileCreate(), and SCIPprofileFree().
Referenced by executeHeuristic().
◆ getEstPermutation()
|
static |
creates a permutation of the job w.r.t. earliest start time
- Parameters
-
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 589 of file heur_listscheduling.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortIntInt().
Referenced by executeHeuristic().
◆ getLctPermuataion()
|
static |
creates a permutation of the job w.r.t. latest completion time
- Parameters
-
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 617 of file heur_listscheduling.c.
References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownIntInt().
Referenced by executeHeuristic().
◆ executeHeuristic()
|
static |
execution method of heuristic
- Parameters
-
scip SCIP data structure heur Heuristic data structure result pointer to store whether solution is found or not
Definition at line 645 of file heur_listscheduling.c.
References collectEstLst(), constructSolution(), FALSE, getEstPermutation(), getLctPermuataion(), NULL, performBackwardScheduling(), performForwardScheduling(), 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(), and TRUE.
Referenced by SCIP_DECL_HEUREXEC().
◆ SCIP_DECL_HEURFREE()
|
static |
destructor of primal heuristic to free user data (called when SCIP is exiting)
Definition at line 759 of file heur_listscheduling.c.
References heurdataFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().
◆ SCIP_DECL_HEUREXEC()
|
static |
execution method of primal heuristic
Definition at line 798 of file heur_listscheduling.c.
References executeHeuristic(), HEUR_NAME, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPdebugMessage, and SCIPheurGetData().
◆ SCIPincludeHeurListScheduling()
SCIP_RETCODE SCIPincludeHeurListScheduling | ( | SCIP * | scip | ) |
creates the list scheduling primal heuristic and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 834 of file heur_listscheduling.c.
References FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory(), SCIPincludeHeurBasic(), and SCIPsetHeurFree().
Referenced by runShell().
◆ SCIPinitializeHeurListScheduling()
SCIP_RETCODE SCIPinitializeHeurListScheduling | ( | SCIP * | scip, |
SCIP_DIGRAPH * | precedencegraph, | ||
SCIP_VAR ** | vars, | ||
int * | durations, | ||
int ** | resourcedemands, | ||
int * | capacities, | ||
int | njobs, | ||
int | nresources | ||
) |
initialize heuristic
- Parameters
-
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 861 of file heur_listscheduling.c.
References HEUR_NAME, heurdataFree(), heurdataInit(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfindHeur(), and SCIPheurGetData().
Referenced by SCIPcreateSchedulingProblem().