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 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 with that take as value the number of the job in position (rank) . Every job takes a single position. This constraint can be represented by a KAllDifferent on the variables:

The processing time for the job in position is given by (where denotes the duration given in the table in the previous section). Similarly, the release time is given by (where denotes the given release date):

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

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

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 ). The complete model is then given by the following (where is a sufficiently large value, such as the sum of all release dates and all durations):

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

The new objective consists of minimizing the average processing time, or equivalently, minimizing the sum of the job completion times:

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 for the variable that corresponds to the tardiness of the job with rank . Its value is the difference between the completion time of a job and its due date . If the job finishes before its due date, the value must be zero. We thus obtain the following constraints:

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

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 REL[] = { 2,  5,  4,  0,  0,  8,  9};
int DUR[] = { 5,  6,  8,  4,  2,  4,  2};
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 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;
}
}
}
}
}
}
}
MAXTIME = MAXREL + SDUR;

char name[80];
}
start += (* new KIntVar(problem,name,0,MAXTIME));
}
dur += (* new KIntVar(problem,name,MINDUR,MAXDUR));
}
comp += (* new KIntVar(problem,name,0,MAXTIME));
}
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;

}

// Release date of job at position k
}

// Sequence of jobs
}
// Start times
// Completion times
}

// 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.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("Rel\t");
}
printf("\nDur\t");
}
printf("\nStart\t");
}
printf("\nEnd\t");
}
printf("\nDue\t");
}
printf("\n");

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

KLinTerm totalCompletionTerm;
}
KIntVar averageCompletion(problem,"average completion",0,1000);
problem.post(averageCompletion == totalCompletionTerm);

problem.setObjective(averageCompletion);
result = solver.optimize();
// solution printing
printf("average: %i\n",problem.getSolution().getValue(averageCompletion));
printf("Rel\t");
}
printf("\nDur\t");
}
printf("\nStart\t");
}
printf("\nEnd\t");
}
printf("\nDue\t");
}
printf("\n");

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

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

due += (* new KIntVar(problem,name,MINDUE,MAXDUE));
late += (* new KIntVar(problem,name,0,MAXTIME));
}

// Due date of job at position k
}

KLinTerm totLatTerm;
// building each tasks with fixed time horizon (0..HORIZON)
// Late jobs: completion time exceeds the due date
}

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

problem.setObjective(totLate);
result = solver.optimize();
// solution printing
printf("average: %i\n",problem.getSolution().getValue(averageCompletion));
printf("Tardiness: %i\n",problem.getSolution().getValue(totLate));
printf("Rel\t");
}
printf("\nDur\t");
}
printf("\nStart\t");
}
printf("\nEnd\t");
}
printf("\nDue\t");