Skip to main content
Log in

Order-lot pegging for minimizing total tardiness in semiconductor wafer fabrication process

  • General Paper
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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.

    Article  Google Scholar 

  • Baker KR and Trietsch D (2009). Principles of Sequencing and Scheduling. Wiley: New York.

    Book  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Bang JY and Kim YD (2011). Scheduling algorithms for a semiconductor probing facility. Computers and Operations Research 38: 666–673.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Chen ZL and Pundoor G (2006). Order assignment and scheduling in a supply chain. Operations Research 54 (3): 555–572.

    Article  Google Scholar 

  • Du J and Leung JYT (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 15 (3): 483–495.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • Glover F and Kochenberger GA (2003). Handbook of Metaheuristics. Kluwer Academic Publishers: Dordrecht, MA.

    Book  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • Lim SK and Kim JG (2009). Order-lot pegging for minimizing total tardiness in a wafer fabrication facility. Proceedings of APIEMS 2009: 2425–2431.

    Google Scholar 

  • Ng TS, Sun Y and Fowler JW (2010). Semiconductor lot allocation using robust optimization. European Journal of Operational Research 205: 557–570.

    Article  Google Scholar 

  • Potts CN and Kovalyov MY (2000). Scheduling with batching: A review. European Journal of Operational Research 120 (2): 228–249.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

Download references

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

Authors

Corresponding author

Correspondence to J-G Kim.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2011.133

Keywords

Navigation