以基因演算法求解有限資源多專案排程問題

有限資源多專案排程問題不僅需考慮專案中各活動間的先行關係，尚需考慮多種所需資源的資源總數限制下進行排程，也由於這些限制使得有限資源多專案排程問題更符合實際情形且具有NP-hard(Non-Polynomial) 的特性，在此特性下使用最佳解法求解時會因為求解問題的大小使得排程的計算時間呈現指數的成長。因此為提高求解速度與排程績效，啟發式解法廣泛的被應用在求解有限資源多專案排程問題。本研究應用基因演算法 (Genetic algorithm：GA) 並搭配啟發式解法針對有限資源多專案排程問題進行求解並期望能達到最小化專案總延遲時間的排程目標，其中各專案到期日的設定方式如同文獻中所提及的，是以資源不受限制下的要徑法所計算出各專案的完成時間做為各專案到期日。本研究所應用的基因演算法與求解有限資源多專案排程問題中三種典型的啟發式解法進行比較，其中包含：Maximum Total Work Content (MAXTWK), Earliest Due Date (EDD), and Minimum Slack First (MINSLK)。並且套用文獻中兩個典型的有限資源多專案排程問題範例進行排程與績效評估，結果發現本研究應用的基因演算法當目標為最小化專案總延遲時間時，排程績效比其他三種啟發式解法較佳。

關鍵字

有限資源多專案排程問題；基因演算法；啟發式解法

並列摘要

Resource-constrained multiple project scheduling problems (RCMPSP) consider precedence relationship among activities and the capacity constraints of multiple resources for multiple projects. RCMPSP are NP-hard due to these practical constraints indicating an exponential calculation time to reach optimal solution. In order to improve the speed and the performance of problem solving, heuristic approaches are widely applied to solve RCMPSP. This research applies Genetic algorithm (GA) and heuristic approach to solve RCMPSP with an objective to minimize the total tardiness. Project due dates are set as the unconstrained critical path duration, similar to the way used in literature. The proposed GA is compared with three typical heuristics for RCMPSP: Maximum Total Work Content (MAXTWK), Earliest Due Date (EDD), and Minimum Slack First (MINSLK). Two typical RCMPSP from literature are used as a test bed for performance evaluation. The results demonstrate that GA outperforms the three heuristic methods in term of the total tardiness.

並列關鍵字

resource-constrained multi-project scheduling problems ； heuristic method ； genetic algorithm

參考文獻

J. Alcaraz, C. Maroto and R. Ruiz, Solving the Multi-Mode Resource-Constrained Project Scheduling Problem with Genetic Algorithms, The Journal of the Operational Research Society, Vol.54, No.6, pp.614, 2003.

J. Alcaraz and C.Maroto, A Robust Genetic Algorithm for Resource Allocation in Project Scheduling, Annals of Operation Research, Vol.102, pp.83-109, 2001.

J. Dumond, V. A. Marbet, Evaluating Project Scheduling and Due Date Assignment Procedures: an Experimental Analysis, Management Science, Vol.34, No.11, pp.101-118, 1988.

J. F. Goncalves, J. J. M. Mendes, and M. G. C. Resende, A Genetic Algorithm for the Resource Constrained Multi-Project Scheduling Problem, European Journal of Operational Research, Vol.189, pp.1171-1190, 2008.

J. J. Grefenstette, Optimization of Control Parameters for Genetic Algorithms, IEEE Transactions on Systems, Man and Cybernetics, Vol.16, pp.122-128, 1986.

國際替代計量

以基因演算法求解有限資源多專案排程問題

全文下載

主題瀏覽