Initializing help system before first use

B. Scheduling problems
Description:

Problem name and type, features Difficulty
B‑1 Construction of a stadium: Project scheduling (Method of Potentials) ***
2 problems; selection with `|', sparse/dense format, naming and redefining constraints, subroutine: procedure for solution printing, forward declaration
B‑2 Flow shop scheduling ****
alternative formulation using SOS1
B‑3 Job shop scheduling ***
formulating disjunctions (BigM); dynamic array, range, exists, forall-do
B‑4 Sequencing jobs on a bottleneck machine: Single machine scheduling ***
3 different objectives; subroutine: procedure for solution printing, if-then
B‑5 Paint production: Asymmetric Traveling Salesman Problem (TSP) ***
solution printing, repeat-until, cast to integer, selection with `|', round
B‑6 Assembly line balancing **
encoding of arcs, range


File(s): b1stadium.mos (Mar. 2002 rev. Oct. 2009), b2flowshop.mos (Mar. 2002), b3jobshop.mos (Mar. 2002), b3jobshop2.mos (Mar. 2002), b4seq.mos (Mar. 2002), b5paint.mos (Mar. 2002), b6linebal.mos (Mar. 2002)
Data file(s): b1stadium.dat, b2flowshop.dat, b3jobshop.dat, b3jobshop2.dat, b4seq.dat, b5paint.dat, b6linebal.dat
b1stadium.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b1stadium.mos
   ``````````````````
   Construction of a stadium
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. Oct 2009
*******************************************************!)

model "B-1 Stadium construction"
 uses "mmxprs"
 
 forward procedure print_sol
 
 declarations   
  N = 19                              ! Number of tasks in the project 
                                      ! (last = fictitious end task)
  TASKS=1..N
  ARC: dynamic array(TASKS,TASKS) of real  ! Matrix of the adjacency graph 
  DUR: array(TASKS) of real           ! Duration of tasks
  start: array(TASKS) of mpvar        ! Start times of tasks
  obj1: real                          ! Solution of first problem
 end-declarations

 initializations from 'b1stadium.dat'
  ARC DUR
 end-initializations
 
! Precedence relations between tasks
 forall(i,j in TASKS | exists(ARC(i,j)))  
  Prec(i,j):= start(j) - start(i) >= DUR(i)

! Solve the first problem: minimize the total duration
 minimize(start(N))
 obj1:=getobjval
 
! Solution printing
 print_sol

! **** Extend the problem ****
 declarations
  BONUS: integer                      ! Bonus per week finished earlier
  MAXW: array(TASKS) of real          ! Max. reduction of tasks (in weeks)
  COST: array(TASKS) of real          ! Cost of reducing tasks by a week 
  save: array(TASKS) of mpvar         ! Number of weeks finished early
 end-declarations 

 initializations from 'b1stadium.dat'
  MAXW BONUS COST
 end-initializations

! Second objective function
 Profit:= BONUS*save(N) - sum(i in 1..N-1) COST(i)*save(i)

! Redefine precedence relations between tasks
 forall(i,j in TASKS | exists(ARC(i,j)))  
  Prec(i,j):= start(j) - start(i) + save(i) >= DUR(i)

! Total duration
 start(N) + save(N) = obj1

! Limit on number of weeks that may be saved
 forall(i in 1..N-1) save(i) <= MAXW(i)

! Solve the second problem: maximize the total profit
 maximize(Profit) 
 
! Solution printing
 writeln("Total profit: ", getsol(Profit))
 print_sol

!-----------------------------------------------------------------

 procedure print_sol
  writeln("Total duration: ", getsol(start(N)), " weeks")
  forall(i in 1..N-1)
   write(strfmt(i,2), ": ", strfmt(getsol(start(i)),-3),
    if(i mod 9 = 0,"\n",""))
  writeln
 end-procedure

