FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

LCSP: Labour constrained scheduling problem

Description
Schedule the processing of a set of jobs with resource usage profiles subject to precedence constraints between certain pairs of jobs. The objective is to minimize the makespan (completion time of last job).
  • difficult MIP problem
  • dynamic creation of variables
  • constraint definitions with logical conditions
  • using parameters in the optimization function
  • if-then-else statement


Source Files





lscp1.mos

(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file lscp1.mos                                      *
  * ``````````````                                      *
  * Example for the use of the Mosel language           *
  * (Labour Constrained Scheduling Problem)             *
  *                                                     *
  * (c) 2008 Fair Isaac Corporation                     *
  *     author: S. Heipcke, 2001, rev. Mar. 2018        *
  *******************************************************!)

model Lscp1                        ! Start a new model

uses "mmxprs"                      ! Load the optimizer library
uses "mmsystem"

parameters
 WEAKPREC = false ! false: use formulation with strong precedence constraints
 LOADSOL = true   ! Whether to load a known feasible solution
end-parameters

declarations
 NJ     = 25     ! Number of jobs (dummy end job is last and is counted)
 RJ     = 1..NJ  ! Range of jobs
 RJT    = 1..5   ! Range of job-types (includes dummy end job type)
 RJOBL  = 1..9   ! Range of job lengths
 TT     = 73     ! Time horizon
 RT     = 1..TT  ! Range of time slices
 RARCS  = 1..26  ! Range of precedence constraints
 LABOUR = 18     ! Number of workers available per period

 JT: array(RJ) of integer          ! Job-class for jobs
 P: array(RJT) of integer          ! Processing times of job-classes
                                   ! (must be positive)
 TMIN: array(RJ) of integer        ! Earliest start time for jobs
 TMAX: array(RJ) of integer        ! Latest start time for jobs
 LABREQ: array(RJT,RJOBL) of integer ! Labour requirement per period of
                                     ! job-type
 ARC: array(RARCS,1..2) of integer ! Precendence constraints (TAIL(a),HEAD(a))
 TAIL: array(RARCS) of integer     ! Tail of a precedence arc
 HEAD: array(RARCS) of integer     ! Head of a precedence arc

 HSOL: array(RJ) of integer        ! Start solution (optional)
 KnownSol: array(mpvar) of real    ! Known solution

 x: dynamic array(RT,RJ) of mpvar  ! 1 if job j starts at time t, else 0
 st: array(RJ) of mpvar            ! Start times of jobs
 Makespan: linctr                  ! Objective function
end-declarations
 
 JT:: [1,1,1,1,1,1,1,2,2,2,2,3,3,3,4,4,4,4,4,4,4,4,4,4,5]
 P::  [7,9,8,5] 
 TMIN:: [1,8,15,22,29,36,43, 
         1,10,19,28, 
         1,9,17, 
         9,14,19,24,29,34,39,44,49,54, 
         59]
 TMAX:: [23,30,37,44,51,58,65, 
         36,45,54,63, 
         14,29,44, 
         22,27,32,37,42,47,52,57,62,67, 
         72]
 LABREQ:: [12,12,6,2,2,2,2,0,0,
           12,12,6,2,2,2,2,2,2,
           12,12,3,3,3,3,3,3,0,
           6,6,6,3,3]
 ARC:: [1,2,
        2,3,
        3,4,
        4,5,
        5,6,
        6,7,
        8,9,
        9,10,
        10,11,
        12,13,
        13,14,
        15,16,
        16,17,
        17,18,
        18,19,
        19,20,
        20,21,
        21,22,
        22,23,
        23,24,
        12,15,
        13,18,
        14,21,
        7,25,
        11,25,
        24,25]
 HSOL:: [ 3,10,22,32,39,47,57, 
          5,17,42,52, 
	  8,20,28, 
	 16,24,29,34,39,44,49,54,59,64,
	 69]

 forall(a in RARCS) do
  TAIL(a):=ARC(a,1)
  HEAD(a):=ARC(a,2)
 end-do   

                                   ! Create the variables
 forall(t in RT,j in RJ | t>=TMIN(j) and t<= TMAX(j))
  create(x(t,j))

                                   ! Link s_j variables with x_jt variables
 forall(j in RJ) Link(j):= st(j) = sum(t in RT|exists(x(t,j))) t * x(t,j)

                                   ! Each job has to start exactly once
 forall(j in RJ) Start(j):= sum(t in RT|exists(x(t,j))) x(t,j) = 1

                                   ! Labour capacity constraints
 forall(t in RT) Labour(t):= sum(i in 1..NJ-1,u in 1..P(JT(i)) | 
   t-u+1>=1 and t-u+1<=TT) LABREQ(JT(i),u) * x(t-u+1,i) <= LABOUR

 if (WEAKPREC) then                ! Weak precedence constraints
  forall(a in RARCS) WPrec(a):= st(HEAD(a)) >= st(TAIL(a)) + P(JT(TAIL(a)))
 else                              ! Strong precedence constraints
  forall(a in RARCS, t in TMIN(HEAD(a))..minlist(TMAX(HEAD(a)),TT) |
    t-P(JT(TAIL(a))) >= TMIN(TAIL(a)) and t-P(JT(TAIL(a))) <= TMAX(TAIL(a)))
      SPrec(a,t):= sum(s in 1..t) x(s,HEAD(a)) <=
        sum(s in 1..t-P(JT(TAIL(a)))) x(s,TAIL(a))
 end-if
 
 forall(t in RT,j in RJ|exists(x(t,j)))
  x(t,j) is_binary                 ! Variables x are 0/1
  
! Objective function: minimize the start time of the final (dummy) job
! (it can only start once all other jobs are complete).
 Makespan:=st(NJ)

! Display solver log
 setparam("XPRS_verbose", true)

! We know that there are only integer solutions to this problem given that all
! coefficients are integers
 setparam("XPRS_MIPADDCUTOFF", -0.999)

! Stop once a second solution is found
! setparam("XPRS_MAXMIPSOL", 2)

! Load a known MIP solution
 if LOADSOL then
  loadprob(Makespan)
  forall(j in RJ) KnownSol(x(HSOL(j),j)):=1
  addmipsol("InitSol", KnownSol)
 end-if

! Solve the problem
 minimize(Makespan)
                                   ! Print out the solution
 writeln("Solution:\n Objective: ", getobjval)

 forall(j in 1..NJ-1) do
  write(" start(", j,"): ", st(j).sol)
  if JT(j)<JT(j+1) then writeln; end-if
 end-do

 writeln("Resource use per time interval:")
 writeln("Capacity: ", text("#")*LABOUR)
 forall(t in 1..round(getobjval))
  writeln(strfmt(t,8), ": ", round(Labour(t).act) * text("*"))

end-model


This labour constrained scheduling problem is a simplification
of a practical problem arising in chemical industry. Jobs are 
subject to precedence constraints and have specified processing times. 
Moreover, for each job the labour requirement varies as the job is 
processed. Given the amount of labour available in each period, the 
problem is to finish all the jobs as soon as possible, that is, to 
minimize the makespan, subject to the precedence and labour constraints. 

An instance of LCSP is determined by a set N={1,...,n} of jobs, the 
processing time P(j) and labour profile L[j,1], ..., L[j,p(j)] of each 
job j in N, and a digraph D=(N,A) representing the precedence 
constraints between jobs. An amount L of labour is available in each 
period.

Furthermore, in the particular instance considered here the jobs are 
grouped into job types with similar processing times and labour 
requirements.

Back to examples browserPrevious exampleNext example