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

On Project Scheduling with Respect to Resources Constrained and Robust

10.29698/FJMR.200809.0001

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

有限資源專案排程問題 ； 穩健排程 ； 禁忌搜尋法 ； resource-constrained project scheduling problem ； robustness scheduling ； tabu-search algorithm

輔仁管理評論

15卷3期（2008 / 09 / 01）

1 - 33

繁體中文

在有限資源的專案排程問題(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.

1. 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.
2. 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.
3. Bedworth, D. D.(1973).Industrial System: Planning: Analysis and Control.New York:The Ronald Press Co..
4. Boctor, F. F.(1990).Some Efficient Multi-heuristic Processdures for Resource-constrained Project Scheduling.European Journal of Operational Research,49,3-13.
5. Bowers, J. A.(2000).Interpreting Float in Resource Constrained Projects.International Journal of Project Management,18,385-392.
6. Brand, J. D.,Meyer, W. L.,Shaffer, L. R.(1964).Civil Engineering Studies Report.Urbana, IL:Department of Civil Engineering, University of Illinois.
7. Davis, E. W.,Patterson, J. H.(1975).A Comparison of Heuristic and Optimum Solutions in Resource-constrained Project Scheduling.Management Science,21,944-955.
8. Dell`Amico, M.,Trubian, M.(1993).Applying Tabu Search to the Job-shop Scheduling Problem.Annals of Operations Research,41,231-252.
9. Dorn, J.,Girsch, M.,Skele G.,Slany, W.(1998).Comparison of Iterative Improvement Techniques for Schedule Optimization.European Journal of Operational Research,94,349-361.
10. Glover, F.(1986).Future Path for Integer Programming and Links to Artificial Intelligence.Computers and Operations Research,13,533-549.
11. Glover, F.,Laguna, M.(1997).Kluwer Academic Publishers.Boston/Dordrecht/London:
12. Kelley, J. E.(1963).The Critical Path Method: Resources Planning and Scheduling.New Jersey:Ch. 21 in Industrial scheduling, Prentice-Hall, Englewood Cliffs.
13. Kincaid, R. K.(1993).Minimizing Distortion in Truss Structures: A Comparison of Simulated Annealing and Tabu Search.Structural Optimization,5,217-224.
14. Kurtulus, I. S.,Davis, E. W.(1982).Multi-project Scheduling: Categorization of Heuristics Rules Performance.Management Science,28(2),161-172.
15. Kurtulus, I. S.,Narula, S. C.(1986).Multi-project Scheduling: Analysis of Project Performance.IIE Transactions,17(1),58-66.
16. Lee, I.(2001).Artificial Intelligence Search Methods for Multi-machine Two-stage Scheduling with Due Date Penalty, Inventory, and Machining Costs.Computers and Operations Research,28,835-852.
17. Lee, J. K.,Kim, Y. D.(1996).Search Heuristics for Resource Constrained Project Scheduling.Journal of the Operational Research Society,47,678-689.
18. Malek, M.,Guruswamy, M.,Pandya, M.(1989).Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem.Annals of Operations Research,21,59-84.
19. Manoharan, S.,Shanmuganathan, S.(1999).A Comparison of Search Mechanisms for Structural Optimization.Computers and Structures,73,363-372.
20. Marett, R.,Wright, M.(1996).A Comparison of Neighborhood Search Techniques for Multi-objective Combinatorial Problems.Computers and Operations Research,23(5),465-483.
21. Murata, T.,Ishibuchi, H.(1994).Performance Evaluation of Genetic Algorithms for Flowshop Scheduling Problems.IEEE Transactions
22. Nonobe, K.,Ibaraki, T.,Ribeiro, CC.,Hansen, P. (Ed.)(2002).Essays and surveys in metaheuristics.Kluwer Academic.
23. Patterson, J. H.,Huber, W. D.(1974).A Horizon-varying Zero-one Approach to Project Scheduling.Management Science,20(6),990-998.
24. Patterson, J. H.,Slowinski, R.,Talbot, F. B.,Weglarz, J.(1990).Computational Experience with A Back-tracking Algorithm for Solving a General Class of Precedence and Resource Constrained Scheduling Problems.European Journal of Operational Research,49,68-79.
25. Pirlot, M.(1996).General Local Search Methods.European Journal of Operational Research,92,493-511.
26. Sinclair, M.(1993).Comparison of the Performance of Modern Heuristics for Combinatorial Optimization on Real Data.Computers and Operations Research,20(7),687-695.
27. Taillard, E. D.(1990).Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem.European Journal of Operational Research,47,65-74.
28. Talbot, F. B.(1982).Resource-constrained Project Scheduling with Time-resource Tradeoffs: the Non-preemptive Case.Management Science,28,1197-1210.
29. Talbot, F. B.,Patterson, J. H.(1978).An Efficient Integer Programming Algorithm for Solving Resource Constrained Scheduling Problem.Management Science,24(11),1163-1174.
30. Wang, J.(2005).Constraint-based Schedule Repair for Product Development Projects with Time-limited Constraints.International Journal of Production Economics,95,399-414.
31. Widmer, M.,Hertz, A.(1989).A New Heuristic Method for the Flow Shop Sequencing Problem.European Journal of Operational Research,41,186-193.
32. Wiest, J. D.(1967).A Heuristic Model for Scheduling Large Projects with Limited Resources.Management Science,13,359-377.
33. 蔡登茂(1996)。有限資源多專案排程啓發法之績效評估及應用。技術學刊，11(4)，547-562。