implies: Paint production

The problem description in this section is taken from Section 7.5 `Paint production' of the book `Applications of optimization with Xpress-MP'

As a part of its weekly production a paint company produces five batches of paints, always the same, for some big clients who have a stable demand. Every paint batch is produced in a single production process, all in the same blender that needs to be cleaned between every two batches. The durations of blending paint batches 1 to 5 are respectively 40, 35, 45, 32, and 50 minutes. The cleaning times depend on the colors and the paint types. For example, a long cleaning period is required if an oil-based paint is produced after a water-based paint, or to produce white paint after a dark color. The times are given in minutes in the following Table Matrix of cleaning times CLEAN where CLEAN_ij denotes the cleaning time between batch i and batch j.

Since the company also has other activities, it wishes to deal with this weekly production in the shortest possible time (blending and cleaning). Which is the corresponding order of paint batches? The order will be applied every week, so the cleaning time between the last batch of one week and the first of the following week needs to be counted for the total duration of cleaning.

Formulation of model 1

As for the problem in Section element: Sequencing jobs on a single machine we are going to present two alternative model formulations. The first one is closer to the Mathematical Programming formulation in `Applications of optimization with Xpress-MP', the second uses a two-dimensional element 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. We introduce decision variables succ_j taking their values in JOBS, to indicate the successor of every job, and variables clean_j for the duration of the cleaning after every job. The cleaning time after every job is obtained by indexing CLEAN_ij with the value of succ_j. We thus have the following problem formulation.

The objective function sums up the processing and cleaning times of all batches. The last (all-different) constraint guarantees that every batch occurs exactly once in the production sequence.

Unfortunately, this model does not guarantee that the solution forms a single cycle. Solving it indeed results in a total duration of 239 with an invalid solution that contains two sub-cycles 1 → 3 → 2 → 1 and 4 → 5 → 4. A first possibility is to add a disjunction excluding this solution to our model and re-solve it iteratively until we reach a solution without sub-cycles.

However, this procedure is likely to become impractical with larger data sets since it may potentially introduce an extremely large number of disjunctions. We therefore choose a different, a-priori formulation of the sub-cycle elimination constraints with a variable y_j per batch and NJ · (NJ-1) implication constraints.

The variables y_j correspond to the position of job j in the production cycle. With these constraints, job 1 always takes the first position.

Implementation of model 1

The Mosel implementation of the model formulated in the previous section is quite straightforward. The sub-cycle elimination constraints are implemented as logic relations with implies (a stronger formulation of these constraints is obtained by replacing the implications by equivalences, using equiv).

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

 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
  CB: array(JOBS) of integer         ! Cleaning times after a batch

  succ: array(JOBS) of cpvar         ! Successor of a batch
  clean: array(JOBS) of cpvar        ! Cleaning time after batches
  y: array(JOBS) of cpvar            ! Variables for excluding subtours
  cycleTime: cpvar                   ! Objective variable
 end-declarations

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

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

! Cleaning time after every batch
 forall(j in JOBS) do
  forall(i in JOBS) CB(i):= CLEAN(j,i)
  clean(j) = element(CB, succ(j))
 end-do

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

! One successor and one predecessor per batch
 all_different(succ)

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

! 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(getsol(clean(first)),9))
  first:=getsol(succ(first))
 until (first=1)

end-model

Formulation of model 2

We may choose to implement the paint production problem using rank variables similarly to the sequencing model in Section Model formulation 1.

As before, 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. We introduce decision variables rank_k taking their values in JOBS, for the number of the job in position k. Variables clean_k (k ∈ JOBS) now denote the duration of the k^th cleaning time. This duration is obtained by indexing CLEAN_ij with the values of two consecutive rank_k variables. We thus have the following problem formulation.

As in model 1, the objective function sums up the processing and cleaning times of all batches. Although not strictly necessary from the mathematical point of view, we use different sum indices for durations and cleaning times to show the difference between summing over jobs or job positions. We now have an all-different constraint over the rank variables to guarantee that every batch occurs exactly once in the production sequence.

Implementation of model 2

The implementation of the second model uses the 2-dimensional version of the element constraint in Xpress Kalis.

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

 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

  rank: array(JOBS) of cpvar         ! Number of job in position k
  clean: array(JOBS) of cpvar        ! Cleaning time after batches
  cycleTime: cpvar                   ! Objective variable
 end-declarations

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

 forall(k in JOBS) setdomain(rank(k), JOBS)

! Cleaning time after every batch
 forall(k in JOBS)
  if k<NJ then
   element(CLEAN, rank(k), rank(k+1)) = clean(k)
  else
   element(CLEAN, rank(k), rank(1)) = clean(k)
  end-if

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

! One position for every job
 all_different(rank)

! 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")
 forall(k in JOBS)
  writeln("  ", getsol(rank(k)), strfmt(DUR(getsol(rank(k))),8),
          strfmt(getsol(clean(k)),9))

end-model

Results

The minimum cycle time for this problem is 243 minutes which is achieved with the following sequence of batches: 1 → 4 → 3 → 5 → 2 → 1. This time includes 202 minutes of (incompressible) processing time and 41 minutes of cleaning.

When comparing the problem statistics produced by Xpress Kalis for this problem we see that the second model is a weaker formulation resulting in a considerably longer enumeration (using the default strategies).