Implementation

The implementation of a model that starts submodels in the form of clones in order to work with shared data structures needs to contain the code for both, master and submodels, in a single file.

The main model logic with all declarations of entities and subroutines is shown below: the actual model is contained in the last if statement that decides which subroutines to execute depending on whether the model is run as the master or as a clone that solves a sequencing subproblem.

model "Job shop - Clone"
 uses "mmxprs", "mmjobs", "mmsystem"

 parameters
  DATAFILE = "mt10.dat"           ! Muth and Thompson 10x10 instance
  MACH = 1                        ! Subproblem identifier
  MAXTHRD = 2                     ! Max number of parallel threads for one inst.
 end-parameters

 declarations
 ! **** Shared data
  NBJOBS: shared integer                     ! Number of jobs
  NBRES: shared integer                      ! Number of resources
  JOBS: shared range                         ! Set of jobs
  TASKS: shared range                        ! Set of tasks (one per machine)
  TASKSM1: shared range                      ! Set of tasks without last
  RESOURCES: shared range                    ! Set of resources
  DUR: shared array(JOBS,TASKS) of integer          ! Durations of tasks
  RESIND: shared array(RESOURCES,JOBS) of integer   ! Task index per resource
  MAXDUR: shared array(RESOURCES) of integer
  BIGM: integer                              ! Used in formulation of master

  cutoff,starttime: real                     ! Temp. value used in master
  bbindex: integer                           ! Temp. value used in master

 ! **** Declarations for master model
  start: array(JOBS,TASKS) of mpvar          ! Start times of tasks
  comp: array(JOBS,TASKS) of mpvar           ! Completion times of tasks
  makespan: mpvar                            ! Schedule completion time
  y: dynamic array(RESOURCES,JOBS,JOBS) of mpvar  ! Disjunction variables

 ! **** Declarations for sequencing subproblems
  heursol: dynamic array(set of mpvar) of real
  rank: array(JOBS,JOBS) of mpvar            ! =1 if job j at position k
  jcomp,tstart: array(JOBS) of mpvar         ! Start time of job at position k

 ! **** Model and solution handling
  SeqMod: array(RESOURCES) of Model             ! Models
  NOSOL=2                                       ! "No sol found" event
  NEWSOL=3                                      ! "Solution found" event
  pos: shared array(RESOURCES,JOBS) of integer  ! Subproblem solutions
  Makespan: shared array(RESOURCES) of real     ! Subproblem makespan

 ! **** Subroutines
  procedure readdata
  procedure sequencemachine(m:integer)
  procedure disjunctiveconstraints(m:integer)
  procedure solvemaster
  procedure printsol
 end-declarations

!*********************************Model body*******************************

 if getparam("sharingstatus")<=0 then
   readdata
   solvemaster
   printsol
 else
   sequencemachine(MACH)
 end-if

end-model  

Jobshop master problem

The master model starts with the data input via the following subroutine readdata, all input data items are a marked as shared meaning that they are available within clones of the master model:

 procedure readdata
   initializations from DATAFILE
     NBJOBS NBRES
   end-initializations
   JOBS := 1..NBJOBS; finalize(JOBS)
   TASKS := 1..NBRES ; finalize(TASKS)
   TASKSM1 := 1..NBRES-1  ; finalize(TASKSM1)
   RESOURCES := 0..NBRES-1 ; finalize(RESOURCES)

   declarations
     taskUse: array(JOBS,TASKS) of integer   ! Resource use of tasks
   end-declarations

   initializations from DATAFILE
     taskUse  DUR as "taskDuration"
   end-initializations

   forall(m in RESOURCES,j in JOBS,t in TASKS | taskUse(j,t) = m) RESIND(m,j):=t

   BIGM:=sum(j in JOBS,t in TASKS) DUR(j,t)    ! Some (sufficiently) large value
   forall(m in RESOURCES) MAXDUR(m):=sum(j in JOBS) DUR(j,RESIND(m,j))
 end-procedure

