Sequencing jobs on a single machine

The problem described in this section is taken from Section 7.4 Sequencing jobs on a bottleneck machine of the book Applications of optimization with Xpress-MP. The aim of this problem is to provide a model that may be used with different objective functions for scheduling operations on a single (bottleneck) machine. We shall see here how to minimize the total processing time, the average processing time, and the total tardiness. A set of tasks (or jobs) is to be processed on a single machine. The execution of tasks is nonpreemptive (that is, an operation may not be interrupted before its completion). For every task i its release date, duration, and due date are given in the following table :

Job

1

2

3

4

5

6

7

Release date

2

5

4

0

0

8

9

Duration

5

6

8

4

2

4

2

Due date

10

21

15

10

5

15

22

What is the optimal value for each of the objectives: minimizing the total duration of the schedule (makespan), the mean processing time or the total tardiness (that is, the amount of time by which the completion of jobs exceeds their respective due dates) ?

Model formulation

We are going to present a model formulation that is close to the Mathematical Programming formulation in Applications of optimization with Xpress-MP. In model formulation we are going to deal with the different objective functions in sequence, but the body of the models will remain the same. To represent the sequence of jobs we introduce variables rank_k with k \in JOBS = \{1, . . . , NJ\} that take as value the number of the job in position (rank) k. Every job j takes a single position. This constraint can be represented by a KAllDifferent on the rank_k variables:

&\text{all-different}(rank_1,..., rank_{NJ})\\

The processing time dur_k for the job in position k is given by DUR_{rank_k} (where DUR_j denotes the duration given in the table in the previous section). Similarly, the release time rel_k is given by REL_{rank_k} (where REL_j denotes the given release date):

&\forall k \in JOBS : dur_k = DUR_{rank_k}\\ &\forall k \in JOBS : rel_k = REL_{rank_k}\\

If start_k is the start time of the job at position k, this value must be at least as great as the release date of the job assigned to this position. The completion time comp_k of this job is the sum of its start time plus its duration:

&\forall k \in JOBS : start_k \geq rel_k\\ &\forall k \in JOBS : comp_k = start_k + dur_k\\

Another constraint is needed to specify that two jobs cannot be processed simultaneously. The job in position k+1 must start after the job in position k has finished, hence the following constraints:

&\forall k \in \{1, ..., NJ-1 \} : start_{k+1} \geq start_k + dur_k\\

Objective 1: The first objective is to minimize the makespan (completion time of the schedule), or, equivalently, to minimize the completion time of the last job (job with rank NJ). The complete model is then given by the following (where MAXTIME is a sufficiently large value, such as the sum of all release dates and all durations):

&\text{minimize } comp_{NJ}\\ &\forall k \in JOBS : rank_k \in JOBS\\ &\forall k \in JOBS : start_k,comp_k \in \{0, ..., MAXTIME\}\\ &\forall k \in JOBS : dur_k \in \{\min_{j\in JOBS}DUR_j, ..., \max_{j \in JOBS}DUR_j\}\\ &\forall k \in JOBS : rel_k \in \{\min_{j\in JOBS}REL_j, ..., \max_{j \in JOBS}REL_j\}\\ &\text{all-different}(rank_1, ..., rank_{NJ})\\ &\forall k \in JOBS : dur_{k} = DUR_{rank_k}\\ &\forall k \in JOBS : rel_{k} = REL_{rank_k}\\ &\forall k \in JOBS : start_k \geq rel_k\\ &\forall k \in JOBS : comp_k = start_k + dur_k\\ &\forall k \in \{1, ..., NJ-1 \} : start_{k+1} \geq start_k + dur_k\\

Objective 2: For minimizing the average processing time, we introduce an additional variable totComp representing the sum of the completion times of all jobs. We add the following constraint to the problem to calculate totComp:

&totComp = \sum_{k \in JOBS} comp_{k}\\

The new objective consists of minimizing the average processing time, or equivalently, minimizing the sum of the job completion times: \text{minimize }totComp

Objective 3: If we now aim to minimize the total tardiness, we again introduce new variables this time to measure the amount of time that jobs finish after their due date. We write late_k for the variable that corresponds to the tardiness of the job with rank k. Its value is the difference between the completion time of a job j and its due date DUE_j. If the job finishes before its due date, the value must be zero. We thus obtain the following constraints:

