Flexible Heuristics for Project Scheduling with Limited Resources

Resource-constrained project scheduling is an NPhard optimisation problem. There are many different heuristic strategies how to shift activities in time when resource requirements exceed their available amounts. These strategies are frequently based on priorities of activities. In this paper, we assume that a suitable heuristic has been chosen to decide which activities should be performed immediately and which should be postponed and investigate the resource-constrained project scheduling problem (RCPSP) from the implementation point of view. We propose an efficient routine that, instead of shifting the activities, extends their duration. It makes it possible to break down their duration into active and sleeping subintervals. Then we can apply the classical Critical Path Method that needs only polynomial running time. This algorithm can simply be adapted for multiproject scheduling with limited resources.

Authors:

• Miloš Šeda

Keywords:

• Project management
• resource-constrained scheduling
• NP-hard problem
• CPM
• heuristic method.

References:

[1] C. Artigues, P. Michelon and S. Reusser, "Insertion Techniques for
Static and Dynamic Resource-Constrained Project Scheduling,"
European Journal of Operational Research, vol. 149, pp. 249-267,
2003.
[2] A. Azaron, C. Perkgoz and M. Sakawa, "A Genetic Algorithm for the
Time-Cost Trade-off in PERT Networks," Applied Mathematics and
Computation, vol. 168, pp. 1317-1339, 2005.
[3] J. Blazewicz, K.H. Ecker, G. Schmidt and J. Weglarz, Scheduling
Computer and Manufacturing Processes. Berlin: Springer-Verlag, 1996.
[4] K. Bouleimen and H. Lecocq, "A new Efficient Simulated Annealing
Algorithm for the Resource-Constrained Project Scheduling Problem
and Its Multiple Mode Version," European Journal of Operational
Research, vol. 149, pp. 268-281, 2003.
[5] P. Brucker, A. Drexl, R. Möhring, K. Neumann and E. Pesch,
"Resource-Constrained Project Scheduling: Notation, Classification,
Models, and Methods," European Journal of Operational Research, vol.
112, pp. 3-41, 1999.
[6] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to
Algorithms. Cambridge, Massachusetts: MIT Press, 2001.
[7] S.E. Elmaghraby, Activity Networks: Project Planning and Control by
Network Models. New York: John Wiley & Sons, 1977.
[8] W. Herroelen, E. Demeulemeester and B.D. Reyck, "A Note on the
Paper "Resource-Constrained Project Scheduling: Notation,
Classification, Models, and Methods" by Brucker et al," European
Journal of Operational Research, vol. 128, pp. 679-688, 2001.
[9] K.W. Kim, M. Gen and G. Yamazaki, "Hybrid Genetic Algorithm with
Fuzzy Logic for Resource-Constrained Project Scheduling," Applied
Soft Computing, vol. 2/3F, pp. 174-188, 2003.
[10] K.W. Kim, Y.S. Yun, J.M. Yoon, M. Gen and G. Yamazaki, "Hybrid
Genetic Algorithm with Adaptive Abilities for Resource-Constrained
Multiple Project Scheduling," Computers in Industry, vol. 56, pp. 143-
160, 2005.
[11] J. Klapka, J. Dvoř├ík and P. Popela. Methods of Operational Research
(in Czech). Brno: VUTIUM, 2001.
[12] M. Mika, G. Walig├│ra and J. Weglarz, "Simulated Annealing and Tabu
Search for Multi-Mode Resource-Constrained Project Scheduling with
Positive Discounted Cash Flows and Different Payment Models,"
European Journal of Operational Research, vol. 164, pp. 639-668,
2005.
[13] L.-Y. Tseng and S.-C. Chen, "A Hybrid Metaheuristic for the Resource-
Constrained Project Scheduling Problem," European Journal of
Operational Research, 2005, article in press.
[14] V. Valls, S. Quintanilla and F. Ballestin, "Resource-Constrained Project
Scheduling: A Critical Activity Reordering Heuristic," European
Journal of Operational Research, vol. 149, pp. 282-301, 2003.
[15] H. Zhang, X. Li, H. Li and F. Huang, "Particle Swarm Optimization-
Based Schemes for Resource-Constrained Project Scheduling,"
Automation in Construction, vol. 14, pp. 393-404, 2005.