On the Feasibility Testing of the Economic Lot Scheduling Problem Using the Extended Basic Period Approach

運用延伸基本周期法求解經濟批量排程問題之可行解測試

姚銘忠(Ming-Jong Yao) ； Salah E. Elmaghraby ； 陳萸欽(Ing-Chine Chen)

《工業工程學刊》 20卷5期 (2003/09) Pp. 435-448

摘要

本文探討運用延伸基本週期法求解經濟批量排程問題時，對搜尋演算法所獲得的解進行可行性測試的問題。在本研究中，我們首先回顧可行性測試問題的相關文獻，再提出兩個自行推導的整數（線性）規劃模式。為具體顯示可行性測試問題的困難度，本研究證明此問題為「非多項式複雜度演算法可解」(NP-hard)的問題。而鑑於本問題的困難度，本研究提出一個新的啟發式解法，命名為Proc FT，其運用隨機搜尋的架構進行求解。為測試啟發式解法的效率，本研究運用隨機產生的問題進行測試；實驗顯示啟發式解法的複雜度約可估計為O(n^3)，堪稱為一能迅速求解的方法。另外，本研究並對各種實驗參數進行敏感度分析，以確認該啟發式解法為一強韌的(Robust)好解法。本研究另一重要的結論是：在機台稼動率超過70％時，本研究所提出之啟發式解法則優於所有現存於文獻中的解法。

關鍵字

可行解測試 ； 批量排程 ； 隨機搜尋演算法 ； 比較

並列摘要

In this paper, we present our research on the feasibility testing problem for the Economic Lot Scheduling Problem (ELSP) using the Extended Basic Period (EBP) approach, i.e., the ELSP (EBP). We review past contributions to the issue of the feasibility of a given 'solution' to the ELSP and we propose two integer linear programming (ILP) models for its resolution. In view of the difficulty in solving the ILP (we demonstrate that this problem is NP-hard), we propose a new heuristic, Proc FT, to solve it. Numerical experiments verify that Proc FT is efficient, since its run time is of cubic order of the problem size, i.e., it is approximately an O(n^3) algorithm. Also, using a set of randomly generated problems, our experimental results provide some insights into how the difficulty of the problem grows with the parameters in the problem. Importantly, our experimental results demonstrate that Proc FT is more reliable than the other heuristics, especially, when the utilization rate of the production facility is more than70%.

並列關鍵字

feasibility testing ； lot scheduling ； random search algorithm ； comparison

參考文獻

Boctor, F. F.(1987).The G-group Heuristic for Single Machine Lot Scheduling.International Journal of Production Research.25(3)

Coffman, E. G.,Garey, M. R.,Johnson, D. S.(1984).Algorithm Design for Computer System Design.Vienna:Springer.

Davis, S. G.(1990).Scheduling Economic Lot Size Production Runs.Management Science.36(8)

Elmaghraby, S. E.(1978).The Economic Lot Scheduling Problem (ELSP): Review and Extension.Management Science.24(6)

Elmaghraby, S. E.,Elimam, A. A.(1980).Knapsack-Based Approaches to the Makespan Problem on Multiple Processors.AIIE Transactions.12