&\forall k \in JOBS : due_k = DUE_{rank_k}\\ &\forall k \in JOBS : late_k \geq comp_k - due_k\\

For the formulation of the new objective function we introduce the variable totLate representing the total tardiness of all jobs. The objective now is to minimize the value of this variable:

&\text{minimize }totLate\\ &totLate = \sum_{k \in JOBS} late_k\\

Implementation

The implementation below (BottleneckSequencing.cpp) solves the same problem three times, each time with a different objective, and prints the resulting solutions.

// Number of tasks
int NTASKS = 7;
// Release date of tasks
int REL[] = { 2,  5,  4,  0,  0,  8,  9};
// Duration of tasks
int DUR[] = { 5,  6,  8,  4,  2,  4,  2};
// Due date of tasks
int DUE[] = {10, 21, 15, 10,  5, 15, 22};

// Number of job at position k
KIntVarArray  rank;
// Start time of job at position k
KIntVarArray start;
// Duration of job at position k
KIntVarArray dur;
// Completion time of job at position k
KIntVarArray comp;
// Release date of job at position k
KIntVarArray rel;

// Creation of the problem in this session
KProblem problem(session,"B-4 Sequencing");

// compute some statistics
int indexTask;
int MAXTIME = 0;
int MINDUR = MAX_INT;
int MAXDUR = 0;
int MINREL = MAX_INT;
int MAXREL = 0;
int MINDUE = MAX_INT;
int MAXDUE = 0;
int SDUR = 0;
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    if (MINDUR > DUR[indexTask]) {
        MINDUR = DUR[indexTask];
    }
    if (MAXDUR < DUR[indexTask]) {
        MAXDUR = DUR[indexTask];
    }
    if (MINREL > REL[indexTask]) {
        MINREL = REL[indexTask];
    }
    if (MAXREL < REL[indexTask]) {
        MAXREL = REL[indexTask];
    }
    if (MINDUE > DUE[indexTask]) {
        MINDUE = DUE[indexTask];
    }
    if (MAXDUE < DUE[indexTask]) {
        MAXDUE = DUE[indexTask];
    }
    SDUR += DUR[indexTask];
}
MAXTIME = MAXREL + SDUR;

char name[80];
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    sprintf(name,"rank(%i)",indexTask);
    rank += (* new KIntVar(problem,name,0,NTASKS-1));
}
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    sprintf(name,"start(%i)",indexTask);
    start += (* new KIntVar(problem,name,0,MAXTIME));
}
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    sprintf(name,"dur(%i)",indexTask);
    dur += (* new KIntVar(problem,name,MINDUR,MAXDUR));
}
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    sprintf(name,"comp(%i)",indexTask);
    comp += (* new KIntVar(problem,name,0,MAXTIME));
}
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    sprintf(name,"rel(%i)",indexTask);
    rel += (* new KIntVar(problem,name,MINREL,MAXREL));
}

// One position per job
problem.post(KAllDifferent("alldiff(rank)",rank));

// Duration of job at position k
KIntArray idur;
KIntArray irel;
KIntArray idue;

for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    idur += DUR[indexTask];
    irel += REL[indexTask];
    idue += DUE[indexTask];
}

for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    KEltTerm kelt(idur,rank[indexTask]);
    problem.post(kelt == dur[indexTask]);
    // Release date of job at position k
    KEltTerm keltrel(irel,rank[indexTask]);
    problem.post(keltrel == rel[indexTask]);
}

for (indexTask = 0;indexTask < NTASKS-1; indexTask++) {
    // Sequence of jobs
    problem.post(start[indexTask+1] >= start[indexTask] + dur[indexTask]);
}
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    // Start times
    problem.post(start[indexTask] >= rel[indexTask]);
    // Completion times
    problem.post(comp[indexTask] == start[indexTask] + dur[indexTask]);
}

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

// Set the branching strategy
KBranchingSchemeArray myBa;
myBa += KSplitDomain(KSmallestDomain(),KMinToMax());
// creation of the solver
KSolver solver(problem,myBa);