The implementation of the jobshop problem is contained in the following subroutine that defines the problem, creates and runs the concurrent sequencing subproblems as clones, and transforms the solutions returned by these into the required from for adding them as (partial) start solutions into the full problem.

 procedure solvemaster
  ! Precedence constraints between last task of every job and makespan
   forall(j in JOBS) makespan >= start(j,NBRES) + DUR(j,NBRES)

  ! Precedence constraints between the tasks of every job
   forall(j in JOBS,t in TASKSM1)
     start(j,t) + DUR(j,t) <= start(j,t+1)

  ! Disjunctions
   forall(r in RESOURCES) disjunctiveconstraints(r)

  ! Linking start and completion times
   forall(j in JOBS,t in TASKS) start(j,t)+DUR(j,t) = comp(j,t)

  ! Bound on latest completion time
   makespan <= BIGM

   starttime:=gettime

  ! Solve the single machine sequencing problems
   forall(m in RESOURCES) do
     load(SeqMod(m))                      ! Clone the current model
     SeqMod(m).uid:= m
     setworkdir(SeqMod(m), ".")
     run(SeqMod(m), "MACH="+m +",MAXTHRD="+1)
   end-do
   tct:=0
   while (tct<NBRES) do
     wait                                 ! Wait for the next event
     Msg:= getnextevent                   ! Get the event
     mid:= Msg.fromuid                    ! Get model number of sender
     if getclass(Msg)=NEWSOL then         ! Get the event class
       if Makespan(mid)>cutoff then
         cutoff:= Makespan(mid);
         bbindex:=mid
       end-if
       writeln_("*** (", gettime-starttime, "s) Machine ", mid, ": ", Makespan(mid))

       forall(i,j in JOBS | i<j ) heursol(y(mid,i,j)):= if(pos(mid,i)<pos(mid,j), 0, 1)
       loadprob(makespan)                 ! Make sure problem is loaded
       id:="mach"+mid
       addmipsol(id,heursol)              ! Load the heuristic solution
       writeln_("Loaded solution Id: ", id)
       setcallback(XPRS_CB_SOLNOTIFY, "solnotify")
       delcell(heursol)                   ! Delete saved solution values
     elif getclass(Msg)=NOSOL then
       writeln_("Subproblem ", mid, " has no solution. Stopping")
       exit(1)
     else
       tct+=1
       unload(SeqMod(mid))                ! Delete subproblem
     end-if
   end-do

   writeln_("(", gettime-starttime, "s) Best lower bound: ", cutoff)

  ! Re-inforce use of user solutions by local search MIP heuristics
   setparam("XPRS_USERSOLHEURISTIC", 3)

  ! Set a time limit
   setparam("XPRS_MAXTIME", 5)

  ! Solve the problem: minimize latest completion time
   minimize(makespan)
 end-procedure

! **** Callback reporting the status of loaded solutions ****
 public procedure solnotify(id:string, status:integer)
   writeln_("Optimiser loaded solution ", id, " status=", status)
 end-procedure

The subroutine disjunctiveconstraints defines the disjunctions between tasks on the same resource—by moving the definition of these constraints into a separate subroutine it becomes easy to experiment with alternative formulations for these constraints (such as by using indicator constraints in place of the big-M construct employed in the version shown here).

 procedure disjunctiveconstraints(m:integer)
   forall(i,j in JOBS | i<j) do
     create(y(m,i,j))
     y(m,i,j) is_binary               !=1 if i>>j, =0 if i<<j

     start(i,RESIND(m,i))+DUR(i,RESIND(m,i)) <=
       start(j,RESIND(m,j))+BIGM*y(m,i,j)
     start(j,RESIND(m,j))+DUR(j,RESIND(m,j)) <=
       start(i,RESIND(m,i))+BIGM*(1-y(m,i,j))
    end-do
 end-procedure   

The implementation of the master model is completed with some solution display at the end of the solving of the full problem:

 procedure printsol
   writeln_("(", gettime-starttime, "s) Total completion time: ", getobjval)
   forall(j in JOBS) write(strfmt(j,8))
   writeln
   forall(m in RESOURCES) do
     write(strfmt((m+1),-3))
     forall(j in JOBS)
       if(DUR(j,RESIND(m,j))>0) then
         write(formattext("%4d-%3d", round(getsol(start(j,RESIND(m,j)))),
              round(getsol(start(j,RESIND(m,j)))+DUR(j,RESIND(m,j)))))
       else
         write(strfmt(" ",6))
       end-if
     writeln
   end-do
 end-procedure 

Sequencing subproblem

The implementation of the sequencing subproblem is provided by the following subroutine that terminates by sending an event that notifies the master problem of the solving status (indicating whether a subproblem solution is available):

 procedure sequencemachine(m:integer)
  ! 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..NBJOBS-1)
     tstart(k+1) >=
       tstart(k) + sum(j in JOBS) DUR(j,RESIND(m,j))*rank(j,k)

  ! Start times (release date = min total duration for preceding tasks)
   forall(j in JOBS) REL(j):= sum(t in 1..RESIND(m,j)-1) DUR(j,t)
   forall(j in JOBS) DURSUCC(j):= sum(t in RESIND(m,j)+1..NBRES) DUR(j,t)

   forall(k in JOBS) tstart(k) >= sum(j in JOBS) REL(j)*rank(j,k)

  ! Completion times
   forall(k in JOBS) jcomp(k) =
     tstart(k) + sum(j in JOBS) (DUR(j,RESIND(m,j))+DURSUCC(j))*rank(j,k)

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

  ! Objective function: minimize latest completion time
   forall(k in JOBS) makespan >= jcomp(k)

  ! Solve the problem
   minimize(makespan)

  ! Solution reporting
   if getprobstat=XPRS_OPT then
    ! writeln_("*** Machine ", m, ": ", getobjval)
     forall(j in JOBS) pos(m,j):= round(sum(k in JOBS) k*rank(j,k).sol)
     Makespan(m):=getobjval

    ! Send "solution found" signal
     send(NEWSOL, getobjval)
   else
     send(NOSOL, 0)
   end-if
 end-procedure