Constraint propagation in flexible manufacturing (Q1582801)

The book is based on the author's PhD thesis and is devoted to the development of solution methods for a very general scheduling problem that is called Disjunctive Scheduling Problem (DSP). The problem is in fact a version of the job shop problem to minimize the makespan subject to conjunctive and disjunctive precedence constraints imposed over the set of operations. The model also incorporates the setup times and the transportation times. Chapter 1 gives a brief introduction. Chapter 2 (General Solution Methods) presents an overview of various solution techniques such as constraint propagation, branch-and bound and local search. The DSP and its properties are formally discussed in Chapter 3. Chapter 4 describes an application of constraint propagation to the DSP. A branch-and bound algorithm that in particular incorporates a constraint propagation lower bound is the subject of Chapter 5. Various decomposition strategies are presented in Chapter 6. Finally, Chapter 7 handles several local search heuristics. The discussion is supported by numerous results of computational experiments and their analysis.