occurrence: Sugar production

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

The harvest of cane sugar in Australia is highly mechanized. The sugar cane is immediately transported to a sugarhouse in wagons that run on a network of small rail tracks. The sugar content of a wagonload depends on the field it has been harvested from and on the maturity of the sugar cane. Once harvested, the sugar content decreases rapidly through fermentation and the wagonload will entirely lose its value after a certain time. At this moment, eleven wagons loaded with the same quantity have arrived at the sugarhouse. They have been examined to find out the hourly loss and the remaining life span (in hours) of every wagon, these data are summarized in the following table.

Every lot may be processed by any of the three, fully equivalent production lines of the sugarhouse. The processing of a lot takes two hours. It must be finished at the latest at the end of the life span of the wagonload. The manager of the sugarhouse wishes to determine a production schedule for the currently available lots that minimizes the total loss of sugar.

Model formulation

Let WAGONS = {1,...,NW} be the set of wagons, NL the number of production lines and DUR the duration of the production process for every lot. The hourly loss for every wagon w is given by LOSS_w and its life span by LIFE_w. We observe that, in an optimal solution, the production lines need to work without any break—otherwise we could reduce the loss in sugar by advancing the start of the lot that follows the break. This means that the completion time of every lot is of the form s · DUR, with s > 0 and is an integer. The maximum value of s is the number of time slots (of length DUR) that the sugarhouse will work, namely NS = ceil(NW/NL), where ceil stands for `rounded to the next largest integer'. If NW/NL is an integer, every line will process exactly NS lots. Otherwise, some lines will process NS-1 lots, but at least one line processes NS lots. In all cases, the length of the optimal schedule is NS · DUR hours. We call SLOTS = {1,...,NS} the set of time slots.

Every lot needs to be assigned to a time slot. We define variables process_w for the time slot assigned to wagon w and variables loss_w for the loss incurred by this wagonload. Every time slot may take up to NL lots because there are NL parallel lines; therefore, we limit the number of occurrences of time slot values among the process_w variables (this constraint relation is often called cardinality constraint):

The loss of sugar per wagonload w and time slot s is COST_ws = s · DUR · LOSS_w. Let variables loss_w denote the loss incurred by wagon load w:

The objective function (total loss of sugar) is then given as the sum of all losses:

Implementation

The following model is the Mosel implementation of this problem. It uses the function ceil to calculate the maximum number of time slots.

The constraints on the processing variables are expressed by occurrence relations and the losses are obtained via element constraints. The branching strategy uses the variable selection criterion KALIS_SMALLEST_MAX, that is, choosing the variable with the smallest upper bound.

model "A-4 Cane sugar production (CP)"
 uses "kalis"

 declarations
  NW = 11                            ! Number of wagon loads of sugar
  NL = 3                             ! Number of production lines
  WAGONS = 1..NW
  NS = ceil(NW/NL)
  SLOTS = 1..NS                      ! Time slots for production

  LOSS: array(WAGONS) of integer     ! Loss in kg/hour
  LIFE: array(WAGONS) of integer     ! Remaining time per lot (in hours)
  DUR: integer                       ! Duration of the production (in hours)
  COST: array(SLOTS) of integer      ! Cost per wagon

  loss: array(WAGONS) of cpvar       ! Loss per wagon
  process: array(WAGONS) of cpvar    ! Time slots for wagon loads

  totalLoss: cpvar                   ! Objective variable
 end-declarations

 initializations from 'Data/a4sugar.dat'
  LOSS LIFE DUR
 end-initializations

 forall(w in WAGONS) setdomain(process(w), 1, NS)

! Wagon loads per time slot
 forall(s in SLOTS) occurrence(s, process) <= NL

! Limit on raw product life
 forall(w in WAGONS) process(w) <= floor(LIFE(w)/DUR)

! Objective function: total loss
 forall(w in WAGONS) do
  forall(s in SLOTS) COST(s):= s*DUR*LOSS(w)
  loss(w) = element(COST, process(w))
 end-do
 totalLoss = sum(w in WAGONS) loss(w)

 cp_set_branching(assign_var(KALIS_SMALLEST_MAX, KALIS_MIN_TO_MAX, process))

! Solve the problem
 if not (cp_minimize(totalLoss)) then
  writeln("No solution found")
  exit(0)
 end-if

! Solution printing
 writeln("Total loss: ", getsol(totalLoss))
 forall(s in SLOTS) do
  write("Slot ", s, ": ")
  forall(w in WAGONS)
   if(getsol(process(w))=s) then
    write("wagon ", strfmt(w,2), strfmt(" (" + s*DUR*LOSS(w) + ")  ", 8))
   end-if
  writeln
 end-do

end-model

An alternative formulation of the constraints on the processing variables is to replace them by a single distribute relation, indicating for every time slot the minimum and maximum number (MINUSE_s=0 and MAXUSE_s=NL) of production lines that may be used.

 forall(s in SLOTS) MAXUSE(s):= NL
 distribute(process, SLOTS, MINUSE, MAXUSE)

Yet another formulation of this problem is possible with Xpress Kalis, namely interpreting it as a cumulative scheduling problem (see Section Cumulative scheduling: discrete resources), where the wagon loads are represented by tasks of unit duration, scheduled on a discrete resource with a capacity corresponding to the number of production lines.

Results

We obtain a total loss of 1620 kg of sugar. The corresponding schedule of lots is shown in the following Table Optimal schedule for the cane sugar lots (there are several equivalent solutions).