Scheduling with Unary Resources: the Job-Shop Problem

INDEX PREVIOUS NEXT

Some scheduling problems are very difficult to find an optimal solution for, even if the problem is of a small size. The aim of this chapter (and of Chapter 16 and Chapter 30) is to explore various problem-solving methods that address such difficult scheduling problems. The examples are based on well-known problems from operations research about scheduling operations in a job-shop. Because these problems have proved so intractable in the past, we offer different approaches to them here with the aim of showing how to achieve satisfactory results for other intractable problems in a realistic industrial setting.

Describing the Problem presents three job-shop scheduling problems known as MT06, MT10, and MT20. They were first proposed in 1963 in the book Industrial Scheduling. The second of these problems remained unsolved for nearly 25 years and is still considered hard. Very few scheduling specialists have been able to solve it efficiently or satisfactorily.

Defining the Problem, Designing a Model develops the code needed to define these problems.

A Minimizing Algorithm applies the algorithm given in Chapter 14 to these problems. We observe that to get an optimal solution for MT10 we have to use a very high number of optimizing iterations, and the final iterations require a great amount of computational time. Similarly, MT20 remains unsolved after a large amount of computational time.

Another algorithm is developed in Chapter 16 to facilitate faster convergence toward an optimal solution. The idea is to converge to the optimal makespan by applying a dichotomic search. A specific search goal provides a good upper bound of the optimal makespan for this dichotomic search. That example also introduces a more efficient heuristic. The approach in Chapter 16 allows the three job-shop problems to be solved in a reasonable amount of computational time.

The job-shop problems are also discussed in Chapter 30. That chapter presents yet another kind of algorithm, one not guaranteed to generate an optimal solution, but one that tends to provide "good" solutions. Such an approach is often useful when solving complex and realistic problems.