ISBN: 3540679138
TITLE: Constraint Propagation in Flexible Manufacturing
AUTHOR: T.P. Huy
TOC:

1 Introduction 1
2 General Solution Methods 7
2.1 Constraint Satisfaction and Optimization 8
2.2 Constraint Propagation 10
2.2.1 K-Consistency 14
2.2.2 Domain-Consistency 15
2.2.3 Bound-Consistency 17
2.2.4 Consistency Tests 18
2.3 Exhaustive Search 22
2.3.1 Backtracking 23
2.3.2 Branch-and-Bound 25
2.3.3 Keeping the Balance 26
2.4 Local Search 26
2.4.1 Hill Climbing 29
2.4.2 Simulated Annealing 30
2.4.3 Tabu Search 31
2.4.4 Genetic Algorithms 33
3 The Disjunctive Scheduling Problem 35
3.1 The Disjunctive Scheduling Model 36
3.1.1 The Basic Model 36
3.1.2 A Graph Theoretical Approach 37
3.1.3 Subclasses of the DSP 41
3.2 Disjunctive Clique Decompositions 45
3.2.1 Cliques and Clique Decompositions 45
3.2.2 Computing Clique Decompositions 47
4 Constraint Propagation and the DSP 51
4.1 Some Basic Definitions 52
4.2 Conjunctive Consistency Tests 53
4.3 Lower-Level Bound-Consistency 54
4.3.1 2-B-Consistency 55
4.3.2 3-B-Consistency 56
4.4 Input/Output Consistency Tests 62
4.4.1 Sequence Consistency Tests 63
4.4.2 Domain Consistency Tests 64
4.4.3 Dominance Relations 64
4.4.4 Sequence Consistency Tests Revisited 68
4.4.5 Algorithms and Implementation Issues 68
4.5 Input/Output Negation Consistency Tests 79
4.5.1 Sequence Consistency Tests 79
4.5.2 Domain Consistency Tests 80
4.5.3 Dominance Relations 81
4.5.4 Algorithms and Implementation Issues 83
4.6 Input-or-Output Consistency Tests 91
4.6.1 Domain and Sequence Consistency Tests 91
4.6.2 Algorithms and Implementation Issues 92
4.7 Energetic Reasoning 96
4.7.1 Interval Processing Time 99
4.7.2 Energetic Input/Output Consistency Tests 99
4.7.3 Other Energetic Consistency Tests 102
4.8 Shaving 102
4.9 A Comparison of Disjunctive Consistency Tests 103
4.10 Conjunctive vs. Disjunctive Consistency Tests 105
4.11 Bound-Consistency Revisited 106
5 A Branch-and-Bound Algorithm 113
5.1 The Block Branching Scheme 114
5.1.l Block Decompositions 114
5.1.2 Block Branching Schemes 115
5.1.3 Block Decomposition Schemes 122
5.2 Lower Bound Calculation 124
5.2.1 Subproblem Based Lower Bounds 126
5.2.2 Constraint Propagation Based Lower Bounds 130
5.3 Upper Bound Calculation 131
5.4 Putting Things Together: The Algorithm 133
5.5 Computational Results 136
5.5.1 The JSP 137
5.5.2 The OSP 156
5.5.3 The DSP 165
6 A Decomposition Based Heuristic 172
6.1 Edge-Guessing 173
6.2 Parallel Strategy 176
6.3 A Sequential Strategy 178
6.4 Computational Results 181
6.4.1 The JSP 181
6.4.2 The DSP 187
7 A Local Search Based Heuristic 211
7.1 Neighbourhood Structures 211
7.2 Makespan Approximations 213
7.3 A Tabu Search Approach 217
7.4 Edge-Guessing and Local Search 220
7.5 Computational Results 220
7.5.1 The JSP 221
7.5.2 The OSP 222
7.5.3 The DSP 222
8 Some Concluding Remarks 234
List of Symbols 237
Bibliography 244
END
