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

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

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

《工業工程學刊》 23卷2期 (2006/03) Pp. 127-140

https://doi.org/10.29977/JCIIE.200603.0004

摘要

本研究提出一新的演算法求解二冪策略下流程型工廠之經濟批量排程問題。由相關文獻回顧顯示出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.

並列關鍵字

Lot scheduling ； Heuristics ； Random experiments ； Power-of-Two policy

參考文獻

Bazaraa, M.,H. D. Sherali,C.M. Shetty(1993).Nonlinear Programming: Theory and Algorithms.

Crowston, W. B.,Wagner, M.,Williams J.F.(1973).Economic lot-size determination in multi-stage assemble systems.Management Science.19,517-527.

Elmaghraby, S. E.(1978).The economic lot scheduling problem (ELSP): review and extension.Management Science.24,587-597.

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.

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.