 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Flow-shop scheduling

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 wait 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 explanation of this example: 'Applications of optimization with Xpress-MP', Section 7.2 'Flow-shop scheduling'

Source Files

Data Files

flowshop_graph.mos

```(!******************************************************
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)   