(!******************************************************
Mosel Example Problems
======================
file flowshop.mos
`````````````````
TYPE: Flow-shop scheduling problem
DIFFICULTY: 4
FEATURES: MIP problem, alternative formulation using SOS1,
graphical solution representation
DESCRIPTION: A workshop with three different machines produces six
types of pipes, for which the durations of the processing
steps are given. Every workpiece runs through the machines
in the same order. Once started, any operations must be
carried out without interruption, but the workpieces may
inwait between the machines. Every machine only processes
one piece at a time. A workpiece may not overtake any
other by passing onto the following machine. Which is the
sequence of workpieces that minimizes the total time for
completing all pieces?
FURTHER INFO: `Applications of optimization with Xpress-MP',
Section 7.2 `Flow-shop scheduling'
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Sep. 2107
*******************************************************!)
model "Flow shop"
uses "mmxprs", "mmsvg"
declarations
NM = 3 ! Number of machines
NJ = 6 ! Number of jobs
MACH = 1..NM
RANKS = 1..NJ
JOBS = 1..NJ
DUR: array(MACH,JOBS) of integer ! Durations of jobs on machines
rank: array(JOBS,RANKS) of mpvar ! 1 if job j has rank k, 0 otherwise
empty: array(MACH,1..NJ-1) of mpvar ! Space between jobs of ranks k and k+1
inwait: array(1..NM-1,RANKS) of mpvar ! Waiting time between machines m
! and m+1 for job of rank k
start: array(MACH,RANKS) of mpvar ! Start of job rank k on machine m
! (optional)
end-declarations
initializations from 'flowshop.dat'
DUR
end-initializations
! Objective: total inwaiting time (= time before first job + times between
! jobs) on the last machine
TotWait:= sum(m in 1..NM-1,j in JOBS) (DUR(m,j)*rank(j,1)) +
sum(k in 1..NJ-1) empty(NM,k)
! Every position gets a job
forall(k in RANKS) OneJobPos(k):= sum(j in JOBS) rank(j,k) = 1
! Every job is assigned a rank
forall(j in JOBS) JobRank(j):= sum(k in RANKS) rank(j,k) = 1
! Relations between the end of job rank k on machine m and start of job on
! machine m+1
forall(m in 1..NM-1,k in 1..NJ-1)
Prec(m,k):=
empty(m,k) + sum(j in JOBS) DUR(m,j)*rank(j,k+1) + inwait(m,k+1) =
inwait(m,k) + sum(j in JOBS) DUR(m+1,j)*rank(j,k) + empty(m+1,k)
! Calculation of start times (to facilitate the interpretation of results)
forall(m in MACH, k in RANKS)
Start(m,k):= start(m,k) = sum(u in 1..m-1,j in JOBS) DUR(u,j)*rank(j,1) +
sum(p in 1..k-1,j in JOBS) DUR(m,j)*rank(j,p) +
sum(p in 1..k-1) empty(m,p)
! First machine has no idle times
forall(k in 1..NJ-1) empty(1,k) = 0
! First job has no inwaiting times
forall(m in 1..NM-1) inwait(m,1) = 0
forall(j in JOBS, k in RANKS) rank(j,k) is_binary
(! Alternative formulations using SOS-1:
forall(j in JOBS) RankSet(j):= sum(k in RANKS) k*rank(j,k) is_sos1
forall(k in RANKS) JobSet(k):= sum(j in JOBS) j*rank(j,k) is_sos1
!)
! Solve the problem
minimize(TotWait)
! Solution printing
writeln("Total inwaiting time for last machine: ", getobjval)
write(strfmt("Item",-11))
forall(k in RANKS) write(strfmt(getsol(sum(j in JOBS) j*rank(j,k)),3))
writeln
forall(m in MACH) do
write("Machine ", m, ": ")
forall(k in RANKS) write(strfmt(getsol(start(m,k)),3))
writeln
end-do
! Solution drawing
declarations
JobGraph: array(JOBS) of string
end-declarations
svgsetgraphviewbox(0,0,
max(m in MACH,k in RANKS) start(m,k).sol+max(m in MACH,j in JOBS)DUR(m,j), NM*5)
svgsetgraphscale(10)
svgsetgraphlabels("Time", "")
forall(k in RANKS) do
JobGraph(k):="J"+k
svgaddgroup(JobGraph(k), "Job "+round(getsol(sum(j in JOBS) j*rank(j,k))) )
svgsetstyle(SVG_FILL, SVG_CURRENT)
end-do
forall(m in MACH, k in RANKS)
svgaddrectangle(JobGraph(k), getsol(start(m,k)), m*4,
DUR(m,round(getsol(sum(j in JOBS) j*rank(j,k)))), 1)
svgaddgroup("M", "", SVG_BLACK)
forall(m in MACH) svgaddtext(0,m*4-1, "Machine "+m)
svgsave("flowshop.svg")
svgrefresh
svgwaitclose("Close browser window to terminate model execution.", 1)
end-model