// **********************
// Objective 1: Makespan
// **********************
problem.setObjective(comp[NTASKS-1]);
problem.setSense(KProblem::Minimize);

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

// solution printing
printf("Completion time: %i\n",problem.getSolution().getValue(comp[NTASKS-1]));
printf("Rel\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",REL[indexTask]);
}
printf("\nDur\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",DUR[indexTask]);
}
printf("\nStart\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",problem.getSolution().getValue(start[indexTask]));
}
printf("\nEnd\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",problem.getSolution().getValue(comp[indexTask]));
}
printf("\nDue\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",DUE[indexTask]);
}
printf("\n");

// ***************************************
// Objective 2: Average completion time:
// ***************************************

KLinTerm totalCompletionTerm;
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    totalCompletionTerm = totalCompletionTerm + comp[indexTask];
}
KIntVar averageCompletion(problem,"average completion",0,1000);
problem.post(averageCompletion == totalCompletionTerm);

problem.setObjective(averageCompletion);
result = solver.optimize();
// solution printing
printf("Completion time: %i\n",problem.getSolution().getValue(comp[NTASKS-1]));
printf("average: %i\n",problem.getSolution().getValue(averageCompletion));
printf("Rel\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",REL[indexTask]);
}
printf("\nDur\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",DUR[indexTask]);
}
printf("\nStart\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",problem.getSolution().getValue(start[indexTask]));
}
printf("\nEnd\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",problem.getSolution().getValue(comp[indexTask]));
}
printf("\nDue\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
printf("%i\t",DUE[indexTask]);
}
printf("\n");

// *****************************
// Objective 3: total lateness:
// *****************************

// Lateness of job at position k
KIntVarArray late;
// Due date of job at position k
KIntVarArray due;

for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    sprintf(name,"due(%i)",indexTask);
    due += (* new KIntVar(problem,name,MINDUE,MAXDUE));
    sprintf(name,"late(%i)",indexTask);
    late += (* new KIntVar(problem,name,0,MAXTIME));
}

// Due date of job at position k
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    KEltTerm keltdue(idue,rank[indexTask]);
    problem.post(keltdue == due[indexTask]);
}

KLinTerm totLatTerm;
// building each tasks with fixed time horizon (0..HORIZON)
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
// Late jobs: completion time exceeds the due date
    problem.post(late[indexTask] >= (comp[indexTask]) - due[indexTask]);
    totLatTerm = totLatTerm + late[indexTask];
}

KIntVar totLate(problem,"total lateness",0,1000);
problem.post(totLate == totLatTerm);

problem.setObjective(totLate);
result = solver.optimize();
// solution printing
printf("Completion time: %i\n",problem.getSolution().getValue(comp[NTASKS-1]));
printf("average: %i\n",problem.getSolution().getValue(averageCompletion));
printf("Tardiness: %i\n",problem.getSolution().getValue(totLate));
printf("Rel\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",REL[indexTask]);
}
printf("\nDur\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",DUR[indexTask]);
}
printf("\nStart\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",problem.getSolution().getValue(start[indexTask]));
}
printf("\nEnd\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
printf("%i\t",problem.getSolution().getValue(comp[indexTask]));
}
printf("\nDue\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",DUE[indexTask]);
}
printf("\nLate\t");
for (indexTask = 0;indexTask < NTASKS; indexTask++) {
    printf("%i\t",problem.getSolution().getValue(late[indexTask]));
}
printf("\n");

Results

The minimum makespan of the schedule is 31, the minimum sum of completion times is 103 (which gives an average of 103 / 7 = 14. 71). A schedule with this objective value is 5 \rightarrow 4 \rightarrow 1 \rightarrow 6 \rightarrow 2 \rightarrow 3. If we compare the completion times with the due dates we see that jobs 1, 2, 3, and 6 finish late (with a total tardiness of 21). The minimum tardiness is 18. A schedule with this tardiness is 5 \rightarrow 1 \rightarrow 4 \rightarrow 6 \rightarrow 2 \rightarrow 7 \rightarrow 3 where jobs 4 and 7 finish one time unit late and job 3 is late by 16 time units, and it terminates at time 31 instead of being ready at its due date, time 15. This schedule has an average completion time of 15.71.