考慮資源限制與穩健性之專案排程研究

On Project Scheduling with Respect to Resources Constrained and Robust

黃榮華(Rong-Hwa Huang) ； 楊長林(Chang-Lin Yang) ； 劉士豪(Shih-Hao Liu)

《輔仁管理評論》 15卷3期 (2008/09) Pp. 1-33

https://doi.org/10.29698/FJMR.200809.0001

摘要

在有限資源的專案排程問題(resource constrained project scheduling problem, RCPSP)中，普遍存在一個事實，對於已經計劃好的排程，常會受到一些不可控制的因素干擾而延工，使得專案往往無法在承諾的完工時間之內完成。本研究將穩健性(robustness)的觀念引入有限資源專案排程中，動態(dynamic)賦予平行作業先後順序，並衡量平行作業集合中各作業活動的寬裕時間(slack time)，藉以篩選出寬裕時間獨立性較大的排程方案，以有效縮短專案延工率。
本研究針對作業活動的持續時間(duration)可能在專案計畫實際運作的過程中發生變動，而導致延工的問題，提出了一套求解架構，嘗試將平行作業的排工順序與非平行作業分離，採用禁忌搜尋演算法(tabu search algorithm, tabu)配合ACTIM法則選擇的起始解，在平行作業發生資源衝突時，搜尋出最適作業排程，以更高之穩健性降低專案的延工率。演算法之資料測試係取自題庫PSPLIB (project scheduling problem library)所提供的四種不同作業數(30、60、90、120)類型之問題。考慮三種不同增幅之作業時間，分別在資源限制爲10單位與15單位狀態下，共測試了720組樣本，所有問題的求解品質皆優於單純使用ACTIM法則之結果。

關鍵字

有限資源專案排程問題 ； 穩健排程 ； 禁忌搜尋法

並列摘要

A common problem in project management is that planned schedules are often disrupted by some uncontrollable factors like additional job duration. As a result, project managers are often unable to meet their promised completion dates. To aim that, we introduced the concept of schedule robustness and find the more robustness plan by finding job independent slack to less the extra cost of undesirable conditions happen like rework cost.
In this paper, we designed a bi-objective function which is not only considered the make span of the project, but al so robustness to less extra cost of delay work.
We used the meta-algorithms which combined tabu-search algorithm and ACTIM to test the data of PSPLIB (project scheduling problem library) with two-factor experiment design and compared with only use ACTIM. The result of computation based on 720 schedules show that our meta-algorithms is more effective than currently published based on ACTIM rule.

並列關鍵字

resource-constrained project scheduling problem ； robustness scheduling ； tabu-search algorithm

參考文獻

蔡登茂(1996)。有限資源多專案排程啓發法之績效評估及應用。技術學刊。11(4)，547-562。

Al-Fawzan, M. A.,Haouari M.(2005).A Bi-objective Model for Robust Resource-constrained Project Scheduling.International Journal of Production Economics.96,175-187.

Baar, T. P. Brucker,Knust, S.,S. Voss,S. Martello,I. Osman,C. Roucairol (Eds.)(1998).Tabu-search Algorithms and Lower Bounds for the Resource-constrained Project Scheduling Problem, Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization.Boston:Kluwer.

Bedworth, D. D.(1973).Industrial System: Planning: Analysis and Control.New York:The Ronald Press Co..

Boctor, F. F.(1990).Some Efficient Multi-heuristic Processdures for Resource-constrained Project Scheduling.European Journal of Operational Research.49,3-13.