多組態資源限制專案排程-最小成本組態選擇問題解算之研究

Hybrid Evolutionary Algorithms for the Multi-Mode ResourceConstrained Project Scheduling Problem with the Objective of Minimizing Execution Cost within a Due Date

雷鵬遠(pong yeng Lei)

指導教授 ： 徐旭昇

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

https://doi.org/10.6838/YZU.2007.00137

摘要

承包商是否接受一項專案，執行成本與完工期限為兩項重要考慮因素。同時，承包商可依其經驗與資料對專案中對每個作業產生數個執行方式(組態)，然後選擇其一去執行，藉以符合顧客之要求並降低專案總花費成本。本研究即針對此情況加以研究，假設顧主與承包商皆已決定專案完工期限，且承包商已對專案中各作業皆計算出數種可執行組態，在有限制資源下，尋找最小成本專案組態(即各作業之執行組態)及其對應之一個專案作業排程，在規定期限內完成專案。
本研究針對上述問題分成兩情況探討：(1)問題一：假設專案中作業皆須使用一至數種不可恢復資源某些單位，但此類資源僅納入作業成本計算，此類型資源並無單期使用量及專案總使用量限制；因此這問題為多組態可恢復資源限制專案排程問題，目標為上段所述。(2)問題二：專案各作業之不可恢復資源不僅皆須計算成本，但有專案使用量總額限制，此問題目標與問題一相同。
針對問題一，本研究提出三種演算法：(1)分枝界限法結合Memetic演算法 (B&B-MA)；(2)基因演算子演算法結合Memetic演算法(GO-MA)；(3)基因演算子演算法結合模擬退火法(GO-SA)。上述演算法中，第一部份名稱(B&B與GO)定位在專案組態搜尋方式，第二部份(MA與SA)則為各作業組態已指定下之專案排程演算法。三個演算法中，B&B-MA可求得最佳或近似最佳解，且效果頗為穩健，然計算時間較長；GO-MA與GO-SA皆能在短時間求得近似最佳解，但演算法效果解之品質與穩健度不如B&B-MA。
問題二亦使用GO-MA與B&B-MA，但須加檢驗專案組態是否符合不可恢復資源限制。同時本研究對問題二另提出二種演算法：(1)分枝界限法結合模擬退火法(B&B-SA)；(2)分枝界限法接續基因演算子演算法結合Memetic 演算法 (B&B-GO-MA)，B&B-GO為先使用分枝界限法搜尋組態後將優良資訊傳遞給基因演算子演算法繼續搜尋。
演算法效果之測試採用國際測試題庫(PSPLIB)之多組態測試題為基本，對每測試題利用所建立之規則產生各類型資源單位成本，如此便可產生測試題作業各組態之執行成本。實驗以各演算法對每題求解十次，做統計分析比較。實驗結果顯示：(1)於問題一，B&B-MA求解中小型問題(j10.mm ~ j20.mm)效果最佳且穩定，於大型問題(j30.mm)其求解時間常無法被使用者接受。(2)於問題二，中小型問題仍屬B&B-MA求解品質最佳，但其求解時間過長，推測大型問題已無法使用；因此本研究於中大型問題使用B&B-GO-MA，此方法可維持求解品質，除部分題目誤差較大外，求解時間顯著減少也較穩定。此外本研究發現，增加不可恢復資源成本之比重時，問題一與問題二所求得最佳解之相同比率增加，反之則下降。

關鍵字

多組態資源限制專案排程問題 ； 分枝界限法 ； Memetic演算法 ； 模擬退

並列摘要

Project execution cost and committed due date are two significant factors for a contractor to consider when determining the profitability of a project. In practice, a contractor can usually create several alternatives (modes) to execute each activity of the project. In this thesis, we consider two multi-mode resource constrained project scheduling problems with the objective of minimizing the project execution cost within a specified deadline. Both problems consider the total usage of non-renewable resources in the project as a part of their objective functions, but the second problem (Problem 2) also imposes these resources to the model as constraints while Problem 1 does not.
Three hybrid evolutionary algorithms are developed for Problem 1: (1) Branch and Bound with Memetic Algorithm (B&B-MA), (2) Genetic Operators with Memetic Algorithm (GO-MA), and (3) Genetic Operators with Simulated Annealing (GO-SA). For each algorithm, the first abbreviation (B&B or GO) refers to the means of selecting a project mode assignment, and the second abbreviation represents the method used to find a feasible project schedule with respect to a given project mode assignment. Four simple but powerful thresholds are used to shorten the computational time for B&B-MA, including the feasibility test for resource and due date, and the branch advancing test and the project mode assignment scheduling test based on cost criteria. The well-known BF method is used to refine each offspring in MA and each neighboring solution in SA. The algorithm B&B-MA is designed to provide optimal or near-optimal solutions for test instances.
Four hybrid evolutionary algorithms are developed for Problem 2: (1) B&B-MA, (2) GO-MA, (3) B&B-SA, and (4) B&B-GO-MA. Unlike the methods used for solving Problem 1, these four algorithms place one more step in checking if the non-renewable constraints are satisfied. Algorithm B&B-SA is similar to B&B-MA except the project scheduling method given a project mode assignment uses simulated annealing. Finally, algorithm B&B-GO-MA is designed to reduce computational time while at the same time maintaining the searching effectiveness.
The performances of these proposed algorithms were tested through the multi-mode benchmark instances in the PSPLIB, using a rule to generate the cost of each activity mode. In the experiment, each instance was run ten times. For both Problems 1 and 2, our experimental results show that B&B-MA is very robust and works efficiently for all test instances between j10.mm and j20.mm, but its computational time for j30.mm is quite long. For Problem 1, GO-MA and GO-SA are very efficient in solving instances from j10.mm to j30.mm, but the robustness and the quality of their solutions appear to decrease as the problem size increases. For Problem 2, B&B-MA is not practical for j30.mm due to unacceptable computational time, but B&B-GO-MA produces promising solutions for most instances in an acceptable computational time. Finally, our numerical results with B&B-MA on test instances j14.mm indicate that raising the cost of non-renewable resources will result in the increase of the identical best solutions found by B&B-MA for the two problems in the test instance set.

並列關鍵字

Project scheduling ； Multi-mode ； Branch and bound method ； Memetic algorithms ； Simulated annealing ； PSPLIB

參考文獻

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

4. Alcaraz, J. and Maroto, C., “A robust genetic algorithm for resource allocation in project scheduling”, Annals of Operations Research, 102, 83-109 (2001).

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

6. Baroum, R.B. and Patterson, J.H., “An exact solution procedure for maximizing the net present value of a project”, Weglarz J. (Eds.), in Handbook on Recent Advances in Project Scheduling, Kluwer Academic Publishers, 1999.

8. Bouleimen, K. and Lecocq, H., 2003. “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version”, European Journal of Operational Research, 149, 268-281 (2003).