Heuristic approaches for master planning in semiconductor manufacturing. (English) Zbl 1251.90110
Summary: We propose heuristic approaches for solving master planning problems that arise in semiconductor manufacturing networks. The considered problem consists of determining appropriate wafer quantities for several products, facilities, and time periods by taking demand fulfillment (i.e., confirmed orders and forecasts) and capacity constraints into account. In addition, fixed costs are used to reduce production partitioning. A mixed-integer programming (MIP) formulation is presented and the problem is shown to be NP-hard. As a consequence, two heuristic procedures are proposed: a product based decomposition scheme and a genetic algorithm. The performance of both heuristics is assessed using randomly generated test instances. It turns out that the decomposition scheme is able to produce high-quality solutions, while the genetic algorithm achieves results with reasonable quality in a short amount of time.
MSC:
| 90B30 | Production models |
| 90B90 | Case-oriented studies in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
master planning; semiconductor manufacturing; decomposition; genetic algorithm; computational experimentsReferences:
| [1] | Stadtler, H.; Kilger, C., Supply Chain Management and Advanced Planning: Concepts, Models, Software, and Case Studies (2007), Springer |
| [2] | Chien C-F, Dauzère-Pérès S, Ehm H, Fowler JW, Jiang Z, Krishnaswamy S, Mönch L, Uzsoy R. Modeling and analysis of semiconductor manufacturing in a shrinking world: challenges and successes. In: Proceedings of the Winter Simulation Conference; 2008. p. 2009-93.; Chien C-F, Dauzère-Pérès S, Ehm H, Fowler JW, Jiang Z, Krishnaswamy S, Mönch L, Uzsoy R. Modeling and analysis of semiconductor manufacturing in a shrinking world: challenges and successes. In: Proceedings of the Winter Simulation Conference; 2008. p. 2009-93. |
| [3] | Tempelmeier H. Supply chain planning with advanced planning systems. In: Proceedings of the Aegean International Conference on Design and Analysis of Manufacturing Systems; 2001.; Tempelmeier H. Supply chain planning with advanced planning systems. In: Proceedings of the Aegean International Conference on Design and Analysis of Manufacturing Systems; 2001. |
| [4] | Uzsoy, R.; Lee, C.-Y.; Martin-Vega, L. A., A review of production planning and scheduling models in the semiconductor industry part I: system characteristics, performance evaluation and production planning, IIE Transactions, 24, 4, 47-60 (1992) |
| [5] | Uzsoy, R.; Lee, C.-Y.; Martin-Vega, L. A., A review of production planning and scheduling models in the semiconductor industry part II: shop-floor control, IIE Transactions, 26, 5, 44-55 (1994) |
| [6] | Gupta, J. N.D.; Ruiz, R.; Fowler, J. W.; Mason, S. J., Operational planning and control of semiconductor wafer fabrication, Production Planning and Control, 17, 7, 639-647 (2006) |
| [7] | Vieira, G. E., Understanding Master Production Scheduling from a Practical Perspective: Fundamentals, Heuristics, and Implementations, (Hermann, J. W., Handbook of Production Scheduling (2006), Springer), 149-176 · Zbl 1090.90523 |
| [8] | Bermon, S.; Hood, S. J., Capacity optimization planning system (CAPS), Interfaces, 29, 5, 31-50 (1999) |
| [9] | Barahona, F.; Bermon, S.; Günlük, O.; Hood, S., Robust capacity planning in semiconductor manufacturing, Naval Research Logistics, 52, 5, 459-468 (2005) · Zbl 1072.90517 |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-Completeness (1979), W. H. Freeman and Co.: W. H. Freeman and Co. San Francisco · Zbl 0411.68039 |
| [11] | Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic production planning: algorithms and complexity, Management Science, 26, 7, 669-679 (1980) · Zbl 0445.90025 |
| [12] | Voß, S.; Woodruff, D. L., Introduction to Computational Optimization Models for Production Planning in a Supply Chain (2006), Springer · Zbl 1140.90006 |
| [13] | Stray, J.; Fowler, J. W.; Carlyle, M.; Rastogi, A. P., Enterprise-wide semiconductor resource planning, IEEE Transactions on Semiconductor Manufacturing, 19, 2, 259-268 (2006) |
| [14] | Wu, J.-Z.; Chien, C.-F., Modeling strategic semiconductor assembly outsourcing decisions based on empirical settings, OR Spectrum, 30, 3, 401-430 (2008) |
| [15] | Denton, B. T.; Forrest, J.; Milne, R. J., IBM solves a mixed-integer program to optimize its semiconductor supply chain, Interfaces, 36, 5, 386-399 (2006) |
| [16] | Chern, C.-C.; Hsieh, J.-S., A heuristic algorithm for master planning that satisfies multiple objectives, Computers & Operations Research, 34, 11, 3491-3513 (2007) · Zbl 1128.90026 |
| [17] | Vieira, G. E.; Ribas, P. C., Fractional factorial analysis to the configuration of simulated annealing applied to the multi-objective optimization of master production scheduling problems, International Journal of Production Research, 46, 11, 3007-3026 (2008) · Zbl 1141.90420 |
| [18] | Zobolas, G. I.; Tarantilis, C. D.; Ioannou, G., Extending capacity planning by positive lead time and optional overtime, earliness and tardiness for effective master production scheduling, International Journal of Production Research, 46, 12, 3359-3386 (2008) · Zbl 1141.90422 |
| [19] | Kallrath, J.; Maindl, T. I., Real Optimization with \(SAP^®\) APO (2006), Springer · Zbl 1214.90003 |
| [20] | Ponsignon, T.; Habla, C.; Mönch, L., A model for master planning in semiconductor manufacturing, Proceedings of the Industrial Engineering Research Conference, 1592-1597 (2008) |
| [21] | Ponsignon, T.; Mönch, L., A genetic algorithm to solve master planning problems in semiconductor manufacturing, Proceedings of the Industrial Engineering Research Conference, 2097-2102 (2009) |
| [22] | Pochet, Y.; Wolsey, L. A., Production Planning by Mixed-Integer Programming (2006), Springer · Zbl 1102.90039 |
| [23] | Aytug, H.; Khouja, M.; Vergara, F. E., Use of genetic algorithms to solve production and operations management problems: a review, International Journal of Production Research, 41, 17, 3955-4009 (2003) |
| [24] | Hornung, A.; Mönch, L., Heuristic approaches for determining minimum cost delivery quantities in supply chains, European Journal of Industrial Engineering, 2, 4, 377-400 (2008) |
| [25] | Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0721.68056 |
| [26] | Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs (1996), Springer · Zbl 0841.68047 |
| [27] | Wall M. ‘GALib—a C++ Library of Genetic Algorithm Components’, 〈http://lancet.mit.edu/ga/〉; Wall M. ‘GALib—a C++ Library of Genetic Algorithm Components’, 〈http://lancet.mit.edu/ga/〉 |
| [28] | Wilcoxon, F., Individual comparison by ranking methods, Biometrics Bulletin, 1, 6, 80-83 (1945) |
| [29] | Deb, K., An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186, 2-4, 311-338 (2000) · Zbl 1028.90533 |
| [30] | Pahl, J.; Voß, S.; Woodruff, D. L., Production planning with load dependent lead times: an update of research, Annals of Operations Research, 153, 1, 297-345 (2007) · Zbl 1159.90381 |
| [31] | Hung, Y.-F.; Leachman, R. C., A production planning methodology for semiconductor manufacturing based on iterative simulation and linear programming calculations, IEEE Transactions on Semiconductor Manufacturing, 9, 2, 257-269 (1996) |
| [32] | Irdem, D. F.; Kacar, N. B.; Uzsoy, R., An exploratory analysis of two iterative linear programming—simulation approaches for production planning, IEEE Transactions on Semiconductor Manufacturing, 23, 3, 442-455 (2010) |
| [33] | Irdem DF. Evaluation of clearing functions’ fitting methodology and performance for production planning models, Master Thesis, North Carolina State University, Raleigh; 2009.; Irdem DF. Evaluation of clearing functions’ fitting methodology and performance for production planning models, Master Thesis, North Carolina State University, Raleigh; 2009. |
| [34] | Venkataraman, R.; Nathan, J., Effect of forecast errors on rolling horizon master production schedule cost performance for various replanning intervals, Production Planning and Control, 10, 7, 682-689 (1999) |
| [35] | Tang, O.; Grubbström, R. W., Planning and replanning the master production schedule under demand uncertainty, International Journal of Production Economics, 78, 3, 323-334 (2002) |
| [36] | Xie, J.; Lee, T. S.; Zhao, X., Impact of forecasting errors on the performance of capacitated multi-item production systems, Computers & Industrial Engineering, 46, 2, 205-219 (2004) |
| [37] | Brandimarte, P., Multi-item capacitated lot-sizing with demand uncertainty, International Journal of Production Research, 44, 15, 2997-3022 (2006) · Zbl 1161.90381 |
| [38] | Huang, M.-G.; Chang, P.-L.; Chous, Y.-C., Demand forecasting and smoothing capacity planning for products with high random demand volatility, International Journal of Production Research, 46, 12, 3223-3239 (2007) · Zbl 1141.90398 |
| [39] | Robinson, E. P.; Sahin, F.; Gao, L.-L., Master production schedule time interval strategies in make-to-order supply chains, International Journal of Production Research, 46, 7, 1933-1954 (2007) · Zbl 1153.90435 |
| [40] | Leung, S. C.H.; Lai, K. K.; Ng, W.-L.; Wu, Y., A robust optimization model for production planning of perishable products, Journal of the Operational Research Society, 58, 4, 413-422 (2007) · Zbl 1278.90230 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
