Paint production 2

In this section we work once more with the paint production problem. 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 11.5 uses KAllDifferent constraints to ensure that every job occurs once only, calculates the duration of cleaning times with KElement 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 KCycle constraint. Let JOBS = \{1, ..., NJ\} be the set of batches to produce, DUR_j the processing time for batch j, and CLEAN_{i,j} 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,

&\text{minimize } \sum_{j \in JOBS} DUR_j + cleantime\\
&\forall j \in JOBS : succ_j \in JOBS \backslash \{ j \}\\
&cleantime = cycle((succ_j)_{j \in JOBS}, (CLEAN_{i,j})_{i,j \in JOBS \times JOBS})\\

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 model using the KCycle constraint looks as follows.

// Number of paint batches (=jobs)
int NJ = 5;
// Durations of jobs
int DUR[]  = {40, 35, 45 ,32 ,50};

// Cleaning times between jobs
KIntMatrix CLEAN(5,5,0,"CLEAN");

CLEAN[0][0] = 0;CLEAN[1][0] = 11;CLEAN[2][0] = 7;CLEAN[3][0] = 13;CLEAN[4][0] = 11;
CLEAN[0][1] = 5;CLEAN[1][1] = 0;CLEAN[2][1] = 13;CLEAN[3][1] = 15;CLEAN[4][1] = 15;
CLEAN[0][2] = 13;CLEAN[1][2] = 15;CLEAN[2][2] = 0;CLEAN[3][2] = 23;CLEAN[4][2] = 11;
CLEAN[0][3] = 9;CLEAN[1][3] = 13;CLEAN[2][3] = 5;CLEAN[3][3] = 0;CLEAN[4][3] = 3;
CLEAN[0][4] = 3;CLEAN[1][4] = 7;CLEAN[2][4] = 7;CLEAN[3][4] = 7;CLEAN[4][4] = 0;

// Cleaning times after a batch
KIntArray CB;

// Successor of a batch
KIntVarArray succ;
// Objective variable
KIntVar * cycleTime;
// Objective variable
KIntVar * cleanTime;


// Creation of the problem in this session
KProblem problem(session,"B-5 Paint production");

// variables creation
char name[80];
int j,i;
for (j=0;j<NJ;j++) {
    sprintf(name,"succ(%i)",j);
    succ += (* new KIntVar( problem,name,0,NJ-1) );
    succ[j].remVal(j);
}

cleanTime = new KIntVar(problem,"cleanTime",0,1000);
// Assign values to 'succ' variables as to obtain a single cycle
// 'cleanTime' is the sum of the cleaning times
problem.post(new KCycle(&succ, NULL,cleanTime, &CLEAN) );

// objective variable creation
cycleTime = new KIntVar(problem,"cycleTime",0,1000);

// Objective: minimize the duration of a production cycle
KLinTerm cycleTerm;
for (j=0;j<NJ;j++) {
    cycleTerm = cycleTerm + DUR[j];
}
problem.post(cycleTerm + *cleanTime == *cycleTime);

// propagating problem
if (problem.propagate()) {
    printf("Problem is infeasible\n");
    exit(1);
}

// Solve the problem
// creation of the solver
KSolver solver(problem);

// setting objective and sense of optimization
problem.setSense(KProblem::Minimize);
problem.setObjective(*cycleTime);

int result = solver.optimize();
// solution printing
KSolution * sol = &problem.getSolution();
// print solution resume
sol->printResume();

// Solution printing
printf("Minimum cycle time: %i\n", sol->getValue(*cycleTime));
printf("Sequence of batches:\nBatch Duration Cleaning\n");
int first=0;
do {
    printf("%i\t%i\t%i\n", first, DUR[first],CLEAN[first][sol->getValue(succ[first])]);
    first = sol->getValue(succ[first]);
} while (first!=0);

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 Artelys 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 previous versions of the model.