A Generalized Heuristic Learning Approach to Project Scheduling Problems with Resource Constraints

通化型啓發式學習法於專案資源需求排程問題之研究

10.29977/JCIIE.200805.0002

許蒞彥(Li-Yen Shue)；李昇暾(Sheng-Tun Li)

專案排程 ； 啓發式學習法 ； 回溯法 ； 人工智慧 ； Project scheduling ； Heuristic learning ； Backtracking ； Artificial intelligence

工業工程學刊

25卷3期（2008 / 05 / 01）

204 - 214

英文

本論文提出一套通化型啟發式學習演算法，並探討其在專案資源需求排程問題上的應用。此一演算法的特色在於其完整的啟發式學習搜尋過程：狀態選擇、啟發式學習以及搜尋路徑的評估，且能提供持續改善狀態選擇決策的能力。藉由啟發式學習的門檻值，該演算法允許使用者設定其可接受的解，最佳解或近似最佳解的品質。對於專案排程的解法則植基於排程過程中專案活動狀態的特性與資源的可用率。此解法由狀態、狀態轉換運算子、啟發式估測以及狀態轉換的成本等所組成。本研究並以Patterson的110問題爲實證研究對象，以驗證所提出的啟發式學習法於排程問題求解之績效。

We present a generalized heuristic learning algorithm and a solution approach for its implementation in solving project scheduling problems with resource constraints. The search process of the algorithm is characterised by the complete heuristic learning process: state selection, heuristic learning, and search path review. The heuristic learning process enables the algorithm to continue to improve the state selection decision. The heuristic learning threshold of the algorithm allows users to specify solution quality, optimal or near-optimal solutions, with efficient computation. The implementation approach is based on the dynamic nature of activity status and resource availability of a project. It consists of states, state transition operator, heuristic estimate, and the cost of transition between states. The performance analysis of this algorithm with Patterson's 110 problem is presented.

1. Baker, K. R.(1974).Introduction to Sequencing and Scheduling.New York:Wiley.
2. Bell, C. E.,K. Park(1990).Solving resource-constrained project scheduling problems by A* search.Naval Research Logistics,37,280-318.
3. Bell, C.,J. Han(1991).A new heuristic search method in resource-constrained project scheduling.Naval Research Logistics,38,315-331.
4. Blazewicz, J.,J. K. Lenstra,A. H. G. Rinnooy Kan(1983).Scheduling projects to resource constraints: classification and complexity.Discrete Applied Mathematics,5,11-24.
5. Brucker, P.,A. Drexl,R. Mohring,K. Neumann,E. Pesch(1999).Resource-constrained project schedulintg: notation, classification, models, and methods.European Journal of Operational Research,112,3-41.
6. Brucker, P.,S. Knust(2003).Lower bounds for resource-constrained project scheduling problems.European Journal of Operational Research,149,268-281.
7. Christofides, N.,R. Alvarez-Valdes,J. M. Taramit(1987).Project scheduling with resource constraints: a branch and bound approach.European Journal of Operational Research,29,262-273.
8. Davis, E. W.,G. E. Heidorn(1971).An algorithm for optimal project scheduling under multiple resource constraints.Management Science,17,803-816.
9. Demeulemeester, E.,W. Herroelen(1992).A branch-and-bound procedure for the multiple resource constrained project scheduling problems.Management Science,38,1803-1818.
10. Demeulemeester, E.,W. Herroelen(2002).Project Scheduling-A Research Handbook.Boston:Kluwer Academic.
11. Demeulemeester, E.,W. Herroelen,W. Simpson,S. Baroum,J. Patterson,K. Yang(1994).On a paper by Christofides et al. for solving the multiple-resource constrained single project scheduling problem.European Journal of Operational Research,76,218-228.
12. Elmaghraby, S. E.(1995).Activity nets: a guided tour through some recent developments.European Journal of Operational Research,82,383-408.
13. Franch, S.(1982).Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop.New York:Wiley.
14. Hartmann, S.,R. Kolisch(2000).Experimental evaluation of state-of-the-art heuristics for the resourceconstrained project scheduling problem.European Journal of Operational Research,127,394-407.
15. Kolisch, R.,R. Padman(2001).An integrated survey of deterministic project scheduling.Omega,29,249-272.
16. Kolisch, R.,S. Hartmann(2006).Experimental investigation of heuristics for Resource-Constrained Project scheduling: An update.European Journal of Operational Research,174,23-37.
17. Korf, R.(1990).Real time heuristic search.Journal of Artificial Intelligence,42,189-211.
18. Nilsson, N. J.(1982).Principle of Artificial Intelligence.NewYork:Springer-Verlag.
19. Patterson, J. H.(1984).A comparison of exact approaches for solving the multi-constrained resource project scheduling.Management Science,30,854-867.
20. Patterson, J. P.,F. Talbot,R. Slowinski,J. Weglarz(1990).Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems.European Journal of Operational Research,49,68-79.
21. Rinnooy Kan A. H. G.(1976).Machine Scheduling Problems: Classification, Complexity and Computations.Holland:Martinus Nijhoff.
22. Sampson, S.,E. Weiss(1993).Local search techniques for the resource constrained project scheduling problem.Naval Research Logistics,40,665-675.
23. Schrage, L.(1970).Solving resource-constrained network problems by implicit enumeration-non preemptive case.Operations Research,18,263-278.
24. Stinson, J. P.,E. W. David,B. M. Khumawala(1978).Multiple resource-constrained scheduling using branch and bound.AIIE Transactions,3,91-98.
25. Sung, C. S.,S. K. Lim(1997).A scheduling procedure for a general class of resource-constrained project.Computers & Industrial Engineering,32,9-17.
26. Talbot, F. B.,J. H. Patterson(1978).An efficient integer programming algorithm with network cuts for solving resource-constrained scheduling problems.Management Science,24,1163-1174.
27. Wang, J.(2005).Constraint-based schedule repair for product development projects with time-limited constraints.International Journal of Production Economics,95,399-414.
28. Zamani, R.,L. Shue(1998).Solving project scheduling problems with a heuristic learning algorithm.Journal of the Operational Research Society,49,709-716.
29. Zhang, H.,H. Li,C. M. Tam(2006).Particle swarm optimization for resource-constrained project scheduling.International Journal of Project Management,24,83-92.