模擬退火法於利潤最大化多資源限制專案排程問題解算效果之分析

Simulated Annealing Heuristics for the Resource constrained Project Scheduling Problem to Maximize Profit within a Specified Deadline

吳思輝(Sih - Huei Wu)

指導教授 ： 徐旭昇

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

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

摘要

本研究提出以模擬退火法為架構之數種啟發式演算法來求解多資源限制專案排程問題，目標為專案總利潤最大化。論文採用國際測試題庫PSPLIB作業20、30、60之問題結構，並制定一套機制產生各作業之利潤做為測試題。論文將研究範圍分為二部分：(1) 建立數學模式，並結合ILOG CPLEX與Visual C++ 6.0求出作業數20之最佳解，以作為所提出演算法之效果測試標竿；(2)提出六種不同模擬退火法求解多資源限制專案排程於利潤最大化問題，其編碼方式採用權重利潤(Weighted profit；WP)，解碼方式則為作業表單序列法(Serial list scheduling method)，模擬退火法每個溫階之鄰近解則以移動搜尋法產生，同時對每溫階之最佳鄰近解使用前推回擠法(Forward backward improvement；FBI)進一步改善解之品質。本研究在作業數少(20)之測試題使用CPLEX所得之最佳解值做為演算法效果測試標竿；對於較大作業數(30、60)問題，則採用CPM上限值作為演算法效果測試標竿。
本研究所提出之六種模擬退火演算法，皆可以在很短時間內求出作業20之最佳解或近似最佳解。在作業數30與60之測試題，則以加入禁制表單(Tabu list)之依標準差變動降溫之模擬退火法與調適溫度(Adaptive)模擬退火法求解效果為最佳。另由實驗結果得知大多數結構參數相同之問題，其演算法之最佳參數值相同；僅有少數結構參數問題為不同，但其間之誤差並不顯著。

關鍵字

多資源限制專案排程 ； 模擬退火法 ； 禁制表單

並列摘要

In this thesis we propose a simple and flexible payment model for the resource constrained project scheduling problem (RCPSP) with the objective of maximizing the total net present value of the profit at the specified deadline. This payment model is NP-hard since it is equivalent to an RCPSP of which the goal is to minimize total weighted completion time. This problem will be proven to be NP-hard in the strong sense in this research. A mathematical model to this problem is presented and solved optimally with ILOG CPLEX 9.0 on a problem size of 20-activity instances generated by using PROGEN and an activity profit counting formula presented in the research. Besides the mathematical formulation, three simulated annealing (SA) procedures with distinct cooling schemes are proposed in an attempt to solve medium to large problem size instances: (1) geometric decreasing (SA1), (2) decreasing level depending on the variation of solutions in the last temperature (SA2), and (3) decreasing level depending on the number of consecutive failures to improve the current solution (SA3). All the SAs generate a neighboring solution by the Insertion Move method followed by the well known Forward-Backward Improvement procedure. The research also analyzes the effects on the solution quality when a tabu list is added to these SA heuristics.
Our experiments indicate that ILOG CPLEX takes considerable computational time for hard instances of 20-activity. Such hard instances require various types of resources with highly limited capacity. The experiments shows that the proposed SA algorithms often optimally solve these small size instances in a short computational time.
For testing the performance of the SA heuristics on medium to large size problems, the instances of j30.sm and j60.sm in the PSPLIB are taken with each activity profit being generated by our formula. The solutions obtained by the critical path method (CPM) are used as an upper bound for making performance comparisons between the proposed SA heuristics. The numerical results show that both SA2 and SA3 with a tabu list outperform the others. We also conducted an experiment to investigate whether the best parameter settings of these SA heuristics for a set of problems will also be the best for another set of problems with the same structure. The result indicates that the best parameter settings are often identical for a pair set of test instances with the same problem structure.

並列關鍵字

Resource constrained project scheduling ； 0-1 integer programming ； Simulated annealing ； Payment scheduling method ； Discount rate

參考文獻

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

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

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).

Aarts, E., Korst, J., “Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and Neural Computing,” John Wiley and Sons, (1989).

Azizi, N. and Zolfaghrai, S., “ Adaptive temperature control for simulated annealing: a comparative study,” Computers and Operations Research, 31, 2439-2451 (2004).