以遺傳演算法求解一般整數策略下之經濟批量排程問題

Tunghai University Institutional Repository > 工學院 > 工業工程與經營資訊學系所 > 碩博士論文 > Item 310901/3973

Please use this identifier to cite or link to this item: http://140.128.103.80:8080/handle/310901/3973

Title:	以遺傳演算法求解一般整數策略下之經濟批量排程問題
Other Titles:	Solving the Economic Lot Scheduling Problem under General-Integer Policy Using Genetic Algorithms
Authors:	陳英欽 Chen, Lng-Chine
Contributors:	林水順;彭泉;蔡禎騰;姚銘忠 Lin, Shui-Shun;Perng, Chyuan;Tsai, Jen-Teng;Yao, Ming-Jong 東海大學工業工程與經營資訊學系
Keywords:	遺傳演算法;經濟批量;生產排程;存貨 Genetic Algorithm;Lot;Scheduling;Inventory
Date:	2002
Issue Date:	2011-05-19T05:14:30Z (UTC)
Abstract:	經濟批量排程問題(ELSP)已確認是一個非多項式時間演算法可解(NP-hard)的存貨問題，一般求解ELSP的問題，大都使用分析式方法或啟發式方法。分析式方法如動態規劃及整數規劃，它在解決10種產品以上的ELSP問題時，會花費很多的演算時間。而啟發式方法所得到的解，都會傾向於區域的最小值，因此不能保證所求的解是全面的最佳解。為解決上述求解ELSP的缺點，本研究希望藉由遺傳演算法(GA)多點平行搜尋的優點，迅速求取ELSP可能的最佳解。再運用經濟批量排程問題之可行解測試法(Feasibility Testing Procedure for the ELSP；Proc FT)，來判斷GA所求得的解是否可行。本研究先以文獻範例進行測試與修訂所提出的解法(即GA + Proc FT)，再依機器不同的產能利用率隨機產生共80組的數據，來驗證本研究所得到最佳解的品質及演算法的時間。在單台機器生產10種產品及產能利用率小於 0.70時，利用本研究所建構的方法平均約2分鐘(Pentium 266 PC with 64M RAM)，即可找到與成本下限值平均差距1.12%以內的可行解，足見其解法優異的效率，故此解法可作為決策者生產排程上的參考。 The Economic Lot Scheduling Problem (ELSP) is an NP-hard inventory problem. The solution approaches for the ELSP may be classified into two categories, i.e., analytic approaches and heuristic approaches. However, the analytic approaches, for example, dynamic programming and integer programming, usually take extremely long run time to secure an optimal solution. On the other hand, the heuristic approaches often lead to a local minimum, and there is no guarantee for the quality of the solution. In order to efficiently solve the ELSP, we derive a hybrid genetic algorithm (HGA) that utilizes the advantage of multi-directional search in GA and employs an efficient heuristic, namely, Proc FT, to test feasibility of the solutions found. We pilot-run our HGA using the benchmark examples in literature, and then fine-tune the parameters of HGA by the testing results. Also, we generate random experiments to verify the performance of our HGA and to show that HGA secures excellent-quality solutions within a reasonably short run time. Especially, when the utilization rate of the production facility is less than 70%, the average deviation of HGA’s solutions from a lower bound is within 1.12%. Therefore, we conclude that our HGA is able to efficiently solve the ELSP, and it may provide important decision support for production managers.
Appears in Collections:	[工業工程與經營資訊學系所] 碩博士論文

Files in This Item:

There are no files associated with this item.

Loading...