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

多組態有限資源多專案排程問題不僅需考慮專案中各活動間的先行關係，尚需考慮多種所需資源的資源總數限制下進行排程以及執行各種專案組態的資源限制，也由於這些限制使得多組態有限資源多專案排程問題更符合實際情形且具有NP-hard (Non-Polynomial) 的特性，在此特性下使用最佳解法求解時會因為求解問題的大小使得排程的計算時間呈現指數的成長。因此為提高求解速度與排程績效，啟髮式解法被應用在求解多組態有限資源多專案排程問題。本研究應用啟髮式解法配合基因演算法，發展一混合基因演算法 (Hybrid Genetic Algorithm: HGA) 針對多組態有限資源多專案排程問題進行求解並期望能達到最小化專案完成時間的排程目標。本研究從文獻中假設出48個多組態資源限制多專案排程問題，其中各專案到期日的設定方式如同文獻中所提及的，是以資源不受限制下的要徑法所計算出各專案的完成時間做為各專案到期日。本研究所應用的混合基因演算法搭配不同的啟髮式解法 (串列法與平行法) 與派工法則 (Earliest Due Date、Shortest Process Time、Minimum Slack、and Maximum Total Work Content) 進行比較，結果發現本研究提出的混合基因演算法當目標為最小化專案完成時間時，排程績效比基因演算法與其他混合基因演算法較佳。

關鍵字

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

並列摘要

Multi-Mode Resource-Constrained Multi-Project Scheduling Problems (MMRCMPSP) consider precedence relationship among activities、the capacity constraints of each execution mode of the activity、and multiple resources for multiple projects. MMRCMPSP 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 applied to solve MMRCMPSP. This research proposes Hybrid Genetic Algorithm (HGA) and heuristic approach to solve MMRCMPSP with an objective to minimize makespan. HGA is compared with four typical priority rules (Earliest Due Date、Shortest Process Time、Minimum Slack、and Maximum Total Work Content) and two heuristics methods (Serial and Parallel Heuristic methods) for MMRCMPSP. Forty-eight examples of MMRCMPSP from literature are used as a test bed for performance evaluation and project due dates are set as the unconstrained critical path duration、similar to the way used in literature. The results demonstrate that the proposed HGA outperforms the other HGA and simple-GA in term of the makespan.

並列關鍵字

Multi-mode resource-constrained multi-project schedulin ； Heuristic method ； Genetic algorithm

參考文獻

[2] Al-Fawzan M. A. and Haouari M.、2005. A bi-objective model for robust resource-constrained project scheduling、International Journal of Production Economics 96、175-187.

[3] Chen P. and Chahandashti S. M.、2009. Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints、Automation in Construction 18、434-443.

[4] Chen J. C.、Jaong W. H.、Sun C. J.、Lee H. Y.、Wu J. S.、and Ku C. C.、2010. Applying Genetic Algorithm to Resource Constrained Multi-Project Scheduling Problems、Key Engineering Materials 419-420、633-636.

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

[7] Grefenstette J. J.、1986. Optimization of Control Parameters for Genetic Algorithms、IEEE Transactions on Systems、Man and Cybernetics 16、122-128,.

國際替代計量

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

未授權

主題瀏覽