(!******************************************************
   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) 2002 Dash Associates
       author: S. Heipcke
*******************************************************!)

model "Job shop"
 uses "mmxprs","mmive"
 
 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: array(MACH,JOBS) of mpvar    ! Start times of tasks
  finish: mpvar                       ! Schedule completion time
  y: 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 integer
  GCOLOR: array(JOBS) of integer
 end-declarations

 GCOLOR:= [IVE_RED, IVE_CYAN, IVE_YELLOW]
 IVEzoom(0,0,round(getobjval)+3,max(m in MACH)m+1)
 
 forall(j in JOBS) JobGraph(j):= IVEaddplot("Job "+j, GCOLOR(j) )
  
 forall(m in MACH, j in JOBS) 
  IVEdrawarrow(JobGraph(j), getsol(start(m,j)), m, 
                            getsol(start(m,j))+DUR(m,j), m)

end-model