Two Heuristic Algorithms for a Multi-Mode Resource-Constrained Multi-Project Scheduling Problem

求解多模式資源限制多專案排程問題之二個啟發式演算法

曾清枝(Ching-Chih Tseng)

《科學與工程技術期刊》 4卷2期 (2008/06) Pp. 63-74

https://doi.org/10.7117/JSET.200806.0063

摘要

至今有大量關於資源限制排程問題被發表，但對於探討多模式甚至於多專案之文獻卻相對稀少。因此，本文針對多模式資源限制多專案排程問題提出二個啟發式演算法，分別是結合作業和模式優先派遣法組合之平行排程演算法和遺傳演算法。依據前者演算法在四組模擬測試問題中比較20個作業和模式組合後，選出最可能求得最佳解之作業和模式最佳組合當作後者演算法之比較基礎。在每一組問題中，考慮二個資源可用量水準和二個限制工期水準。由於某些排程法則含有機率因子，兩階段抽樣方法被導入以確保可獲得更可靠的模擬結果。最後本文就所提出平行排程演算法使用最佳作業和模式優先派遣法組合，和所提出之遺傳演算法作模擬比較，結果發現所提出之遺傳演算法優於所提出平行排程演算法。

關鍵字

多專案排程 ； 平行排程演算法 ； 遺傳演算法 ； 兩階段抽樣方法

並列摘要

Many studies on the resource-constrained project-scheduling problem have been published, but literature further considering multi-mode or multi-project issues often occurring in the real world is rather scarce. In this research, two heuristic algorithms are developed to solve a multi-mode resource-constrained multi-project scheduling problem (MMRCMPSP). The first, a parallel scheduling algorithm (PSA), includes a combination of an activity- and a mode-priority rule; the second is a genetic algorithm (GA). The solutions obtained by the former algorithm with the best activity-and mode-priority rule combination are used as a baseline to compare those obtained by the latter. On four sets of test problems, twenty combinations of rules are compared to determine the best one for deriving the most likely best solution in the proposed PSA. In each set, two resource-availability levels and two due-date levels are considered. Due to certain priority rules' having probabilistic factors, a two-stage sampling method is introduced to ensure that more reliable computational results are obtained. Finally, the solutions obtained by the proposed PSA having the best activity- and mode- priority rule combination are compared on the test problems with those obtained by the proposed GA. Finally, conclusions are drawn from the computational results.

並列關鍵字

multi-project scheduling ； parallel scheduling algorithm ； genetic algorithm ； two-stage ； sampling