cycle: Paint production

In this section we work once more with the paint production problem from Section implies: Paint production. The objective of this problem is to determine a production cycle of minimal length for a given set of jobs with sequence-dependent cleaning times between every pair of jobs.

Model formulation

The problem formulation in Section implies: Paint production uses 'all-different' constraints to ensure that every job occurs once only, calculates the duration of cleaning times with 'element' constraints, and introduces auxiliary variables and constraints to prevent subcycles in the production sequence. All these constraints can be expressed by a single constraint relation, the 'cycle' constraint.

Let JOBS = {1,...,NJ} be the set of batches to produce, DUR_j the processing time for batch j, and CLEAN_ij the cleaning time between the consecutive batches i and j. As before we define decision variables succ_j taking their values in JOBS, to indicate the successor of every job. The complete model formulation is the following,

where 'cycle' stands for the relation 'sequence into a single cycle without subcycles or repetitions'. The variable cleantime equals the total duration of the cycle.

Implementation

The Mosel model using the cycle constraint looks as follows.

model "B-5 Paint production (CP)"
 uses "kalis"

 setparam("KALIS_DEFAULT_LB", 0)

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

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

  succ: array(JOBS) of cpvar         ! Successor of a batch
  cleanTime,cycleTime: cpvar         ! Durations of cleaning / complete cycle
 end-declarations

 initializations from 'Data/b5paint.dat'
  DUR CLEAN
 end-initializations

 forall(j in JOBS) do
  0 <= succ(j); succ(j) <= NJ-1; succ(j) <> j
 end-do

! Assign values to 'succ' variables as to obtain a single cycle
! 'cleanTime' is the sum of the cleaning times
 cycle(succ, cleanTime, CLEAN)

! Objective: minimize the duration of a production cycle
 cycleTime = cleanTime +sum(j in JOBS) DUR(j)

! Solve the problem
 if not cp_minimize(cycleTime) then
  writeln("Problem is infeasible")
  exit(1)
 end-if
 cp_show_stats

! Solution printing
 writeln("Minimum cycle time: ", getsol(cycleTime))
 writeln("Sequence of batches:\nBatch Duration Cleaning")
 first:=1
 repeat
  writeln("  ", first, strfmt(DUR(first),8),
                strfmt(CLEAN(first,getsol(succ(first))),9) )
  first:=getsol(succ(first))
 until (first=1)

end-model

Notice that we have renumbered the tasks, starting the index range with 0, to conform with the input format expected by the cycle constraint.

Results

The optimal solution to this problem has a minimum cycle time of 243 minutes, resulting from 202 minutes of (incompressible) processing time and 41 minutes of cleaning.

The problem statistics produced by Xpress Kalis for a model run reveal that the 'cycle' version of this model is the most efficient way of representing and solving the problem: it takes fewer nodes and a shorter execution time than the two versions of Section implies: Paint production.