Abstract
We consider a problem of order-lot pegging in semiconductor wafer fabrication process. In the problem, we determine an assignment of wafers in lots to orders and a plan for input release of wafers into a wafer fabrication facility with the objective of minimizing total tardiness of the orders over a finite time horizon. The problem is formulated as a mixed integer linear program and proved to be strongly NP-hard. We find properties for an optimal order-lot assignment of the problem and develop a pegging method based on the properties. Also, we prove that an optimal order-lot assignment can be obtained by finding an optimal order sequence of assigning wafers to orders when using the pegging method developed in this study. In addition, we suggest two search heuristic algorithms for finding the optimal order sequence of assigning wafers to orders. The test results on randomly generated problems show that the suggested algorithms work fairly well compared to the commercial optimization software package and solve industrial-sized problems in a reasonable amount of time.
Similar content being viewed by others
References
Allahverdi A, Ng CT, Cheng TCE and Kovalyov MY (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research 187 (3): 985–1032.
Baker KR and Trietsch D (2009). Principles of Sequencing and Scheduling. Wiley: New York.
Bang JY and Kim YD (2010). Hierarchical production planning for semiconductor wafer fabrication based on linear programming and discrete-event simulation. IEEE Transactions on Automation Science and Engineering 7 (2): 326–336.
Bang JY and Kim YD (2011). Scheduling algorithms for a semiconductor probing facility. Computers and Operations Research 38: 666–673.
Bang JY, An KY, Kim YD and Lim SK (2005). A due-date-based algorithm for order-lot pegging in a semiconductor wafer fabrication facility. In: Proceedings of the Third International Conference on Modeling and Analysis of Semiconductor Manufacturing, Singapore, pp 175–180.
Bang JY, An KY, Kim YD and Lim SK (2008). A due-date-based algorithm for lot-order assignment in a semiconductor wafer fabrication facility. IEEE Transactions on Semiconductor Manufacturing 21 (2): 209–216.
Boushell TG, Fowler JW, Keha A, Knutson KR and Montgomery DC (2008). Evaluation of heuristics for a class-constrained lot-to-order matching problem in semiconductor manufacturing. International Journal of Production Research 46 (12): 3143–3166.
Carlyle M, Knutson K and Fowler J (2001). Bin covering algorithms in the second stage of the lot to order matching problem. Journal of the Operations Research Society 52 (11): 1232–1243.
Chen ZL and Pundoor G (2006). Order assignment and scheduling in a supply chain. Operations Research 54 (3): 555–572.
Du J and Leung JYT (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 15 (3): 483–495.
Fowler J, Knutson K and Carlyle M (2000). Comparison and evaluation of lot-to-order matching policies for a semiconductor assembly and test facility. International Journal of Production Research 38 (8): 1841–1853.
Glover F and Kochenberger GA (2003). Handbook of Metaheuristics. Kluwer Academic Publishers: Dordrecht, MA.
Kim JG, Lim SK, Shim SO and Choi SW (2010). Order-lot pegging heuristics for minimizing total tardiness in a wafer fabrication facility. Proceedings of IEEM, Macao, pp 1224–1229.
Kim YD, Kim JU, Lim SK and Jun HB (1998). Due-date based scheduling and control policies in a multiproduct semiconductor wafer fabrication facility. IEEE Transactions on Semiconductor Manufacturing 11 (1): 155–164.
Kim YD, Kang JH, Lee GE and Lim SK (2011). Scheduling algorithms for minimizing tardiness of orders at the burn-in workstation in a semiconductor manufacturing system. IEEE Transactions on Semiconductor Manufacturing 24 (1): 14–26.
Knutson K, Kempf K and Fowler J (1999). Lot-to-order matching for a semiconductor assembly and test facility. IIE Transactions 31 (11): 1103–1111.
Lim SK and Kim JG (2009). Order-lot pegging for minimizing total tardiness in a wafer fabrication facility. Proceedings of APIEMS 2009: 2425–2431.
Ng TS, Sun Y and Fowler JW (2010). Semiconductor lot allocation using robust optimization. European Journal of Operational Research 205: 557–570.
Potts CN and Kovalyov MY (2000). Scheduling with batching: A review. European Journal of Operational Research 120 (2): 228–249.
Potts CN and Van Wassenhove LN (1992). Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. Journal of the Operations Research Society 43 (5): 395–406.
Steiner G and Yeomans JS (1996). Optimal level schedules in mixed-model, multi-level JIT assembly systems with pegging. European Journal of Operations Research 95 (1): 38–52.
Wu TW (2003). Modular demand and supply pegging mechanism for semiconductor foundry. Proceedings of the 2003 IEEE International Symposium on Semiconductor Manufacturing, San Jose, CA, pp 325–328.
Acknowledgements
This work was supported by the Korea Research Foundation (KRF) grant funded by the Korea government (MEST) (No. 2009-0074109).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kim, JG., Lim, SK. Order-lot pegging for minimizing total tardiness in semiconductor wafer fabrication process. J Oper Res Soc 63, 1258–1270 (2012). https://doi.org/10.1057/jors.2011.133
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.133