An Improved Heuristic for Solving the Economic Lot Scheduling Problem in Flow Shops under Power-of-Two Policy

二冪策略下求解流程型工廠經濟批量排程之改良式演算法

10.29977/JCIIE.200603.0004

黃嘉彥(Jia-Yen Huang)；姚銘忠(Ming-Jong Yao)

批量排程 ； 演算法 ； 隨機試驗 ； 二冪策略 ； Lot scheduling ； Heuristics ； Random experiments ； Power-of-Two policy

工業工程學刊

23卷2期（2006 / 03 / 01）

127 - 140

英文

本研究提出一新的演算法求解二冪策略下流程型工廠之經濟批量排程問題。由相關文獻回顧顯示出Ouenniche與Boctor[15]的演算法不但是目前現有解法中最佳者，並可獲得合理解。然其解法中仍存在許多的問題，故本研究之動機即為針對此法提出一個改良式的演算法。為評估本演算法的效能，本研究以隨機產生1,800個例子的方式測試比較兩種解法。由試驗的結果顯示本改良式演算法所求得解的品質明顯地優於Ouenniche與Boctor的演算法。

This paper proposes a new heuristic for solving the economic lot scheduling problem in flow shops under the Power-of-Two policy. A review of relevant literature shows that the heuristic in Ouenniche and Boctor [15] not only solves this problem with the best objective function value among the existing solution approaches, but also generates a feasible production schedule. However there are several problems when implementing Ouenniche and Boctor's heuristic. Therefore, we are motivated to propose an improved heuristic in this study. To evaluate the performance of the improved heuristic, a total of 1,800 instances were randomly generated and then solved by both solution approaches in our experiments. The numerical results conclude that the improved heuristic significantly outperforms Ouenniche and Boctor's heuristic.

1. Bazaraa, M.,H. D. Sherali,C.M. Shetty(1993).Nonlinear Programming: Theory and Algorithms
2. Crowston, W. B.,Wagner, M.,Williams J.F.(1973).Economic lot-size determination in multi-stage assemble systems.Management Science,19,517-527.
3. Elmaghraby, S. E.(1978).The economic lot scheduling problem (ELSP): review and extension.Management Science,24,587-597.
4. El-Najdawi, M .K.(1997).Multi-cycle flow shop scheduling: An application in multi-stage, multi-product production processes.International Journal of Production Research,35,3323-3332.
5. El-Najdawi, M. K.(1994).A job-splitting heuristic for lot-size scheduling in multi-stage, multi-product production processes.European Journal of Operational Research,75,365-377.
6. El-Najdawi, M. K.,P. R. Kleindorfer(1993).Common cycle lot-size scheduling for multi-product multi-stage production.Management Science,39,872-885.
7. Goyal, S. K.(1976).Note on manufacturing cycle time determination for a multi-stage economic production quantity model.Management Science,23,323-333.
8. Hsu, J. I. S.,M. K. El-Najdawi(1990).Common cycle scheduling in a multistage production process.Engineering Costs and Production Economics,20,73-80.
9. Hsu, W. L.(1983).On the general feasibility of scheduling lot sizes of several products on one machine.Management Science,29,93-105.
10. Huang, J. Y,M. J. Yao(2003).On the Production Schedule Generation for the Economic Lot-sizing Problem in Flow Shop.The Annual Conference of Chinese Institute of Industrial Engineering
11. Jensen P. A.,H. A. Khan(1972).Scheduling in a multistage production system with set-up and inventory costs.AIIE Transactions,4,136-133.
12. Lopez, M. A.,B. G. Kingsman(1991).The economic lot scheduling problem: theory and practice.International Journal of Production Economics,23,147-164.
13. Moily, J. P.(1986).Optimal and heuristic procedure for component lot-splitting in multi-stage manufacturing systems.Management Science,32,113-122.
14. Ouenniche, J.,F. F. Boctor(2001).The multi-product, economic lot-sizing problem in flow shops: the power-of-two heuristic.Computers & Operations Research,28,1165-1182.
15. Ouenniche, J.,F. F. Boctor(2001).The two-group heuristic, to solve the multi-product, economic lot-sizing and scheduling problem in flow shops.European Journal of Operational Research,539-554.
16. Ouenniche, J.,F. F. Boctor(1998).Sequencing, lot-sizing and scheduling of several products in flow shops: the common cycle approach.International Journal of Production Research,35,1125-1140.
17. Szendrovits, A. Z.(1975).Manufacturing cycle time determination for a multi-stage economic production quantity model.Management Science,22,298-307.
18. Szendrovits, A. Z.(1976).On the optimality of sub-batch sizes for a multi-stage EPQ model – a rejoiner.Management Science,23,334-338.
19. Taha, H. A.,R. W. Skeith(1970).The economic lot-sizes in multi-stage production systems.AIIE Transactions,2,157-162.
20. Yao, M. J.(1999).North Carolina USA,North Carolina State University.

1. Yao, Ming-Jong,Chang, Yu-Jen(2009).A GENETIC ALGORITHM FOR SOLVING THE ECONOMIC LOT SCHEDULING PROBLEM WITH REWORKS.工業工程學刊,26(5),411-425.
2. 陳泓任,張育仁(2023)。以渦蟲演算法求解應用基本週期法的經濟批量檢驗與排程問題。計量管理期刊，20(2)，31-56。
3. 張育仁(2023)。以人工蜂群演算法求解結合固定速率法和基本週期法下考量保存期限制的經濟批量排程問題。計量管理期刊，20(1)，95-118。