SCIP Doxygen Documentation
Loading...
Searching...
No Matches
heur_listscheduling.c File Reference

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"

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

◆ HEUR_DESC

#define HEUR_DESC   "scheduling specific primal heuristic which is based on bidirectional serial generation scheme"

Definition at line 67 of file heur_listscheduling.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'x'

Definition at line 68 of file heur_listscheduling.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   10000

Definition at line 69 of file heur_listscheduling.c.

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 70 of file heur_listscheduling.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 71 of file heur_listscheduling.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 72 of file heur_listscheduling.c.

◆ HEUR_TIMING

Definition at line 73 of file heur_listscheduling.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 74 of file heur_listscheduling.c.

Function Documentation

◆ heurdataInit()

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
scipSCIP data structure
heurdataheuristic data structure
precedencegraphprecedence graph
varsstart time variables
durationsduration of the jobs independent of the resources
resourcedemandsresource demand matrix
capacitiescapacities of the resources
njobsnumber if jobs
nresourcesnumber 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().

◆ heurdataFree()

SCIP_RETCODE heurdataFree ( SCIP * scip,
SCIP_HEURDATA * heurdata )
static
Parameters
scipSCIP data structure
heurdataheuristic 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().

◆ constructSolution()

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
scipSCIP data structure
solsolution to be constructed
varsinteger start variables
starttimesstart times for the integer start variables
nvarsnumber 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().

◆ profilesInsertJob()

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
scipSCIP data structure
profilesarray of resource profiles
nprofilesnumber of profiles
starttimestart time of the job
durationduration of the job
demandsprofile depending demands
infeasiblepointer 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().

◆ profilesFindEarliestFeasibleStart()

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
profilesarray of resource profiles
nprofilesnumber of profiles
estearliest start time
lstlatest start time
durationduration of the job
demandsprofile depending demands
infeasiblepointer 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().

◆ profilesFindLatestFeasibleStart()

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
profilesarray of resource profiles
nprofilesnumber of profiles
lstlatest start time
durationduration of the job
demandsprofile depending demands
infeasiblepointer 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().

◆ collectEstLst()

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
scipSCIP data structure
varsarray of start time variables
estsarray to store the earliest start times
lstsarray to store the latest start times
nvarsnumber 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().

◆ propagateEst()

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
precedencegraphprecedence graph
estsarray of earliest start time for each job
lstsarray of latest start times for each job
predindex of the job which earliest start time showed propagated
durationduration of the job
infeasiblepointer 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().

◆ propagateLst()

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
precedencegraphprecedence graph
lstsarray of latest start times for each job
predindex of the job which earliest start time showed propagated
durationduration of the job

Definition at line 416 of file heur_listscheduling.c.

References MIN, SCIPdigraphGetNSuccessors(), and SCIPdigraphGetSuccessors().

Referenced by performBackwardScheduling().

◆ performForwardScheduling()

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
scipSCIP data structure
heurdataheuristic data
starttimesarray to store the start times for each job
lstsarray of latest start times for each job
permpermutation defining the order of the jobs
makespanpointer to store the makespan of the forward scheduling solution
infeasiblepointer 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().

◆ performBackwardScheduling()

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
scipSCIP data structure
heurdataheuristic data
starttimesarray of latest start times for each job
permpermutation defining the order of jobs
infeasiblepointer 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().

◆ getEstPermutation()

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
scipSCIP data structure
starttimesarray of start times for each job
estsearliest start times
permarray to store the permutation w.r.t. earliest start time
njobsnumber of jobs

Definition at line 598 of file heur_listscheduling.c.

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

Referenced by executeHeuristic().

◆ getLctPermuataion()

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
scipSCIP data structure
starttimesarray of start times for each job
durationsarray of durations
permarray to store the permutation w.r.t. latest completion time
njobsnumber of jobs

Definition at line 626 of file heur_listscheduling.c.

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

Referenced by executeHeuristic().

◆ executeHeuristic()

◆ SCIP_DECL_HEURFREE()

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

◆ SCIP_DECL_HEUREXEC()

SCIP_DECL_HEUREXEC ( heurExecListScheduling )
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().

◆ SCIPincludeHeurListScheduling()

SCIP_RETCODE SCIPincludeHeurListScheduling ( SCIP * scip)

creates the list scheduling primal heuristic and includes it in SCIP

Parameters
scipSCIP 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().

◆ 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
scipSCIP data structure
precedencegraphprecedence graph
varsstart time variables
durationsduration of the jobs independent of the resources
resourcedemandsresource demand matrix
capacitiesresource capacities
njobsnumber if jobs
nresourcesnumber 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().