運用基因演算法規劃資源受限專案排程問題之探討

A Genetic Algorithm for Resource Constrained Project Scheduling Problem

吳育周(Yu-Chou Wu)

指導教授 ： 廖光彬

崑山科技大學/商業管理學院/企業管理研究所/碩士(2005年)

https://doi.org/10.6828/KSU.2005.00035

摘要

資源受限專案排程問題具有NP-Hard(nondeterministic polynomial)的特性，本研究所提出的基因演算法，對於不可行解，適應值函數以懲罰策略來處理，並將基因演算法之初始族群的大小，突變率，懲罰值對求解績效(求得較短工期)的影響作一個探討。本研究也針對兩個例題，將基因演算法的懲罰值及突變率作一個深入探討，將其懲罰值由1開始設定，逐一加至50，並搭配六種突變率來作分析。最後比較本研究所提出之基因演算法與平行法(parallel method)在求解績效上(求得較短工期)的表現。在測試的七個例題當中，一個例題的求解績效表現相當，而有五個例題，基因演算法的求解績效優於平行法。而在例題七，本研究將初始族群當中的一個染色體以平行法來獲得，其它19個染色體仍是隨機產生，並搭配0.1之突變率，懲罰值為20，測試結果顯示可求得有效解。故以平行法來獲得初始族群有助於提升本研究所提出的基因演算法之求得有效解之能力，其求解績效(搜尋較短工期)亦優於平行法，顯示本研究所提出之基因演算法在求得較佳工期上有不錯的效果。

關鍵字

基因演算法 ； 資源受限專案排程 ； 平行法

並列摘要

In this study, we develop a genetic algorithm to solve the resource-constrained project scheduling problem, which is a well-known NP-hard problem. For treating infeasible solutions, our approach is based on the design of fitness function which use penalizing strategy. Then we study the impact of population size, mutation rate, and penalty value on the performance of the genetic algorithm. We test two project instances, investigating the impact of mutation rate and penalty value on the performance of the genetic algorithm. For each one of the six mutation rates used, the penalty value is set from 1, added one by one till 50.
Finally, we have compared our genetic algorithm to the parallel method by using seven project instances. In the project instance 1, our genetic algorithm equals the parallel method in the optimal makespan, In the project instances 2 to 6, our genetic algorithm can produce makespans which are shorter than those produced by the parallel method. In the project instance 7, if one chromosome is initialized by the parallel method, 19 chromosomes are initialized by the random method, and a mutation rate of 0.1 and a penalty value of 20 are used, our genetic algorithm has a makespan better than that of the parallel method. It shows that the scheduling capability of the genetic algorithm can be enhanced if some of the chromosomes in the initial population are generated by the parallel method. Our genetic algorithm aided by the parallel method is superior to the parallel method in the optimal makespan.

Keywords: genetic algorithm, resource-constrained project scheduling problem, parallel method

並列關鍵字

genetic algorithm ； resource-constrained project scheduling problem ； parallel method

參考文獻

[ 5 ]錢明淦，“遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究”，碩士論文，元智大學工業工程研究所，民國88年。

[ 6 ]Boctor, F. F., “Some efficient multi-heuristic procedures for resource-constrained project scheduling,” European Journal of Operation Research, Vol.49, 1990, pp.3-13.

[ 8 ]Carruthers, J. A. and Battersby, A., “Advances in critical path methods,” Operational Research Quarterly, Vol.17, 1966.

[ 9 ]Christofides, N. Alvarez-Valdes, R. and Tamarit, J. M., “Project scheduling with resource constrains: a branch and bound approach,” European Journal of OperationalResource, Vol.29, 1987 , pp. 262-273.

[ 10 ]Davis, E. W., and Heidorn, G. E., “An algorithm for optimal project scheduling under multiple constrains, ”Management Sci., Vol. 7, 1971, pp.803-816.