A Genetic Algorithm for Solving the Economic Lot Scheduling Problem with Reworks

使用遺傳演算法求解有重製狀況的經濟批量排程問題

10.29977/JCIIE.200909.0009

張育仁(Yu-Jen Chang)；姚銘忠(Ming-Jong Yao)

存貨 ； 重製 ； 排程 ； 遺傳演算法 ； 經濟批量 ； inventory ； reworks ； scheduling ； genetic algorithm ； economic lot

工業工程學刊

26卷5期（2009 / 09 / 01）

411 - 425

英文

最近幾年，有重製狀況的經濟批量排程問題(economic lot scheduling problem with reworks, ELSPR)之研究日漸受到重視。ELSPR是假設一產品的製造批量生產完畢後，會有一部份因爲瑕疵等因素而必須進行修理(repair)或重加工(rework)。ELSPR的成本有兩個：一個是理想成本(ideal cost)，包括整置成本和存貨持有成本等，一是額外成本(additional cost)，包括因修復或重製之時間差而導致的額外存貨持有成本。因此，求解ELSPR的目標是最小化理想成本和額外成本的總和。當產品的參數是已知且固定，則理想成本是一固定的數值，而額外成本則與產品之批量生產順序有密切關係。本研究提出在共同週期法下ELSPR之數學模式，並假設在一週期內一產品僅有一個製造批量和一個重製批量。本研究建議一個混合式遺傳演算法來求解ELSPR之最佳批量生產順序，以最小化額外成本。本研究的數值範例顯示遺傳演算法的求解效率，得到的成本最多僅比最佳解高出0.18%。

In this study, we are interested in the economic lot scheduling problem (ELSP) with reworks in which the production system deals with two sources of products: manufacturing of the serviceable products and remanufacturing of the rework products. We may consider that these two categories of products compete for the same facility and they must be scheduled simultaneously. In this paper, we formulate a mathematical model for the ELSP with reworks using the common cycle (CC) approach in which only one manufacturing lot and only one rework lot for each product exist during a common cycle, and all the products share the same replenishment cycle. In order to solve this problem, we propose a hybrid genetic algorithm (GA) approach that obtains an optimal production sequence of all manufacturing and rework lots with the lowest average total cost. Our numerical examples demonstrate the effectiveness of the proposed hybrid GA.

1. Tang, O.,R. H. Teunter(2006).Economic lot scheduling problems with returns.Production and Operations Management,15,488-497.
   連結：
2. Yao, M. J.,S. E. Elmaghraby,I. C. Chen(2003).On the feasibility testing of the economic lot scheduling problem using the extended basic period approach.Journal of the Chinese Institute of Industrial Engineering,20,435-448.
   連結：
