FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Job shop scheduling

Description
A company has received an order for three types of wallpapers. Every paper type is produced as a continuous roll of paper that passes through several machines, each printing a different color. The order in which the papers are run through the machines depends on the design of the paper. The processing times differ depending on the surface that needs to be printed. Knowing that every machine can only process one wallpaper at a time and that a paper cannot be processed by several machines simultaneously, how should the paper printing be scheduled on the machines in order to finish the order as early as possible?

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 7.3 'Job shop scheduling' (b3jobshop.mos)

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

Data Files

jobshop_graph.mos

(!******************************************************
Mosel Example Problems
======================

file jobshop.mos

TYPE:         Job shop scheduling problem
DIFFICULTY:   3
FEATURES:     MIP problem, formulating disjunctions (BigM);
dynamic array', range', exists', forall-do',
graphical solution representation
DESCRIPTION:  A company has received an order for three types of
wallpapers. Every paper type is produced as a continuous
roll of paper that passes through several machines, each
printing a different color. The order in which the papers
are run through the machines depends on the design of the
paper. The processing times differ depending on the surface
that needs to be printed.
Knowing that every machine can only process one wallpaper
at a time and that a paper cannot be processed by several
machines simultaneously, how should the paper printing be
scheduled on the machines in order to finish the order as
early as possible?
FURTHER INFO: Applications of optimization with Xpress-MP',
Section 7.3 Job shop scheduling'

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Nov. 2017
*******************************************************!)

model "Job shop"
uses "mmxprs","mmsvg"

declarations
JOBS: range                         ! Set of jobs (wall paper types)
MACH: range                         ! Set of machines (colors)

DUR: array(MACH,JOBS) of integer    ! Durations per machine and paper
NUMT: array(JOBS) of integer        ! Number of tasks per job
SEQ: array(JOBS,MACH) of integer    ! Machine sequence per job
NUMD: array(MACH) of integer        ! No. of jobs (disjunctions) per machine
DISJ: array(MACH,JOBS) of integer   ! List of jobs per machine

start: dynamic array(MACH,JOBS) of mpvar   ! Start times of tasks
finish: mpvar                       ! Schedule completion time
y: dynamic array(range) of mpvar    ! Disjunction variables
end-declarations

initializations from 'jobshop.dat'
DUR NUMT SEQ NUMD DISJ
end-initializations

forall(m in MACH, j in JOBS | DUR(m,j)>0 ) create(start(m,j))

BIGM:=sum(m in MACH, j in JOBS) DUR(m,j)  ! Some (sufficiently) large value

! Precedence constraints
forall(j in JOBS)
PrecLast(j):= finish >= start(SEQ(j,NUMT(j)),j) + DUR(SEQ(j,NUMT(j)),j)
forall(j in JOBS, m in 1..NUMT(j)-1)
Prec(j,m):= start(SEQ(j,m),j)+DUR(SEQ(j,m),j) <= start(SEQ(j,m+1),j)

! Disjunctions
d:=1
forall(m in MACH, i,j in 1..NUMD(m) | i<j) do
create(y(d))
y(d) is_binary
Disj1(m,i,j):=
start(m,DISJ(m,i))+DUR(m,DISJ(m,i)) <= start(m,DISJ(m,j))+BIGM*y(d)
Disj2(m,i,j):=
start(m,DISJ(m,j))+DUR(m,DISJ(m,j)) <= start(m,DISJ(m,i))+BIGM*(1-y(d))
d+=1
end-do

! Bound on latest completion time
finish <= BIGM

! Solve the problem: minimize latest completion time
minimize(finish)

! Solution printing
declarations
COLOR: array(MACH) of string         ! Colors printed by the machines
end-declarations

initializations from 'jobshop.dat'
COLOR
end-initializations

writeln("Total completion time: ", getobjval)
write("     ")
forall(j in JOBS) write(strfmt(j,6))
writeln
forall(m in MACH) do
write(strfmt(COLOR(m),-7))
forall(j in JOBS)
if(DUR(m,j)>0) then
write(strfmt(getsol(start(m,j)),3), "-", getsol(start(m,j))+DUR(m,j))
else
write(strfmt(" ",6))
end-if
writeln
end-do

! Solution drawing
declarations
JobGraph: array(JOBS) of string
end-declarations

svgsetgraphviewbox(0,0,round(getobjval),12*(max(m in MACH)m)+1)
svgsetgraphscale(5)
svgsetgraphlabels("Time","")

forall(j in JOBS) do
JobGraph(j):= "J"+j
svgsetstyle(SVG_FILL,SVG_CURRENT)
end-do

forall(m in MACH, j in JOBS)