Scippy

SCIP

Solving Constraint Integer Programs

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"

◆ 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.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   'x'

Definition at line 68 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   10000

Definition at line 69 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 70 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 71 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 72 of file heur_listscheduling.c.

Referenced by SCIPincludeHeurListScheduling().

◆ HEUR_TIMING

Definition at line 73 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 74 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
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 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
scipSCIP data structure
heurdataheuristic data structure

Definition at line 161 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
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 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
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_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
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 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
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 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
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 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
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, 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
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()

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
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 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
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 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
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()

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
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()

static 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 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 807 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
scipSCIP data structure

Definition at line 843 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
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 HEUR_NAME, heurdataFree(), heurdataInit(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfindHeur(), and SCIPheurGetData().

Referenced by SCIPcreateSchedulingProblem().