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

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'


Source Files

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
   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 

Back to examples browserPrevious exampleNext example