以分解型演化演算法求解多目標資源限制專案排程問題

Abstract

目前求解資源限制專案排程問題 (Resource-Constrained Project Scheduling Problem, RCPSP) 的文獻，大多注重於求解單目標問題，又以專案完工時間 (makespan) 當作目標為大多數。而在實務中，專案經理對專案考慮的目標往往是多方面的，除了專案完工時間之外，也須考量如何在讓所有的工作在所規定的時間內完成，避免工作的延遲導致成本的大幅提高。因此本研究針對最小化專案完工時間以及最小化總延遲時間 (total tardiness) 兩項目標進行求解。 本研究提出MOMA/D-IGR來求解此問題，改良自MOEA/D [7]，為了增加族群的多樣性，在環境選擇機制上，讓子代可取代的個數限制為一個，並且不讓相同個體進行取代更新。接著提出四種區域搜尋策略，希望能讓族群中的個體分採用求解方向對應之區域搜尋方法。實驗的測試問題採用Xiao等人 [15] 所提出的測試問題集，並與Xiao等人 [15] 所提出的6種演算法進行比較，分別為SPEA2、SPEA2-EM、NSGAII、NSGAII-EM、MOEA/D 以及MOEA/D-EM。實驗結果顯示MOMA/D-IGR能得出最好的效果。