應用分枝界限法解決資源具有限性下的專案選擇與排程問題

Resource-constrained project selection and scheduling problem using a branch and bound method

尹新瀚(Shin-Han Ying)

指導教授 ： 吳建文

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

https://doi.org/10.6841/NTUT.2009.00625

摘要

近代，專案排程問題是一個相當被重視的問題，許多與該主題有關的研究與文獻相繼地提出，不過早期的排程問題通常假設活動排程時所需要的各種資源數量為無限下的最佳化研究，不過這樣的假設並不符合現實的狀況，因此自60年代提出資源有限下的專案排程問題後，這樣的問題便更受到學者們的重視。
資源有限下的專案排程問題(簡稱RCPSP問題)被證明為一種NP-Hard問題，而在RCPSP問題中使用分枝界限法是一種尋找最佳解的好方法。因此本研究透過列舉與分枝界限法分別解決專案的選擇與排程問題。列舉程序每次列舉一種專案組合，並透過分枝界限法找出該組合的最佳排程解，我們假設該專案的利潤函數與其完成時間有關，在排程完畢後便可得到該組合的最大利潤，透過各組合下的利潤比較得到具有最大利潤的專案組合與規劃結果，供專案經理作為決策依據。而實驗結果亦證明列舉法結合分枝界限法可以獲得較高的利潤。

關鍵字

專案選擇 ； 列舉法 ； 資源有限的專案規劃 ； 分枝界限法

並列摘要

Project scheduling problem is an old well known problem. There is a lot of literature related to this problem. In last forty years, project scheduling problem with resource constraint has attracted more attention to researchers.
Resource-constrained project scheduling problem（RCPSP）has been proved to be a NP-hard problem . Many methods had been used to find the optimal solution . The branch and bound method is one of the efficient methods. In our thesis, we combine an explicit enumeration procedure and the branch and bound method for solving RCPSP and project selection problem simultaneously. In our approach, we enumerate all combinations of projects and use the branch and bound method to schedule the selected projects. In each step of enumeration, we calculate the project profit of this combination. Finally, we can provide maximum profit for decision maker who needs to select the most profitable projects to execute. The experiment result in this paper shows that our approach gives better solution than other heuristic methods.

並列關鍵字

Project scheduling problem ； RCPSP ； Branch and bound method

參考文獻

[5] Alvarez-Valdes, R., and Tamarit, J.M., “Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis”, Advances in project scheduling, 1989, pp.134

[6] Blazewicz, J., Lenstra, J.K., and Rinnooy Kan, A.H.G., “Scheduling subject to resource constraints: Classification and complexity”, Discrete Appl. Math., 1983, vol.5, no.1, pp. 11-24

[7] Boctor, F., “Some efficient multi-heuristic procedures for resource-constrained project scheduling. Euro”, J. Opl. Res, 1990, vol.49, pp. 3-13

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

[9] Brucker, P., Knust, S., Schoo, A., and Thiele, O., ”A branch and bound algorithm for the resource-constrained project scheduling problem”, European Journal of Operational Research, 1998, vol.107, no.2 , pp. 272-288