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

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

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

《工業工程學刊》 25卷2期 (2008/03) Pp. 91-104

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

摘要

經濟批量排程問題(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.

並列關鍵字

genetic algorithm ； lot ； scheduling ； inventory ； identical facilities

參考文獻

Boctor, F. F.(1987).The g-group heuristic for single machine lot scheduling.International Journal of Production Research.25,363-379.

Boesel, J.,B. L. Nelson,N. Ishii(2003).A framework for simulation-optimization software.IIE Transactions.35,221-229.

Bollapragada, R.,U. Rao(1999).Single-stage resource allocation and economic lot scheduling on multiple non-identical production lines.Management Science.45,889-904.

Bomberger, E.(1966).A dynamic programming approach to a lot size scheduling problem.Management Science.12,778-784.

Carreno, J. J.(1990).Economic lot scheduling for multiple products on parallel identical processors.Management Science.36,348-358.