有限資源專案排程之巨集啟發式演算法的比較

Abstract

有限資源的專案排程問題(Resource-Constrained Project Scheduling，RCPSP)具有複雜的求解特性。過去已有許多學者提出不同方法來求解，其中Debels et al. (2006)演算法是目前相對較佳的方法。本研究結合共識因子和田口方法提出多種巨集演算法(meta-heuristics)，希望找出一種演算法，能在績效上改進Debels et al. (2006)的演算法。本研究使用1560個案例，分成9種情境進行實驗。與Debels et al. (2006)演算法相比，本研究所發展的演算法僅在22%的情境表現較佳，在另22%的情境績效相近，卻在56%的情境中表現較不如過去的演算法。

Resource-constrained project scheduling is a NP-hard problem. In the last few decades, several meta-heuristics algorithms have been proposed to solve the problem. The algorithm proposed by Debels et al. (2006) is by far the most leading one. To develop a better algorithm, we applied the notions of consensus and Taguchi genetic operators and proposed various meta-heuristics algorithms. Extensive numerical tests have been carried out. These tests include 1560 problem instances, which are categorized into 9 scenarios. Compared with the algorithm proposed by Debels et al. (2006), our algorithm excel in 22% scenarios, has a tie in 22% scenarios, and lose in 56% scenarios.