element: Sequencing jobs on a single machine

The problem described in this section is taken from Section 7.4 `Sequencing jobs on a bottleneck machine' of the book `Applications of optimization with Xpress-MP'

The aim of this problem is to provide a model that may be used with different objective functions for scheduling operations on a single (bottleneck) machine. We shall see here how to minimize the total processing time, the average processing time, and the total tardiness.

A set of tasks (or jobs) is to be processed on a single machine. The execution of tasks is non-preemptive (that is, an operation may not be interrupted before its completion). For every task i its release date, duration, and due date are given in Table Task time windows and durations.

What is the optimal value for each of the objectives: minimizing the total duration of the schedule (makespan), the mean processing time or the total tardiness (that is, the amount of time by which the completion of jobs exceeds their respective due dates)?

Model formulation 1

We are going to present two alternative model formulations. The first is closer to the Mathematical Programming formulation in `Applications of optimization with Xpress-MP'. The second uses disjunctive constraints and branching on these. In both model formulations we are going deal with the different objective functions in sequence, but the body of the models will remain the same.

To represent the sequence of jobs we introduce variables rank_k (k ∈ JOBS = {1,...,NJ}) that take as value the number of the job in position (rank) k. Every job j takes a single position. This constraint can be represented by an all-different on the rank_k variables:

The processing time dur_k for the job in position k is given by DUR_rankk (where DUR_j denotes the duration given in the table in the previous section). Similarly, the release time rel_k is given by REL_rankk (where REL_j denotes the given release date):

If start_k is the start time of the job at position k, this value must be at least as great as the release date of the job assigned to this position. The completion time comp_k of this job is the sum of its start time plus its duration:

Another constraint is needed to specify that two jobs cannot be processed simultaneously. The job in position k+1 must start after the job in position k has finished, hence the following constraints:

Objective 1: The first objective is to minimize the makespan (completion time of the schedule), or, equivalently, to minimize the completion time of the last job (job with rank NJ). The complete model is then given by the following (where MAXTIME is a sufficiently large value, such as the sum of all release dates and all durations):

Objective 2: For minimizing the average processing time, we introduce an additional variable totComp representing the sum of the completion times of all jobs. We add the following constraint to the problem to calculate totComp:

The new objective consists of minimizing the average processing time, or equivalently, minimizing the sum of the job completion times:

Objective 3: If we now aim to minimize the total tardiness, we again introduce new variables—this time to measure the amount of time that jobs finish after their due date. We write late_k for the variable that corresponds to the tardiness of the job with rank k. Its value is the difference between the completion time of a job j and its due date DUE_j. If the job finishes before its due date, the value must be zero. We thus obtain the following constraints:

For the formulation of the new objective function we introduce the variable totLate representing the total tardiness of all jobs. The objective now is to minimize the value of this variable:

Implementation of model 1

The Mosel implementation below solves the same problem three times, each time with a different objective, and prints the resulting solutions by calling the procedures print_sol and print_sol3.

model "B-4 Sequencing (CP)"
 uses "kalis"

 forward procedure print_sol
 forward procedure print_sol3

 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) of cpvar      ! Number of job at position k
  start: array(JOBS) of cpvar     ! Start time of job at position k
  dur: array(JOBS) of cpvar       ! Duration of job at position k
  comp: array(JOBS) of cpvar      ! Completion time of job at position k
  rel: array(JOBS) of cpvar       ! Release date of job at position k
 end-declarations

 initializations from 'Data/b4seq.dat'
  DUR REL DUE
 end-initializations

 MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)
 MINDUR:= min(j in JOBS) DUR(j); MAXDUR:= max(j in JOBS) DUR(j)
 MINREL:= min(j in JOBS) REL(j); MAXREL:= max(j in JOBS) REL(j)

 forall(j in JOBS) do
  1 <= rank(j); rank(j) <= NJ
  0 <= start(j); start(j) <= MAXTIME
  MINDUR <= dur(j); dur(j) <= MAXDUR
  0 <= comp(j); comp(j) <= MAXTIME
  MINREL <= rel(j); rel(j) <= MAXREL
 end-do

! One posistion per job
 all_different(rank)

! Duration of job at position k
 forall(k in JOBS) dur(k) = element(DUR, rank(k))

! Release date of job at position k
 forall(k in JOBS) rel(k) = element(REL, rank(k))

! Sequence of jobs
 forall(k in 1..NJ-1) start(k+1) >= start(k) + dur(k)

! Start times
 forall(k in JOBS) start(k) >= rel(k)

! Completion times
 forall(k in JOBS) comp(k) = start(k) + dur(k)

! Set the branching strategy
 cp_set_branching(split_domain(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX))

!**** Objective function 1: minimize latest completion time ****
 if cp_minimize(comp(NJ)) then
  print_sol
 end-if


!**** Objective function 2: minimize average completion time ****
 declarations
  totComp: cpvar
 end-declarations

 totComp = sum(k in JOBS) comp(k)

 if cp_minimize(totComp) then
  print_sol
 end-if


!**** Objective function 3: minimize total tardiness ****
 declarations
  late: array(JOBS) of cpvar      ! Lateness of job at position k
  due: array(JOBS) of cpvar       ! Due date of job at position k
  totLate: cpvar
 end-declarations

 MINDUE:= min(k in JOBS) DUE(k); MAXDUE:= max(k in JOBS) DUE(k)

 forall(k in JOBS) do
  MINDUE <= due(k); due(k) <= MAXDUE
  0 <= late(k); late(k) <= MAXTIME
 end-do

! Due date of job at position k
 forall(k in JOBS) due(k) = element(DUE, rank(k))

! Late jobs: completion time exceeds the due date
 forall(k in JOBS) late(k) >= comp(k) - due(k)

 totLate = sum(k in JOBS) late(k)

 if cp_minimize(totLate) then
  writeln("Tardiness: ", getsol(totLate))
  print_sol
  print_sol3
 end-if

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

! Solution printing
 procedure print_sol
  writeln("Completion time: ", getsol(comp(NJ)) ,
          "  average: ", getsol(sum(k in JOBS) comp(k)))
  write("\t")
  forall(k in JOBS) write(strfmt(getsol(rank(k)),4))
  write("\nRel\t")
  forall(k in JOBS) write(strfmt(getsol(rel(k)),4))
  write("\nDur\t")
  forall(k in JOBS) write(strfmt(getsol(dur(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))
  writeln
 end-procedure

 procedure print_sol3
  write("Due\t")
  forall(k in JOBS) write(strfmt(getsol(due(k)),4))
  write("\nLate\t")
  forall(k in JOBS) write(strfmt(getsol(late(k)),4))
  writeln
 end-procedure

end-model

NB: The reader may have been wondering why we did not use the more obvious pair start-end for naming the variables in this example: end is a keyword of the Mosel language (see the list of reserved words in the Mosel language reference manual), which means that neither end nor END may be redefined by a Mosel program. It is possible though, to use versions combining lower and upper case letters, like End, but to prevent any possible confusion we do not recommend their use.

Results

The minimum makespan of the schedule is 31, the minimum sum of completion times is 103 (which gives an average of 103/7=14.71). A schedule with this objective value is 5→ 4→ 1→ 7→ 6→ 2→ 3. If we compare the completion times with the due dates we see that jobs 1, 2, 3, and 6 finish late (with a total tardiness of 21). The minimum tardiness is 18. A schedule with this tardiness is 5→ 1→ 4→ 6→ 2→ 7→ 3 where jobs 4 and 7 finish one time unit late and job 3 is late by 16 time units, and it terminates at time 31 instead of being ready at its due date, time 15. This schedule has an average completion time of 15.71.

Alternative formulation using disjunctions

Our second model formulation is possibly a more straightforward way of representing the problem. It introduces disjunctive constraints and branching on these.

Every job is now represented by its starting time, variables start_j (j ∈ JOBS = {1,...,NJ}) that take their values in {REL_j,...,MAXTIME} (where MAXTIME is a sufficiently large value, such as the sum of all release dates and all durations, and REL_j the release date of job j). We state the disjunctions as a single disjunctive relation on the start times and durations of all jobs.

This constraint replaces the pair-wise disjunctions

for all pairs of jobs i < j ∈ JOBS.

The processing time dur_k for the job in position k is given by DUR_rankk (where DUR_j denotes the duration given in the table in the previous section). Similarly, its release time rel_k is given by REL_rankk (where REL_j denotes the given release date).

The completion time comp_j of a job j is the sum of its start time plus its duration DUR_j.

Objective 1: The first objective is to minimize the makespan (completion time of the schedule) or, equivalently, to minimize the completion time finish of the last job. The complete model is then given by the following (where MAXTIME is a sufficiently large value, such as the sum of all release dates and all durations):

Objective 2: The formulation of the second objective (minimizing the average processing time or, equivalently, minimizing the sum of the job completion times) remains unchanged from the first model—we introduce an additional variable totComp representing the sum of the completion times of all jobs.

Objective 3: To formulate the objective of minimizing the total tardiness, we introduce new variables late_j to measure the amount of time that a job finishes after its due date. The value of these variables corresponds to the difference between the completion time of a job j and its due date DUE_j. If the job finishes before its due date, the value must be zero. The objective now is to minimize the sum of these tardiness variables:

Implementation of model 2

As with model 1, the Mosel implementation below solves the same problem three times, each time with a different objective, and prints the resulting solutions by calling the procedures print_sol and print_sol3.

model "B-4 Sequencing (CP)"
 uses "kalis"

 forward procedure print_sol
 forward procedure print_sol3

 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
  DURS: array(set of cpvar) of integer  ! Dur.s indexed by start variables

  start: array(JOBS) of cpvar     ! Start time of jobs
  comp: array(JOBS) of cpvar      ! Completion time of jobs
  finish: cpvar                   ! Completion time of the entire schedule
  Disj: set of cpctr              ! Disjunction constraints
  Strategy: array(range) of cpbranching  ! Branching strategy
 end-declarations

 initializations from 'Data/b4seq.dat'
  DUR REL DUE
 end-initializations

 MAXTIME:= max(j in JOBS) REL(j) + sum(j in JOBS) DUR(j)

 forall(j in JOBS) do
  0 <= start(j); start(j) <= MAXTIME
  0 <= comp(j); comp(j) <= MAXTIME
 end-do

! Disjunctions between jobs
 forall(j in JOBS) DURS(start(j)):= DUR(j)
 disjunctive(union(j in JOBS) {start(j)}, DURS, Disj, 1)

! Start times
 forall(j in JOBS) start(j) >= REL(j)

! Completion times
 forall(j in JOBS) comp(j) = start(j) + DUR(j)

!**** Objective function 1: minimize latest completion time ****
 finish = maximum(comp)

 Strategy(1):= settle_disjunction(Disj)
 Strategy(2):= split_domain(KALIS_LARGEST_MAX, KALIS_MIN_TO_MAX)
 cp_set_branching(Strategy)

 if cp_minimize(finish) then
  print_sol
 end-if


!**** Objective function 2: minimize average completion time ****
 declarations
  totComp: cpvar
 end-declarations

 totComp = sum(k in JOBS) comp(k)

 if cp_minimize(totComp) then
  print_sol
 end-if


!**** Objective function 3: minimize total tardiness ****
 declarations
  late: array(JOBS) of cpvar      ! Lateness of jobs
  totLate: cpvar
 end-declarations

 forall(k in JOBS) do
  0 <= late(k); late(k) <= MAXTIME
 end-do

! Late jobs: completion time exceeds the due date
 forall(j in JOBS) late(j) >= comp(j) - DUE(j)

 totLate = sum(k in JOBS) late(k)
 if cp_minimize(totLate) then
  writeln("Tardiness: ", getsol(totLate))
  print_sol
  print_sol3
 end-if

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

! Solution printing
 procedure print_sol
  writeln("Completion time: ", getsol(finish) ,
          "  average: ", getsol(sum(j in JOBS) comp(j)))
  write("Rel\t")
  forall(j in JOBS) write(strfmt(REL(j),4))
  write("\nDur\t")
  forall(j in JOBS) write(strfmt(DUR(j),4))
  write("\nStart\t")
  forall(j in JOBS) write(strfmt(getsol(start(j)),4))
  write("\nEnd\t")
  forall(j in JOBS) write(strfmt(getsol(comp(j)),4))
  writeln
 end-procedure

 procedure print_sol3
  write("Due\t")
  forall(j in JOBS) write(strfmt(DUE(j),4))
  write("\nLate\t")
  forall(j in JOBS) write(strfmt(getsol(late(j)),4))
  writeln
 end-procedure

end-model

This implementation introduces a new branching scheme, namely settle_disjunction. As opposed to the branching strategies we have seen so far this scheme defines a branching strategy over constraints, and not over variables. With this scheme a node is created by choosing a constraint from the given set and the branches from the node are obtained by adding one of the mutually exclusive constraints forming this disjunctive constraint to the constraint system.

NB: the disjunctive constraint of Xpress Kalis establishes pair-wise inequalities between the processing times of tasks. However, the definition of disjunctive constraints is not restricted to this case: a disjunction may have more than two components, and involve constraints of any type, including other logic relations obtained by combining constraints with and or or.