Solving the Economic Lot Scheduling Problem with Identical Facilities in Parallel Using Genetic Algorithms

使用遺傳演算法求解平行多機經濟批量排程問題

10.29977/JCIIE.200803.0001

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

遺傳演算法 ； 批量 ； 排程 ； 存貨 ； 同質機台 ； genetic algorithm ； lot ； scheduling ； inventory ； identical facilities

工業工程學刊

25卷2期（2008 / 03 / 01）

91 - 104

英文

經濟批量排程問題(ELSP)已確認是一個非多項式時間演算法可解(NP-hard)的存貨問題。一般求解ELSP時，大都使用分析式方法或啟發式方法。分析式方法如動態規劃及整數規劃，它在解決10種產品以上的ELSP時，會花費很多的演算時間。而啟發式方法所得到的解，都會傾向於區域的最小值，因此不能保證所求的解是全面的最佳解。本研究延伸傳統單機ESLP，探討單一生產系統中具有多部同質機台生產多種產品的ELSP，提出一個以遺傳演算法(GA)為基礎的三階段解法。在第一階段，本研究分別使用Carreno啟發式方法和GA來指派產品到合適的機台；接著在第二階段，藉由GA多點平行搜尋的優點，迅速求取多部相同機台之ELSP可能的最佳解；最後在第三階段運用ELSP之可行解測試法，來判斷GA所求得的解是否可行。實驗數據顯示本研究提出之三階段解法確實能兼具求解的品質和時間之要求。

In this study, we solve the Economic Lot Scheduling Problem (ELSP) for a production system with identical facilities in parallel. The ELSP with identical facilities in parallel is concerned with the lot sizing, scheduling, and production assignment decision of n items so as to minimize the total costs per unit time. Since the ELSP with identical facilities in parallel is NP-hard, we propose two three-phase solution approaches based on the Genetic Algorithm (GA). In the first phase, we employ either Carreno's [5] heuristic or a GA to determine the assignment of n items to the identical facilities in parallel. Then, another GA utilizes the advantage of its multi-directional search ability to search for the candidate solutions (i.e., the replenishment cycles of the products) in the second phase. The third phase uses an efficient heuristic to test the feasibility of the candidate solutions and tries to generate a feasible production schedule for each facility. Based on our random experiments, our GA-based approaches are able to efficiently solve the ELSP with identical facilities in parallel within a reasonable run time, and their solution quality dominates Carreno's [5] heuristic.

1. Yao, M. J.(2007).Solving the joint replenishment problem with warehouse-space restrictions using a genetic algorithm.Journal of the Chinese Institute of Industrial Engineers,24,128-141.
   連結：
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 Engineers,20,435-448.
   連結：
3. Boctor, F. F.(1987).The g-group heuristic for single machine lot scheduling.International Journal of Production Research,25,363-379.
4. Boesel, J.,B. L. Nelson,N. Ishii(2003).A framework for simulation-optimization software.IIE Transactions,35,221-229.
5. Bollapragada, R.,U. Rao(1999).Single-stage resource allocation and economic lot scheduling on multiple non-identical production lines.Management Science,45,889-904.
6. Bomberger, E.(1966).A dynamic programming approach to a lot size scheduling problem.Management Science,12,778-784.
7. Carreno, J. J.(1990).Economic lot scheduling for multiple products on parallel identical processors.Management Science,36,348-358.
8. Cormen, T. H.,C. S. Leiserson,R. L. Rivest(1993).Introduction to Algorithms.New York:McGraw-Hill.
9. Davis, S. G.(1990).Scheduling economic lot size production runs.Management Science,36,985-998.
10. Elmaghraby, S. E.(1978).The economic lot scheduling problem (ELSP): review and extension.Management Science,24,587-597.
11. Federgruen, A.,Y. S. Zheng(1993).Optimal power-of-two replenishment strategies in capacitated general production/distribution networks.Management Science,39,710-727.
12. Geng, P. C.,R. G. Vickson(1988).Two heuristics for the economic lot scheduling problem: an experimental study.Naval Research Logistics,35,605-617.
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. Haessler, R.,S. Hogue(1976).A note on the single machine multi-product lot scheduling problem.Management Science,22,909-912.
15. Hanssmann, F.(1962).Operations Research in Production and Inventory.New York:Johnson Wiley & Sons.
16. Hsu, W. L.(1983).On the general feasibility of scheduling lot sizes of several products on one machine.Management Science,29,93-105.
17. Hunter, A.(1998).Crossing over genetic algorithms: the Sugal generalized GA.Journal of Heuristics,4,179-192.
18. Jackson, P. L.,W. L. Maxwell,J. A. Muckstadt(1985).The joint replenishment problem with a power-of-two restriction.IIE Transactions,17,25-32.
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. Maxwell, W. L.,H. Singh(1986).Scheduling cyclic production on several identical machines.Operations Research,34,460-463.
21. 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.
22. Park, K. S.,D. K. Yun(1987).Feasibility test for multi-product lot size scheduling on one machine.Policy and Information,11,101-108.
23. Park, K. S.,D. K. Yun(1984).A stepwise partial enumeration algorithm for the economic lot scheduling problem.IIE Transactions,16,363-370.
24. Pesenti, R.,W. Ukovich(2003).Economic lot scheduling on multiple production lines with resource constraints.International Journal of Production Economics,81-82,469-481.
25. Evolutionary Algorithms: Principles, Methods, and Algorithms
26. Roundy, R.(1989).Rounding off to powers of two in continuous relaxations of capacitated lot sizing problem.Management Science,35,1433-1442.
27. Sarker, R.,C. Newton(2002).A genetic algorithm for solving economic lot size scheduling problem.Computers and Industrial Engineering,42,189-198.
28. Syswerda, G.(1989).Uniform crossover in genetic algorithms.Proceedings of the Third International Conference on Genetic Algorithms,Fairfax, VA, USA:
29. Yao, M. J.(2001).The peak load minimization problem in cycle production.Computers and Operations Research,28,1441-1460.
30. Yao, M. J.,S. E. Elmaghraby(2001).On the economic lot scheduling problem under power-of-two policy.Computers and Mathematics with Applications,41,1379-1393.

1. Liang, Wen-Yau,Huang, Chun-Che(2013).The Genetic Algorithm with Rough Set Theory Incorporated into the Patent Composition.International Journal of Information and Management Sciences,24(1),39-55.
2. (2012).Solving the Economic Lot and Inspection Scheduling Problem using the Extended Basic Period approach under Power-of-Two policy.工業工程學刊,29(1),43-60.
3. (2024)。以魚群演算法和固定速率法求解經濟批量檢驗和排程問題。技術學刊，39(3)，157-168。