Constraint Propagation in Flexible Manufacturing
1 Introduction.- 2 General Solution Methods.- 2.1 Constraint Satisfaction and Optimization.- 2.2 Constraint Propagation.- 2.3 Exhaustive Search.- 2.4 Local Search.- 3 The Disjunctive Scheduling Problem.- 3.1 The Disjunctive Scheduling Model.- 3.2 Disjunctive Clique Decompositions.- 4 Constraint Propagation and the DSP.- 4.1 Some Basic Definitions.- 4.2 Conjunctive Consistency Tests.- 4.3 Lower-Level Bound-Consistency.- 4.4 Input/Output Consistency Tests.- 4.5 Input/Output Negation Consistency Tests.- 4.6 Input-or-Output Consistency Tests.- 4.7 Energetic Reasoning.- 4.8 Shaving.- 4.9 A Comparison of Disjunctive Consistency Tests.- 4.10 Conjunctive vs. Disjunctive Consistency Tests.- 4.11 Bound-Consistency Revisited.- 5 A Branch-and-Bound Algorithm.- 5.1 The Block Branching Scheme.- 5.2 Lower Bound Calculation.- 5.3 Upper Bound Calculation.- 5.4 Putting Things Together: The Algorithm.- 5.5 Computational Results.- 6 A Decomposition Based Heuristic.- 6.1 Edge-Guessing.- 6.2 A Parallel Strategy.- 6.3 A Sequential Strategy.- 6.4 Computational Results.- 7 A Local Search Based Heuristic.- 7.1 Neighbourhood Structures.- 7.2 Makespan Approximations.- 7.3 A Tabu Search Approach.- 7.4 Edge-Guessing and Local Search.- 7.5 Computational Results.- 8 Some Concluding Remarks.- List of Symbols.
Springer, J.B. Metzler
978-3-540-67913-4

