螞蟻演算法於有限資源專案排程最佳化之研究

An Ant Colony Approach for Resource-Constrained Project Scheduling

高文慶(Wen-Ching Kao)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2004年)

摘要

近年來，由於新產品推出速度愈來愈快，相對縮短產品的生命週期，使得企業對於專案排程所需資源安排之要求更為嚴苛，也因此格外重視有限制資源專案排程問題（Resource-Constrained Project Scheduling Problem；RCPSP），而此類問題屬於NP-Hard研究範疇。
本研究針對RCPSP問題，利用平行法(parallel)及向前(forward)運算法則，並配合局部啟發式函數ACT法則，發展出一螞蟻演算法(ACO-RCPSP)最佳化的解題架構。同時針對影響ACO-RCPSP演算法成效因子作參數實驗設計分析，進而提出單一資源問題(Single Resource Problem；SRP )及混合資源問題(Mix Resource Problem；MRP)的最佳參數組合，且透過測試題庫PSPLIB所提供的四種不同作業數(30、60、90及120)之題型進行測試及驗證。
本次研究所提出的ACO-RCPSP所得到的平均LB誤差距離與文獻最佳方法表現相仿，而最小LB誤差距離與目前已知最佳演算法AS-RCPSP相比，所求解的品質較佳且在搜尋效率上有顯著的改善，同時將ACT法則結合ACO演算法之ACO-RCPSP在測試所有不同作業數之題型時，求解的品質均遠優於單純只使用ACT法則之求解品質。

關鍵字

螞蟻演算法 ； 有限資源專案排程問題

並列摘要

Rapid development of new product has shortened the life cycle of product tremendously over the decades. Therefore, enterprises have learned to be much stricter on project scheduling in order to make use of all resources, and this situation leads to focusing on the resources-constrained project scheduling problem (RCPSP) which is an NP-Hard problem.
This research develops an ant colony optimization algorithm (ACO-RCPSP) to solve resources-constrained project scheduling problem. Parallel-forward scheduling method is used, and the maximum ACTim value first (ACT) rule is applied as the local heuristic. To investigate the effects of parameters in the ACO-RCPSP algorithm, a comprehensive design of experiment is employed for both single-resource type and mixed-resource type problems. Four different sizes of test problems from PSPLIB are used as the benchmarks.
ACO-RCPSP performs comparatively to other best-known methods considering the average percentage deviation from the lower bound, outperforms the best-known algorithm (AS-RCPSP) in the minimum percentage deviation from the lower bound measure, and improves the computational efficiency significantly. In addition, when comparing with the best-reported simple heuristic ACT in RCPSP literature, ACO-RCPSP easily outperforms ACT in all types of problems.

並列關鍵字

Ant Colony Optimization ； Resource-Constrained Project Scheduling Problem

參考文獻

3.高秀梅，「蟻群最佳化演算法於時窗車限制之輛途程問題的研究」，元智大學，碩士論文，民國九十二年。

14.錢明淦，「遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究」，元智大學，碩士論文，民國八十八年。

15.Ahn, T. and S. S. Erenguc, “The Resource Constrained Project Scheduling Problem with Multiple Crashable Modes：A Heuristic Procedure,” European Journal of Operational Research, Vol.107, No.2, pp.250-259, 1998.

16.Artigues, C., P. Michelon, and S. Reusser., “Insertion Techniques for Static and Dynamic Resource-Constrained Project Scheduling,“European Journal of Operational Research, Vol.149, No.2, pp.249-267, 2003.

18.Boctor, F. F., “Some Efficient Multi-Heuristic Procedures for Resource- Constrained Project Scheduling,” European Journal of Operational Research, Vol.49, No.1, pp.3-13, 1990.