(!******************************************************
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
svgaddgroup(JobGraph(j), "Job "+j )
svgsetstyle(SVG_FILL,SVG_CURRENT)
end-do
forall(m in MACH, j in JOBS)
svgaddrectangle(JobGraph(j), getsol(start(m,j)), 10*m, DUR(m,j), 4)
svgaddgroup("M", "", SVG_BLACK)
forall(m in MACH) svgaddtext(0,10*m-2,COLOR(m))
svgsave("jobshop.svg")
svgrefresh
svgwaitclose("Close browser window to terminate model execution.", 1)
end-model
|
