.. _paintProduction2:

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 :ref:`section 11.5 <kImplies>` 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 :math:`JOBS = \{1, ..., NJ\}` be the set of batches to produce, :math:`DUR_j` the processing time for batch :math:`j`, and :math:`CLEAN_{i,j}` the cleaning time between the consecutive batches :math:`i` and :math:`j`. As before we define decision variables :math:`succ_j` taking their values in :math:`JOBS`, to indicate the successor of every job. The complete model formulation is the following,

.. math ::
    &\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.

.. tabs::
    
    .. code-tab:: c++
        
        // 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);

    .. code-tab:: py
    
            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
        
    .. code-tab:: java
    
        // 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.