Detailed Description

scheduling specific primal heuristic which is based on bidirectional serial generation scheme.

Author: Jens Schulz

Definition in file heur_listscheduling.c.

#include <assert.h>
#include <string.h>
#include "heur_listscheduling.h"
#include "scip/pub_misc.h"

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 56 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 57 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 'x'

Definition at line 58 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 10000

Definition at line 59 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_FREQ

#define HEUR_FREQ 0

Definition at line 60 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 61 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 62 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE | SCIP_HEURTIMING_BEFOREPRESOL

Definition at line 63 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 64 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

Function Documentation

◆ heurdataInit()

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

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 93 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 SCIP_RETCODE heurdataFree	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata
	)

static

Parameters

scip	SCIP data structure
heurdata	heuristic data structure

Definition at line 151 of file heur_listscheduling.c.

References FALSE, NULL, SCIP_OKAY, SCIPdigraphFree(), and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_HEURFREE(), and SCIPinitializeHeurListScheduling().

◆ constructSolution()

static SCIP_RETCODE constructSolution	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_VAR **	vars,
		int *	starttimes,
		int	nvars
	)

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 187 of file heur_listscheduling.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPsetSolVal().

Referenced by executeHeuristic().

◆ profilesInsertJob()

static SCIP_RETCODE profilesInsertJob	(	SCIP *	scip,
		SCIP_PROFILE **	profiles,
		int	nprofiles,
		int	starttime,
		int	duration,
		int *	demands,
		SCIP_Bool *	infeasible
	)

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 214 of file heur_listscheduling.c.

References SCIP_CALL, SCIP_OKAY, and SCIPprofileInsertCore().

Referenced by performBackwardScheduling(), and performForwardScheduling().

◆ profilesFindEarliestFeasibleStart()

static int profilesFindEarliestFeasibleStart	(	SCIP_PROFILE **	profiles,
		int	nprofiles,
		int	est,
		int	lst,
		int	duration,
		int *	demands,
		SCIP_Bool *	infeasible
	)

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 240 of file heur_listscheduling.c.

References FALSE, r, SCIP_Bool, SCIPdebugMessage, SCIPprofileGetEarliestFeasibleStart(), and TRUE.

Referenced by performForwardScheduling().

◆ profilesFindLatestFeasibleStart()

static int profilesFindLatestFeasibleStart	(	SCIP_PROFILE **	profiles,
		int	nprofiles,
		int	lst,
		int	duration,
		int *	demands,
		SCIP_Bool *	infeasible
	)

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 291 of file heur_listscheduling.c.

References FALSE, r, SCIP_Bool, SCIPdebugMessage, SCIPprofileGetLatestFeasibleStart(), and TRUE.

Referenced by performBackwardScheduling().

◆ collectEstLst()

static void collectEstLst	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int *	ests,
		int *	lsts,
		int	nvars
	)

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 336 of file heur_listscheduling.c.

References NULL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_STAGE_SOLVING, SCIPgetLPSolstat(), SCIPgetSolVal(), SCIPgetStage(), SCIPvarGetLbLocal(), and SCIPvarGetUbGlobal().

Referenced by executeHeuristic().

◆ propagateEst()

static void propagateEst	(	SCIP_DIGRAPH *	precedencegraph,
		int *	ests,
		int *	lsts,
		int	pred,
		int	duration,
		SCIP_Bool *	infeasible
	)

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 371 of file heur_listscheduling.c.

References MAX, SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), and TRUE.

Referenced by performForwardScheduling().

◆ propagateLst()

static void propagateLst	(	SCIP_DIGRAPH *	precedencegraph,
		int *	lsts,
		int	pred,
		int	duration
	)

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 406 of file heur_listscheduling.c.

References SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().

Referenced by performBackwardScheduling().

◆ performForwardScheduling()

static SCIP_RETCODE performForwardScheduling	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		int *	starttimes,
		int *	lsts,
		int *	perm,
		int *	makespan,
		SCIP_Bool *	infeasible
	)

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 432 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 SCIP_RETCODE performBackwardScheduling	(	SCIP *	scip,
		SCIP_HEURDATA *	heurdata,
		int *	starttimes,
		int *	perm,
		SCIP_Bool *	infeasible
	)

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 515 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 SCIP_RETCODE getEstPermutation	(	SCIP *	scip,
		int *	starttimes,
		int *	ests,
		int *	perm,
		int	njobs
	)

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 588 of file heur_listscheduling.c.

References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortIntInt().

Referenced by executeHeuristic().

◆ getLctPermuataion()

static SCIP_RETCODE getLctPermuataion	(	SCIP *	scip,
		int *	starttimes,
		int *	durations,
		int *	perm,
		int	njobs
	)

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 616 of file heur_listscheduling.c.

References SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPsortDownIntInt().

Referenced by executeHeuristic().

◆ executeHeuristic()

static SCIP_RETCODE executeHeuristic	(	SCIP *	scip,
		SCIP_HEUR *	heur,
		SCIP_RESULT *	result
	)

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 644 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 SCIP_DECL_HEURFREE ( heurFreeListScheduling )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 758 of file heur_listscheduling.c.

References heurdataFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecListScheduling )

static

execution method of primal heuristic

Definition at line 797 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 833 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 860 of file heur_listscheduling.c.

References HEUR_NAME, heurdataFree(), heurdataInit(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfindHeur(), and SCIPheurGetData().

Referenced by SCIPcreateSchedulingProblem().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

Function Documentation

◆ heurdataInit()

◆ heurdataFree()

◆ constructSolution()

◆ profilesInsertJob()

◆ profilesFindEarliestFeasibleStart()

◆ profilesFindLatestFeasibleStart()

◆ collectEstLst()

◆ propagateEst()

◆ propagateLst()

◆ performForwardScheduling()

◆ performBackwardScheduling()

◆ getEstPermutation()

◆ getLctPermuataion()

◆ executeHeuristic()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurListScheduling()

◆ SCIPinitializeHeurListScheduling()