多組態資源限制專案排程問題解算之研究－包含不可恢復資源限制

A Two-stage Solving Approach to Multi-mode Resource-Constrained Project Scheduling Problem with non-renewable types

林欣慧(Hsin-Huei Lin)

指導教授 ： 徐旭昇

元智大學/工程學院/工業工程與管理學系/碩士(2005年)

摘要

本研究主旨為研究發展有效率演算法解算多組態資源限制專案排程問題(Multiple-mode resource constrained project scheduling problem，MMRCPSP)，目標為使總專案完工時間最小化。在求解過程中，將整體問題分為兩個階段：(1)使用分枝界限法（Branch and Bound，B&B）搜尋可行組態指派（mode assignments），以可執行組態作為分枝，配合剩餘資源量以及剩餘作業最小總需求量作為界限條件，並應用分離網枝（disjunctive arcs）概念選取可能產生較優解之組態指派。此外，由於分枝界限法僅用於求解可行組態指派，無需受限於作業先後順序，再加上同時應用兩種界限方式降低無謂的搜尋時間，因此本研究所探討的「樹」之結構遠遠小於過往文獻的方法，亦即大幅度地縮小求解空間，提升最佳化解法的求解效率；(2)利用蟻群最佳化演算法（Ant Colony Optimization，ACO）和模擬退火法（Simulated Annealing，SA）求解(1)所得結果之排程解，即為求解單組態RCPSP，其解碼方式為前推式/後推式作業表單串列法（Forward/Backward serial list scheduling，FSLS/BSLS），區域搜尋法為向左向右插入法，最後再加上後推前擠排程法(Backward-forward scheduling method，BF)予以改善解的品質。
透過採用國際測試題庫（PSPLIB）驗證求解效果之後，發現在同樣限制條件（5000個解）下，此兩階段法最大之優點在於不僅是100%且在短時間內即求得可行解，並可在合理的時間內得到良好的求解效果。

關鍵字

多組態資源專案排程 ； 分枝界限法 ； 蟻群最佳化演算法 ； 模擬退火法

並列摘要

In this thesis, we investigate and propose a two-stage method to solve the multi-mode resource-constrained project scheduling problem (MM-RCPSP) with the objective to minimize the project completion time. The feasibility problem of MM-RCPSP is NP-complete when nonrenewable resource types are considered and the optimization problem of MM-RCPSP given a feasible mode assignment (satisfying the nonrenewable constraints) is also NP-hard. In the first stage of our proposed method, branch and bound (B&B) method is employed to find a set of feasible mode assignments. Then a subset of these mode assignments is selected based on smaller critical path values with respect to the project networks resulting from the disjunctive arcs concept. The second stage deals with single-mode RCPSP without nonrenewable resource constraints and two methods, ant colony optimization (ACO) and simulated annealing (SA), are used to find a near-optimal project schedule with respect to each selected feasible mode assignment. In ACO, ants generate schedules by one of the following three methods: forward serial list scheduling (FSLS) method, backward serial list scheduling (BSLS) method, and forward parallel method with MLFT priority rule. In SA, only FSLS and BSLS are used to generate schedules. Both ACO and SA employ two-direction insertion method and backward-forward method (BF) to improve schedules.
The proposed method has two superior advantages. First, it always produces a feasible schedule as long as a given MM-RCPSP instance is feasible. Second, it is capable of finding an optimal or near-optimal solution in acceptably computational time for small and medium size problems. The performance of the two-stage method is evaluated using the standard sets of instances in PSPLIB. Computational results based on 5000 schedules show that this method is competitive among the algorithms currently published.

並列關鍵字

multi-mode resource-constrained project scheduling problem ； branch and bound ； ant colony optimization ； simulated annealing

參考文獻

3. 高文慶，「螞蟻演算法於有限資源專案排程最佳化之研究」，私立元智大學工業工程與管理研究所碩士論文（2004）。

8. 錢明淦，「遺傳演算法應用於具有多種資源組態及資源限制專案計劃排程問題之研究」，私立元智大學工業工程研究所碩士論文（1999）。

9. Ahn, T. and Erenguc, S. S., “The resource constrained project scheduling with multiple crashable modes: A heuristic procedure,” European Journal of Operational Research, 107, 250-259 (1998).

10. Alcaraz, J., Maroto, C. and Ruiz, R., “Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms,” Journal of Operational Research Society, 54, 614-626 (2003).

11. Boctor, F.F., “Heuristics for scheduling projects with resource restrictions and several resource-duration modes,” International Journal of Production Research, 31, 2547-2558 (1993).