# 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 be the set of batches to produce, the processing time for batch , and the cleaning time between the consecutive batches and . As before we define decision variables taking their values in , 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 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);
```

```
from kalis import *
### Data
# Number of paint batches (=jobs)
nb_jobs = 5
# Durations of jobs
jobs_durations = [40, 35, 45, 32, 50]
# Cleaning times between jobs
jobs_cleaning_times = [[0, 11, 7, 13, 11],
[5, 0, 13, 15, 15],
[13, 15, 0, 23, 11],
[9, 13, 5, 0, 3],
[3, 7, 7, 7, 0]]
### Creation of the problem
# Creation of the Kalis session
session = KSession()
# Creation of the problem in this session
problem = KProblem(session, "B-5 Paint production")
# Setting data as a KIntMatrix
K_cleaning_times_matrix = KIntMatrix(5, 5, 0, "CLEAN")
for i in range(nb_jobs):
for j in range(nb_jobs):
K_cleaning_times_matrix.setMatrix(i, j, jobs_cleaning_times[i][j])
### Variables creation
# Successor of a batch
batch_successor = KIntVarArray()
for j in range(nb_jobs):
batch_successor += KIntVar(problem, "succ(%d)" % j, 0, nb_jobs - 1)
batch_successor[j].remVal(j)
# Cycle time monitoring
clean_time = KIntVar(problem, "cleanTime", 0, 1000)
# Assign values to 'batch_successor' variables as to obtain a single cycle
# 'clean_time' is the sum of the cleaning times
problem.post(KCycle(batch_successor, None, clean_time, K_cleaning_times_matrix))
# Objective variable
cycle_time = KIntVar(problem, "cycleTime", 0, 1000)
problem.post(sum(jobs_durations) + clean_time == cycle_time)
### Solve the problem
# First propagation to check inconsistency
if problem.propagate():
print("Problem is infeasible")
sys.exit(1)
# Set the solver
solver = KSolver(problem)
# Setting objective and sense of optimization
problem.setSense(KProblem.Minimize)
problem.setObjective(cycle_time)
# Run optimization
result = solver.optimize()
# Solution printing
if result:
solution = problem.getSolution()
solution.printResume()
print("Minimum cycle time: %d" % solution.getValue(cycle_time))
print("Sequence of batches:")
print("Batch Duration Cleaning")
j = solution.getValue(batch_successor[0])
while j != 0:
next_job = solution.getValue(batch_successor[j])
print("%d\t%d\t%d" % (j, jobs_durations[j], jobs_cleaning_times[j][next_job]))
j = next_job
```

```
// Cleaning times between jobs
KIntMatrix CLEAN = new KIntMatrix(5,5,0,"CLEAN");
CLEAN.setMatrix(0,0,0);
CLEAN.setMatrix(1,0,11);
CLEAN.setMatrix(2,0,7);
CLEAN.setMatrix(3,0,13);
CLEAN.setMatrix(4,0,11);
CLEAN.setMatrix(0,1,5);
CLEAN.setMatrix(1,1,0);
CLEAN.setMatrix(2,1,13);
CLEAN.setMatrix(3,1,15);
CLEAN.setMatrix(4,1,15);
CLEAN.setMatrix(0,2,13);
CLEAN.setMatrix(1,2,15);
CLEAN.setMatrix(2,2,0);
CLEAN.setMatrix(3,2,23);
CLEAN.setMatrix(4,2,11);
CLEAN.setMatrix(0,3,9);
CLEAN.setMatrix(1,3,13);
CLEAN.setMatrix(2,3,5);
CLEAN.setMatrix(3,3,0);
CLEAN.setMatrix(4,3,3);
CLEAN.setMatrix(0,4,3);
CLEAN.setMatrix(1,4,7);
CLEAN.setMatrix(2,4,7);
CLEAN.setMatrix(3,4,7);
CLEAN.setMatrix(4,4,0);
// Successor of a batch
KIntVarArray succ = new KIntVarArray();
// Objective variable
KIntVar cycleTime = new KIntVar();
// Objective variable
KIntVar cleanTime = new KIntVar();
// Creation of the problem in this session
KProblem problem = new KProblem(session,"B-5 Paint production");
// variables creation
int j;
for (j=0; j<NJ; j++)
{
succ.add(new KIntVar(problem, "succ(" + j + ")",0, NJ-1) );
succ.getElt(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
int sumOfDUR = 0;
for (j=0; j<NJ; j++)
{
sumOfDUR += DUR[j];
}
problem.post(new KGreaterOrEqualXyc(cycleTime, cleanTime, sumOfDUR));
// propagating problem
if (problem.propagate())
{
System.out.println("Problem is infeasible");
exit(1);
}
// Solve the problem
// creation of the solver
KSolver solver = new KSolver(problem);
// setting objective and sense of optimization
problem.setSense(KProblem.Sense.Minimize);
problem.setObjective(cycleTime);
solver.optimize();
// solution printing
KSolution sol = problem.getSolution();
// print solution resume
sol.printResume();
// Solution printing
System.out.println("Minimum cycle time: " + sol.getValue(cycleTime));
System.out.print("Sequence of batches:\nBatch Duration Cleaning\n");
int first=0;
do {
System.out.print(first + "\t" + DUR[first] + "\t" + intp_value(CLEAN.getMatrix(first,sol.getValue(succ.getElt(first)))) + "\n");
first = sol.getValue(succ.getElt(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.