集束搜尋法求解可變作業強度之資源限制專案排程

A Beam Search Method for Resource Constrained Project Scheduling with Variable Intensity Operation

王俊軒(Chun-Hsuan Wang)

指導教授 ： 洪一峯

國立清華大學/工學院/工業工程與工程管理學系/碩士(2008年)

https://doi.org/10.6843/NTHU.2008.00388

摘要

This study proposes three approaches to solve single project, nonpreemptive infinite mode RCPSP in which resources are renewable and the intensity of each activity is fixed within the activity duration. The objective of the problem is to minimize project makespan. A piecewise linear curve is proposed to approximate the continuous, nonlinear relations between the duration and the intensity of an activity. Such a project scheduling problem is called approximated problem in this study. There are two parts of decision in our problem. One is to determine a good event sequence. There are three approaches - enumerative approach, beam search approach, multiple-run Boctor approach - proposed in this study for this part. The other one is to determine the duration and the intensity of all activities that minimize project makespan under a given event sequence. This study proposes a linear programming formulation to find the optimal solution. Based on the statistical analysis of the experiments, the control parameters of beam search approach are proposed. Enumerative approach (Wu (2007)) is able to obtain optimal solution for approximated problems. However, the solution time of enumerative approach is too long when the problem size is relatively large. Thus, the second approach, beam search, is proposed to solve this problem to obtain good solution within reasonable solution time. The multiple-run Boctor approach can solve this problem the most efficiently among the three approaches but the solution quality is the worst.

關鍵字

專案排程 ； 作業強度 ； 資源限制 ； 線性規劃 ； 窮舉法 ； 集束搜尋法 ； 片段線性曲線 ； 啟發式演算法

並列摘要

本研究提出三種方法求解單一專案、作業不可中斷性的無限作業執行模式之資源限制專案排程問題，專案中每一個作業之作業強度在執行期間是不可變動且資源可重覆使用，目標在於最小化專案的總完工時間。我們提出片段線性曲線去近似作業執行時間與作業強度所構成的連續型非線性曲線關係，若專案排程問題利用片段線性曲線去近似非線性曲線關係，在本研究中我們稱之為近似問題。第一種方法：分枝窮舉法，能夠得到近似問題的最佳解，然而隨著問題大小的增加，分枝窮舉法的求解時間也會急劇上升，因此本研究提出第二種方法：集束搜尋法搭配Boctor【1996】演算法與吳【2007】線性規劃來求解本問題，希望能在合理的時間內得到一個不錯的專案排程解。但是對於大型問題來說，集束搜尋法仍然不夠有效率，故本研究提出第三種方法：複次Boctor演算法，能夠非常有效率的求解大型專案問題，但所求出的專案排程解也相對地較差。根據實驗與統計分析，我們可以決定集束搜尋法的控制參數，並比較三種方法的求解效率與求解結果。

並列關鍵字

Project scheduling ； Activity intensity ； Resource constraint ； Linear programming ； Enumeration ； Beam search ； Piecewise linear curve ； Heuristics

參考文獻

吳俊炘 (2007)，「利用線性規劃求解可變作業強度之專案排程問題」，國立清華大學工業工程與工程管理學系碩士論文。

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

Boctor, F. F., 1996. A new and efficient heuristic for scheduling projects with resource restrictions and multipleple execution modes. European Journal of Operational Research 90, 349-361.

Kis, T., 2005. A branch-and-cut algorithm for scheduling of projects with variable intensity activities. Mathematical Programming 103, 515-539.

Kogan, K. and Shtub A., 1999. Scheduling projects with variable-intensity activities: The case of dynamic earliness and tardiness costs. European Journal of Operational Research 118, 65-80.