Production Planning in Automated Manufacturing

1 Automated manufacturing.- 1.1 Introduction.- 1.2 Production planning for FMSs.- 1.2.1 What is an FMS?.- 1.2.2 The hierarchical approach.- 1.2.3 Tactical Planning.- 1.2.4 Operational planning.- 1.3 Overview of the monograph.- 2 Throughput rate optimization in the automated assembly of printed circuit boards.- 2.1 Introduction.- 2.2 Technological environment.- 2.3 The throughput rate optimization problem.- 2.4 Workload balancing.- 2.4.1 Subproblem (A).- 2.4.2 Subproblem (B).- 2.5 Scheduling of individual machines.- 2.5.1 Subproblem (C).- 2.5.2 Subproblem (D).- 2.5.3 Subproblem (E).- 2.5.4 Subproblem (F).- 2.6 An example.- 3 Approximation algorithms for three-dimensional assignment problems with triangle inequalities.- 3.1 Introduction.- 3.2 Complexity of T? and S?.- 3.3 Approximation algorithms.- 3.4 Computational results.- 4 Scheduling jobs of equal length: complexity, facets and computational results.- 4.1 Introduction.- 4.2 Complexity of SEL.- 4.3 The LP-relaxation of SEL.- 4.4 More facet-defining and valid inequalities for SEL.- 4.5 A cutting-plane algorithm for SEL.- 5 The tool loading problem: an overview.- 5.1 Introduction.- 5.2 Machine flexibility and tool management.- 5.3 Modeling the magazine capacity constraint.- 5.3.1 A linear model.- 5.3.2 Nonlinear models.- 5.4 Solving the batch selection problem.- 5.5 Grouping of parts and tools.- 5.6 Tool switching.- 6 A column generation approach to job grouping.- 6.1 Introduction.- 6.2 Lower bounds.- 6.2.1 The job grouping problem.- 6.2.2 Column generation.- 6.2.3 The generation subproblem.- 6.2.4 Computation of lower bounds via column generation.- 6.2.5 Lagrangian relaxation.- 6.2.6 Other lower bounds.- 6.3 Upper bounds.- 6.3.1 Sequential heuristics for grouping.- 6.3.2 Set covering heuristics.- 6.4 Implementation.- 6.5 Computational experiments.- 6.5.1 Generation of problem instances.- 6.5.2 Computational results.- 6.6 Summary and conclusions.- 7 The job grouping problem for flexible manufacturing systems: some extensions.- 7.1 Introduction.- 7.2 Multiple slots.- 7.2.1 The job grouping problem.- 7.2.2 Lower bounds via column generation.- 7.2.3 Other lower bounds.- 7.2.4 Upper bounds.- 7.2.5 Adjusting the column generation procedure.- 7.2.6 Computational experiments.- 7.2.7 Computational results.- 7.3 Multiple machines.- 7.3.1 The job grouping problem.- 7.3.2 Lower bounds via column generation.- 7.3.3 Other lower bounds.- 7.3.4 Upper bounds.- 7.3.5 Adjusting the column generation procedure.- 7.3.6 Computational experiments.- 7.3.7 Computational results.- 7.4 Other extensions.- 7.5 Summary and conclusions.- 8 A local search approach to job grouping.- 8.1 Introduction.- 8.2 Local search environment.- 8.2.1 Starting solution.- 8.2.2 Objective function.- 8.2.3 Neighbourhood structure.- 8.2.4 Stopping criteria.- 8.3 Local search approaches.- 8.3.1 Simple improvement approach.- 8.3.2 Tabu search approach.- 8.3.3 Simulated annealing approach.- 8.3.4 Variable-depth approach.- 8.4 Computational experiments.- 8.4.1 The dataset.- 8.4.2 Computational results.- 8.5 Summary and conclusions.- 9 Minimizing the number of tool switches on a flexible machine.- 9.1 Introduction.- 9.2 Basic results.- 9.2.1 NP-hardness results.- 9.2.2 Finding the minimum number of setups for a fixed job sequence.- 9.3 Heuristics.- 9.3.1 Traveling salesman heuristics.- 9.3.2 Block minimization heuristics.- 9.3.3 Greedy heuristics.- 9.3.4 Interval heuristic.- 9.3.5 2-Opt strategies.- 9.3.6 Load-and-Optimize strategy.- 9.4 Computational experiments.- 9.4.1 Generation of problem instances.- 9.4.2 Computational results.- 9.5 Lower bounds.- 9.5.1 Traveling salesman paths.- 9.5.2 Structures implying extra setups.- 9.5.3 Valid inequalities.- 9.5.4 Lagrangian relaxation.- Appendix: Graph-theoretic definitions.- References.