3. Barad, M.,D. Braha(1996).Control limits for multi-stage manufacturing processes with binomial yield (single and multiple production runs).Journal of the Operational Research Society,47,98-112.
4. Boctor, F. F.(1987).The g-group heuristic for single machine lot scheduling.International Journal of Production Research,25,363-379.
5. Boesel, J.,B. L. Nelson,N. Ishii(2003).A framework for simulation-optimization software.IIE Transactions,35,221-229.
6. Bomberger, E.(1966).A dynamic programming approach to a lot size scheduling problem.Management Science,12,778-784.
7. Buscher, U.,G. Lindner(2007).Optimizing a production system with rework and equal sized batch shipments.Computers & Operations Research,34,515-535.
8. Chatfield, D.(2007).The economic lot scheduling problem: a pure genetic search approach.Computers and Operations Research,34,2865-2881.
9. Elmaghraby, S. E.(1978).The economic lot scheduling problem (ELSP): review and extension.Management Science,24,587-597.
10. Flapper, S. D. P.,J. C. Fransoo,R. A. C. M. Broekmeulen,K. Inderfurth(2002).Planning and control of rework in the process industries: a review.Production Planning & Control,13,26-34.
11. Golany, B.,J. Yang,G. Yu(2001).Economic lot-sizing with remanufacturing options.IIE Transactions,33,995-1003.
12. Grosfeld-Nir, A.,Y. Gerchak(2002).Multistage production to order with rework capability.Management Science,48,652-664.
13. Grznar, J.,C. Riggle(1997).An optimal algorithm for the basic period approach to the economic lot scheduling problem.International Journal of Management Science,25,355-364.
14. Hanssmann, F.(1962).Operations Research in Production and Inventory.NY:Johnson Wiley & Sons.
15. Hsu, W. L.(1983).On the general feasibility of scheduling lot sizes of several products on one machine.Management Science,29,93-105.
16. Hunter, A.(1998).Crossing over genetic algorithms: the Sugal generalized GA.Journal of Heuristics,4,179-192.
17. Inderfurth, K.,S. D. P. Flapper,A. J. D. Lambert,C. P. Pappis,T. G., Voutsinas,R. Dekker(eds),M. Fleischmann(eds),K. Inderfurth(eds),L. N. van Wassenhove (eds)(2004).Reverse Logistics-Quantitative Models for Closed-Loop Supply Chains.Springer.
18. Khouja, M.(2000).The economic lot and delivery scheduling problem: common cycle, rework, and variable production rate.IIE Transactions,32,715-725.
19. Khouja, M.,Z. Michalewicz,M. Wilmot(1998).The use of genetic algorithms to solve the economic lot size scheduling problem.European Journal of Operation Research,110,509-524.
20. Lee, H. L.(1992).Lot sizing to reduce capacity utilization in a production process with defective items, process corrections, and rework.Management Science,38,1314-1328.
21. Lee, H. L.,M. J., Rosenblatt(1987).Simultaneous determination of production cycle and inspection schedules in a production system.Management Science,33,1125-1136.
22. Lopez, M. A.,B. G. Kingsmans(1991).The economic lot scheduling problem: theory and practice.International Journal of Production Economics,23,147-164.
23. Moon, I.,E. A. Silver,S. Choi(2002).Hybrid genetic algorithm for the economic lot-scheduling problem.International Journal of Production Research,40,809-824.
24. Pohlheim, H.(2004).Evolutionary algorithms: principles, methods, and algorithms
25. Porteus, E. L.(1990).The impact of inspection delay on process and inspection lot sizing.Management Science,36,999-1007.
26. Porteus, E. L.(1986).Optimal lot sizing, process quality improvement and setup cost reduction.Operations Research,34,137-44.
27. Richter, K.(1996).The EOQ and waste disposal model with variable setup numbers.European Journal of Operational Research,95,313-324.
28. Richter, K.(1996).The extended EOQ repair and waste disposal model.International Journal of Production Economics,45,443-448.
29. Sarker, R.,C. Newton(2002).A genetic algorithm for solving economic lot size scheduling problem.Computers and Industrial Engineering,42,189-198.
30. Schrady, D. A.(1967).A deterministic inventory model for repairable items.Naval Research Logistics Quarterly,14,391-398.
31. Teunter, R. H.(2004).Lot-sizing for inventory systems with product recovery.Computers & Industrial Engineering,46,431-441.
32. Teunter, R. H.(2001).Economic ordering quantities for recoverable Item inventory systems.Naval Research Logistics,48,484-495.
33. Teunter, R. H.,K. Kaparis,O. Tang(2008).Multu-product economic lot scheduling problem with　separate production lines for manufacturing and remanufacturing.European Journal of Operational Research,191,1241-1253.
34. Teunter, R. H.,Z. P. Bayindir,W. V. D. Heuvel(2006).Dynamic lot sizing with product returns and remanufacturing.International Journal of Production Research,44,4377-4400.
35. Torabi, S. A.,S. M. T. Fatemi Ghomi,B. Karimi(2006).A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains.European Journal of Operational Research,173,173-189.
36. Wein, A. S.(1992).Random yield, rework and scrap in a multistage batch manufacturing environment.Operations Research,40,551-563.
37. Winston, W. L.(1991).Operations Research Applications and Algorithms.Boston:PWS-Kent Publishing Company.
38. Yano, C. A.,H. L., Lee(1995).Lot sizing with random yields: a review.Operations Research,43,311-334.
39. Yao, M. J.(1999).PhD thesis, North Carolina State University, USA.USA:North Carolina State University.

1. (2012).Solving the Economic Lot and Inspection Scheduling Problem using the Extended Basic Period approach under Power-of-Two policy.工業工程學刊,29(1),43-60.
2. (2024)。以魚群演算法和固定速率法求解經濟批量檢驗和排程問題。技術學刊，39(3)，157-168。