Decomposition Methods for Complex Factory Scheduling Problems

1 Introduction.- 1.1 Introduction.- 1.2 The Scheduling Problem in the Organization.- 1.3 The Nature of the Factory Scheduling Problem.- 1.4 Deterministic Formulation of the Factory Scheduling.- Problem.- 1.5 Outline of Book.- 2 Industrial Context and Motivation for Decomposition Methods.- 2.1 Introduction.- 2.2 Semiconductor Manufacturing.- 2.3 Formulation as a Job Shop Scheduling Problem.- 2.4 Decomposition Methods.- 2.5 Summary.- 3 Review of Decomposition Methods for Factory Scheduling Problems.- 3.1 Introduction.- 3.2 A Taxonomy of Decomposition Methods for Factory 31 Scheduling Problems.- 3.3 Temporal Decomposition Schemes.- 3.4 Entity Decomposition Schemes.- 3.5 Hybrid Decomposition Schemes.- 3.6 Discussion.- 3.7 Conclusions.- 4 Modelling Interactions Between Subproblems: the Disjunctive Graph Representation and Extensions.- 4.1 Introduction.- 4.2 Disjunctive Graph Representation of the Classical Job Shop 48 Problem.- 4.3 Delayed Precedence Constraints.- 4.4 Extensions to Disjunctive Graph Representation.- 4.5 Summary.- 5 Workcenter-Based Decomposition Procedures for The Classical Job Shop Environment.- 5.1 Introduction.- 5.2 The Shifting Bottleneck Procedure.- 5.3 Dispatching Rules Used in Experiments.- 5.4 Results for Benchmark J//Cmax Problems.- 5.5 Results for Small Job Shop Problems.- 5.6 Results for Large Problems.- 5.7 Evaluation of Shifting Bottleneck using Other Performance.- Measures.- 5.8 Summary.- 6 A Generic Decomposition Procedure for Semiconductor Testing Facilities.- 6.1 Introduction.- 6.2 The Generic Decomposition Procedure.- 6.3 Computational Experiments.- 6.4 Results.- 6.5 Conclusions.- 7 Time-Based Decomposition Procedures for Single-Machine Subproblems with Sequence-Dependent Setup Times.- 7.1 Introduction.- 7.2 Previous Related Work.- 7.3 Rolling Horizon Procedures.- 7.4 Branch and Bound Algorithm.- 7.5 Experimental Design.- 7.6 Results.- 7.7 Conclusions.- 8 Time-Based Decomposition Procedures for Parallel Machine Subproblems with Sequence-Dependent Setup Times.- 8.1 Introduction.- 8.2 Previous Related Work.- 8.3 Rolling Horizon Procedures for Parallel Machines.- 8.4 Use of RHP to Improve on LIST(EDD).- 8.5 Computational Experiments.- 8.6 Results.- 8.7 Conclusions and Future Directions.- 9 Naive Rolling Horizon Procedures for Job Shop Scheduling.- 9.1 Introduction.- 9.2 Scheduling Approach.- 9.3 Implementation and Computational Experiments.- 9.4 Results.- 9.5 Summary and Conclusions.- 10 Tailored Decomposition Procedures for Semiconductor Testing Facilities.- 10.1 Introduction.- 10.2 Subproblem Formulations.- 10.3 Modifications to the Rolling Horizon Procedures.- 10.4 Local Search Procedures for Single and Parallel Machine.- Problems.- 10.5 Operation-Based Decomposition.- 10.6 Tailored Control Structures for Semiconductor Testing.- Facilities.- 10.7 Summary.- 11. Computational Results for Job Shops with Single and Parallel Machine Workcenters.- 11.1 Introduction.- 11.2 Algorithms Compared in Experiments.- 11.3 Results for Shops with Single Machine Workcenters.- 11.4 Results for Shops with Parallel Machine Workcenters.- 11.5 Conclusions.- 12 The Effects of Subproblem Solution Procedures and Control Structures.- 12.1 Introduction.- 12.2 Two Additional Decomposition Procedures.- 12.3 Results for Semiconductor Testing Problems.- 12.4 Results for Reentrant Flow Shops.- 12.5 Summary and Conclusions.- 13 Conclusions and Future Directions.- 13.1 Introduction.- 13.2 Summary.- 13.3 Conclusions and Future Directions.- Author Index.