Learning in Automated Manufacturing: A Local Search Approach

ISBN-13: 9783790807929 / Angielski / Miękka / 1994 / 257 str.

Erwin Pesch

Opis

The central purpose of this book is to acquaint the reader especially with the cases of local search based learning as well as to introduce methods of constraint based reasoning, both with respect to their use in automated manufacturing. We restrict our attention to job shop scheduling as well as to one-machine scheduling with sequence dependent setup times. Additionally some design and planning issues in flexible manufacturing systems are considered. General purpose search methods which in particular include methods from local search such as simulated annealing, tabu search, and genetic algorithms, are the basic ingredients of the proposed intelligent knowledge-based scheduling systems, enriched by a number of constraint-based local decision rules in order to introduce problem specific knowledge.

Spis treści

I. Local Search and Extensions.- 1. Introduction — Local Search.- 2. Infamous Scheduling Problems.- 3. Simulated Annealing.- 4. Tabu Search.- 5. Genetic Algorithms.- II. The Traveling Salesman Problem.- 1. Introduction and Survey.- 2. Effective Genetic Local Search.- 2.1 Numerical Results.- 2.2 Discussion.- 3. Bounded Genetic Local Search.- 3.1 Implementation Details and Numerical Results.- 3.2 Conclusions.- 4. Variable Depth Search Based Learning.- 4.1 Ejection Chains.- 4.2 Computational Results.- 4.3 Conclusions.- III. Job Shop Scheduling.- 1. Introduction — Conventional and New Solution Techniques.- 2. Evolution Based Learning.- 2.1 Genetic Enumeration.- 2.2 Heuristics for the Job Shop Scheduling Problem.- 2.3 Learning by Population Genetics.- 2.4 Details of Implementation and Computational Results.- 2.5 Conclusions.- 3. Learning by Constraint Propagation.- 3.1 Constraint Propagation and Backtrack Search.- 3.2 The Job Shop Constraint Satisfaction Problem.- 3.3 An Immediate Selection Heuristic.- 3.4 Computational Results.- 3.5 Conclusions.- 4. Decomposition Based Learning.- 4.1 Opportunistic Scheduling Heuristics.- 4.2 Constraint Propagation, Local Consistency, and Genetic Based Learning.- 4.3 Computational Results.- 4.4 Conclusions.- IV. Flexible Manufacturing Systems.- 1. Clustering in Cellular Manufacturing.- 1.1 Introduction and Background.- 1.2 The Clique-Partitioning Problem.- 1.3 An Ejection Chain Heuristic.- 1.4 Computational Results of the Heuristics.- 1.5 An EC-Based Branch and Bound Algorithm.- 1.6 Computational Results of the EC-Based Branch and Bound Algorithm.- 1.7 Conclusions.- 2. Factory Layout Planning.- 2.1 Introduction and Background.- 2.2 Fundamental Results.- 2.3 Advanced Moves.- 2.4 Updates and Data Structure Management for Advanced Moves.- 2.5 Algorithms for Generating and Improving Maximally Planar Graphs.- 2.6 Ejection Chains.- 2.7 Computational Results and Comments.- 3. Workload Balancing.- 3.1 Introduction and Background.- 3.2 The Condorcet Model.- 3.3 The Model.- 3.4 Basic Results.- 3.5 Main Results.- 3.6 Polynomial Algorithms.- 3.7 Examples and Counterexamples.- 3.8 Conclusions.- Epilogue.- References.