end-model
b2flowshop.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b2flowshop.mos
   ```````````````````
   Flow shop production planning
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. Jun. 2015
*******************************************************!)

model "B-2 Flow shop"
 uses "mmxprs"
 
 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
  wtime: 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 'b2flowshop.dat'
  DUR
 end-initializations

! Objective: total waiting 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) sum(j in JOBS) rank(j,k) = 1

! Every job is assigned a rank
 forall(j in JOBS) 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)
  empty(m,k) + sum(j in JOBS) DUR(m,j)*rank(j,k+1) + wtime(m,k+1) =
   wtime(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) = 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 waiting times
 forall(m in 1..NM-1) wtime(m,1) = 0

 forall(j in JOBS, k in RANKS) rank(j,k) is_binary  

(! Alternative formulations using SOS-1: 
 forall(j in JOBS) sum(k in RANKS) k*rank(j,k) is_sos1 
 forall(k in RANKS) sum(j in JOBS) j*rank(j,k) is_sos1 
!)

! Solve the problem
 minimize(TotWait)

! Solution printing
 writeln("Total waiting 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 

end-model
b3jobshop.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b3jobshop.mos
   ``````````````````
   Job shop production planning.
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. Nov. 2017
*******************************************************!)

model "B-3 Job shop"
 uses "mmxprs"
 
 declarations                          
  JOBS=1..8                           ! Set of jobs (operations)

  DUR: array(JOBS) of integer         ! Durations of jobs on machines
  ARC: dynamic array(JOBS,JOBS) of integer   ! Precedence graph
  DISJ: dynamic array(JOBS,JOBS) of integer  ! Disjunctions between jobs
 
  start: array(JOBS) of mpvar         ! Start times of jobs
  finish: mpvar                       ! Schedule completion time
  y: dynamic array(range) of mpvar    ! Disjunction variables 
 end-declarations

 initializations from 'b3jobshop.dat'
  DUR ARC DISJ
 end-initializations
 
 BIGM:= sum(j in JOBS) DUR(j)         ! Some (sufficiently) large value

! Precedence constraints
 forall(j in JOBS) finish >= start(j)+DUR(j) 
 forall(i,j in JOBS | exists(ARC(i,j)) ) start(i)+DUR(i) <= start(j)

! Disjunctions
 d:=1
 forall(i,j in JOBS | i<j and exists(DISJ(i,j)) ) do
  create(y(d))
  y(d) is_binary
  start(i)+DUR(i) <= start(j)+BIGM*y(d)
  start(j)+DUR(j) <= start(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
 writeln("Total completion time: ", getobjval)
 forall(j in JOBS)
  writeln(j, ": ", getsol(start(j)), "-", getsol(start(j))+DUR(j))

end-model
b3jobshop2.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b3jobshop2.mos
   ``````````````````
   Job shop production planning, 
   second, generic formulation.
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. Nov. 2017
*******************************************************!)

model "B-3 Job shop (2)"
 uses "mmxprs"
 
 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: dynamic array(range) of mpvar    ! Disjunction variables 
 end-declarations

 initializations from 'b3jobshop2.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) finish >= start(SEQ(j,NUMT(j)),j) + DUR(SEQ(j,NUMT(j)),j)
 forall(j in JOBS, m in 1..NUMT(j)-1) 
  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
  start(m,DISJ(m,i))+DUR(m,DISJ(m,i)) <= start(m,DISJ(m,j))+BIGM*y(d)
  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 'b3jobshop2.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

end-model
b4seq.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b4seq.mos
   ``````````````
   Sequencing jobs on a bottleneck machine
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002
*******************************************************!)

model "B-4 Sequencing"
 uses "mmxprs"

 forward procedure print_sol(obj:integer)
 
 declarations   
  NJ = 7                          ! Number of jobs
  JOBS=1..NJ

  REL: array(JOBS) of integer     ! Release dates of jobs
  DUR: array(JOBS) of integer     ! Durations of jobs
  DUE: array(JOBS) of integer     ! Due dates of jobs

  rank: array(JOBS,JOBS) of mpvar ! =1 if job j at position k
  start: array(JOBS) of mpvar     ! Start time of job at position k
  comp: array(JOBS) of mpvar      ! Completion time of job at position k
  late: array(JOBS) of mpvar      ! Lateness of job at position k
  finish: mpvar                   ! Completion time of the entire schedule
 end-declarations
 
 initializations from 'b4seq.dat'
  DUR REL DUE
 end-initializations

! One job per position
  forall(k in JOBS) sum(j in JOBS) rank(j,k) = 1

! One position per job 
  forall(j in JOBS) sum(k in JOBS) rank(j,k) = 1

! Sequence of jobs
  forall(k in 1..NJ-1)
   start(k+1) >= start(k) + sum(j in JOBS) DUR(j)*rank(j,k)

! Start times
  forall(k in JOBS) start(k) >= sum(j in JOBS) REL(j)*rank(j,k)

! Completion times
  forall(k in JOBS) comp(k) = start(k) + sum(j in JOBS) DUR(j)*rank(j,k)

 forall(j,k in JOBS) rank(j,k) is_binary 
 
! Objective function 1: minimize latest completion time
 forall(k in JOBS) finish >= comp(k)
 minimize(finish)
 print_sol(1)

! Objective function 2: minimize average completion time
 minimize(sum(k in JOBS) comp(k))
 print_sol(2)

! Objective function 3: minimize total tardiness
 forall(k in JOBS) late(k) >= comp(k) - sum(j in JOBS) DUE(j)*rank(j,k) 
 minimize(sum(k in JOBS) late(k))
 print_sol(3)

!-----------------------------------------------------------------

! Solution printing
 procedure print_sol(obj:integer)
  writeln("Objective ", obj, ": ", getobjval,
          if(obj>1, "  completion time: " + getsol(finish), "") ,
          if(obj<>2, "  average: " + getsol(sum(k in JOBS) comp(k)), ""),
          if(obj<>3, "  lateness: " + getsol(sum(k in JOBS) late(k)), ""))
  write("\t")
  forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) j*rank(j,k)),4))
  write("\nRel\t")
  forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) REL(j)*rank(j,k)),4))
  write("\nDur\t")
  forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) DUR(j)*rank(j,k)),4))
  write("\nStart\t")
  forall(k in JOBS) write(strfmt(getsol(start(k)),4))
  write("\nEnd\t")
  forall(k in JOBS) write(strfmt(getsol(comp(k)),4))
  write("\nDue\t")
  forall(k in JOBS) write(strfmt(getsol(sum(j in JOBS) DUE(j)*rank(j,k)),4))
  if(obj=3) then
   write("\nLate\t")
   forall(k in JOBS) write(strfmt(getsol(late(k)),4))
  end-if
  writeln
 end-procedure
 
end-model
b5paint.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b5paint.mos
   ````````````````
   Planning of paint production
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002
*******************************************************!)

model "B-5 Paint production"
 uses "mmxprs"

 declarations   
  NJ = 5                             ! Number of paint batches (=jobs)
  JOBS=1..NJ

  DUR: array(JOBS) of integer        ! Durations of jobs
  CLEAN: array(JOBS,JOBS) of integer ! Cleaning times between jobs

  succ: array(JOBS,JOBS) of mpvar    ! =1 if batch i is followed by batch j,
                                     ! =0 otherwise
  y: array(JOBS) of mpvar            ! Variables for excluding subtours
 end-declarations

 initializations from 'b5paint.dat'
  DUR CLEAN 
 end-initializations
 
! Objective: minimize the duration of a production cycle
 CycleTime:= sum(i,j in JOBS | i<>j) (DUR(i)+CLEAN(i,j))*succ(i,j)

! One successor and one predecessor per batch
 forall(i in JOBS) sum(j in JOBS | i<>j) succ(i,j) = 1
 forall(j in JOBS) sum(i in JOBS | i<>j) succ(i,j) = 1

! Exclude subtours
 forall(i in JOBS, j in 2..NJ | i<>j) y(j) >= y(i) + 1 - NJ * (1 - succ(i,j))

 forall(i,j in JOBS | i<>j) succ(i,j) is_binary
                                         
! Solve the problem
 minimize(CycleTime)
 
! Solution printing
 writeln("Minimum cycle time: ", getobjval)
 writeln("Sequence of batches:\nBatch Duration Cleaning")
 first:=1 
 repeat
  second:= integer(sum(j in JOBS | first<>j) j*getsol(succ(first,j)) )
  writeln("  ", first, strfmt(DUR(first),8), strfmt(CLEAN(first,second),9))
  first:=second
 until (second=1)   

end-model
b6linebal.mos
(!******************************************************
   Mosel Example Problems
   ======================

   file b6linebal.mos
   ``````````````````
   Assembly line balancing
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002
*******************************************************!)

model "B-6 Assembly line balancing"
 uses "mmxprs"

 declarations   
  MACH=1..4                             ! Set of workstations
  TASKS=1..12                           ! Set of tasks

  DUR: array(TASKS) of integer          ! Durations of tasks
  ARC: array(RA:range, 1..2) of integer ! Precedence relations between tasks

  process: array(TASKS,MACH) of mpvar   ! 1 if task on machine, 0 otherwise
  cycle: mpvar                          ! Duration of a production cycle
 end-declarations

 initializations from 'b6linebal.dat'
  DUR ARC 
 end-initializations

! One workstation per task 
 forall(i in TASKS) sum(m in MACH) process(i,m) = 1

! Sequence of tasks
 forall(a in RA) sum(m in MACH) m*process(ARC(a,1),m) <=
                  sum(m in MACH) m*process(ARC(a,2),m)

! Cycle time
 forall(m in MACH) sum(i in TASKS) DUR(i)*process(i,m) <= cycle

 forall(i in TASKS, m in MACH) process(i,m) is_binary

! Minimize the duration of a production cycle
 minimize(cycle)
 
! Solution printing
 writeln("Minimum cycle time: ", getobjval)
 forall(m in MACH) do
  write("Workstation ", m, ":")
  forall(i in TASKS)
   write(if(getsol(sum(k in MACH) k*process(i,k)) = m, " "+i, "")) 
  writeln(" (duration: ", getsol(sum(i in TASKS) DUR(i)*process(i,m)),")")
 end-do  
 
end-model
Parent Topic Mosel language: examples from the book 'Appliations of optimization with Xpress'

© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.