Insertion techniques for job shop scheduling

Tamás Kis
EPFL - DMA, CH - 1015 Lausanne

Job-shop scheduling is an important part of scheduling theory. The quest for efficient methods to solve the classical problem and its extensions still continues. Several algorithms are based on inserting a set of operations into a schedule. On the one hand, most local search algorithms try to improve the actual schedule by removing a single operation and inserting it back into a better position. On the other hand, there is a class of algorithms that remove all operations from a machine and insert them back in a better order. In both cases, the success of the algorithms depends on how efficiently the insertion problem is solved. This shows that insertion techniques have great importance in solving the job-shop scheduling problem or its extensions.

In job-shop scheduling a set of jobs is to be processed on a set of machines. In the ''classical'' problem a job is a sequence of operations and operations require one machine each. Meanwhile, this model has been enriched by letting operations require more than one machine, and by specifying alternative subsets of machines for them. Moreover, the total order is replaced by a partial one in the definition of jobs.

In the first part of the dissertation we study a further extension, where the routing of a job is a directed graph that can model partial order of operations and which contains sets of alternative subgraphs. Exactly one subgraph must be chosen from each set of alternatives and the selected operations must be sequenced both on the machines and in the jobs. The insertion problem emerging in this context is twofold: insert a single operation into the sequence of operations on the machine required and into that of its job, respectively, and insert the operations of a subgraph alternative into the schedule. We propose an efficient algorithm for inserting a single operation into a schedule optimally that we use in a heuristic to solve the other insertion problem. Moreover, we propose two heuristic algorithms to solve the scheduling problem.

In the second part, we study the job insertion problem of job-shop scheduling. Given a feasible job-shop schedule of a set of jobs and a new job, which is not scheduled yet: the new job is to be inserted into the schedule without modifying the order of already scheduled operations, the objective being to minimise the maximum job tardiness or the maximum job completion time (makespan). This is an insertion problem where a set of operations have to be inserted into a schedule. We characterise the set of feasible insertions as the maximal stable sets of an appropriately defined graph, the so-called insertion graph. We propose a transformation of the insertion graph that enables us to compute a lower bound on the value of optimal insertions. We obtain these results by using the theory of perfect graphs and some elements of the theory of convex polytopes. We use our lower bound computation method in branch-and-bound algorithms for the job insertion problem.

Finally, we illustrate that insertion techniques are useful in practice by solving a complex scheduling problem defined by the chemical process industry. With a simple extension of the methods described in the first part of the dissertation we have been able to find solutions of higher quality than those obtained by a commercial software.

For further information, please contact