遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究

A Genetic Algorithms for the Resource Constrained Project Scheduling Problem with Multi-Mode

錢明淦(Ming Tu Chien)

指導教授 ： 徐旭昇

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

摘要

本文的主旨為發展適用於具有多種資源組態及資源限制專案排程問題的啟發性解法，以儘可能地縮短專案的完工時間。所發展的啟發性解法以遺傳演算法為基礎，並提出兩種特殊的編碼技術，配合適當的排程方式以避免產生不合法子代的問題；同時導入移民運算子以及動態參數調整的觀念，來增加演算法的搜尋能力。此外也嘗試數種不同的交配和突變方法。至於演算法的參數設定問題，本文則是透過田口實驗計劃法對各項參數進行參數設計，以找出最穩健合適的參數組合。
本文利用Turbo C 2.0版撰寫程式，且為了與國際上其它研究者的演算法進行績效比較，我們使用國際題庫（PSPLIB）中的測試例題進行測試。測試結果十分理想，不論是誤差平均值、誤差標準差或找到最佳解的個數，均優於其它研究。
此外，我們針對專案管理問題開闢了一個網站，讓有興趣的研究者下載重要的參考資料，並提供各種測試題庫的連結，此網站的網址為http://project.engineer.com.tw。

關鍵字

遺傳演算法 ； 多資源組態 ； 資源限制 ； 專案管理 ； 移民運算子 ； 田口實驗計劃法

並列摘要

The purport of this article is to develop the heuristic algorithm, which is applicable in the multi-mode and the project scheduling problem of resource constrained, so as to shorten the construction time of the project as much as possible. The developed heuristic algorithm is based on genetic algorithms. We submitted two special encoding technologies to match with appropriate project scheduling so that the problem of illegal offspring could be avoided. Meanwhile, we introduced the idea of using the immigration operator and dynamic and adaptive strategies for varying the control parameters to strengthen the searching ability of algorithms. In addition, we also attempted several ways in crossover and mutation. Regarding setting of the parameters in algorithms, different parameters in this article was designed according to the Taguchi’s experiment in order to find out the most stable and suitable parameters set.
In this article, Turbo C 2.0 was used to write programs. In order to compare with the effectiveness of algorithms designed by other international researchers, this program was tested by sample test in the PSPLIB. The result was perfect and superior to other researches’, such as average error, standard average error or the numbers of the best solution.
In addition, we set up a website concerning the problem of case managing. Those who are interested in this project can down load the important references. This website also provides linkage to different sample tests. The address of this website is http://project.engineer.com.tw.

並列關鍵字

Genetic algorithms ； Multi-mode ； Resource constrained ； Project scheduling ； Immigration operator ； Taguchi''s experiment

參考文獻

[16] 楊宗銘，「遺傳演算法在多途程排程問題之探討」，中原大學，

[1] (美）Joseph j. Moder , Cecil R. Phillips著，工程管理-要徑法

[18] Ahn,T. and S.S.Erenguc,〝The Resource Constrained Project

[19] Bac,F.Q. and V.L.Preov,〝New Evolutionary Genetic

Algorithms for NP-Complete Combinatorial Optimization