Production Planning in Automated Manufacturing

ISBN-13: 9783642802720 / Angielski / Miękka / 2011 / 239 str.

Yves Crama; Alwin G. Oerlemans; Frits C. R. Spieksma

Opis

In this book quantitative approaches are proposed for production planning problems in automated manufacturing. In particular, techniques from operations research provide ways to tackle these problems. Special attention is given to the efficient use of tools in automated manufacturing systems. The book presents models and tests solution strategies for different kinds of production decision problems. A case study in the manufacturing of printed circuit boards highlights the methodology. The book will help to understand the nature of production planning problems in automated manufacturing and show how techniques from operations research may contribute to their solution.

Spis treści

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.