Abstract
In the past decades, resource parameters have been introduced in project scheduling literature to measure the scarceness of resources of a project instance. In this paper, we incorporate these resource scarceness parameters in the search process to solve the multi-mode resource constrained project scheduling problem, in which multiple execution modes are available for each activity in the project. Therefore, we propose a scatter search algorithm, which is executed with different improvement methods, each tailored to the specific characteristics of different renewable and nonrenewable resource scarceness values. Computational results prove the effectiveness of the improvement methods and reveal that the procedure is among the best performing competitive algorithms in the open literature.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alcaraz, J., Maroto, C., Ruiz, R.: Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. J. Oper. Res. Soc. 54, 614–626 (2003)
Alvarez-Valdes, R., Tamarit, J.: Heuristic algorithms for resource-constrained project scheduling: A review and empirical analysis. In: Slowinski, R., Weglarz, J. (eds.) Advances in Project Scheduling. Elsevier, Amsterdam (1989)
Blazewicz, J., Lenstra, J., Rinnooy Kan, A.: Scheduling subject to resource constraints: Classification and complexity. Discrete Appl. Math. 5, 11–24 (1983)
Boctor, F.: Heuristics for scheduling projects with resource restrictions and several resource-duration modes. Int. J. Prod. Res. 31, 2547–2558 (1993)
Boctor, F.: A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes. Eur. J. Oper. Res. 90, 349–361 (1996a)
Boctor, F.: Resource-constrained project scheduling by simulated annealing. Int. J. Prod. Res. 34, 2335–2351 (1996b)
Bouleimen, K., Lecocq, H.: A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur. J. Oper. Res. 149, 268–281 (2003)
Brucker, P., Drexl, A., Möhring, R., Neumann, K., Pesch, E.: Resource-constrained project scheduling: notation, classification, models, and methods. Eur. J. Oper. Res. 112, 3–41 (1999)
Buddhakulsomsiri, J., Kim, D.: Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting. Eur. J. Oper. Res. 178, 374–390 (2007)
Cooper, D.: Heuristics for scheduling resource-constrained projects: an experimental investigation. Manag. Sci. 22, 1186–1194 (1976)
Debels, D., Vanhoucke, M.: A bi-population based genetic algorithm for the RCPSP. Lect. Notes Comput. Sci. 3483, 378–387 (2005)
Demeulemeester, E., Vanhoucke, M., Herroelen, W.: A random network generator for activity-on-the-node networks. J. Sched. 6, 13–34 (2003)
Drexl, A., Grünewald, J.: Nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 25, 74–81 (1993)
Glover, F., Laguna, M., Marti, R.: Fundamentals of scatter search and path relinking. Control Cybern. 29, 653–684 (2000)
Hartmann, S.: A competitive genetic algorithm for resource-constrained project scheduling. Nav. Res. Logist. 45, 733–750 (1998)
Hartmann, S.: Project scheduling with multiple modes: A genetic algorithm. Ann. Oper. Res. 102, 111–135 (2001)
Heilmann, R.: Resource-constrained project scheduling: A heuristic for the multi-mode case. OR Spektrum 23, 335–357 (2001)
Herroelen, W., De Reyck, B.: Phase transitions in project scheduling. J. Oper. Res. Soc. 50, 148–156 (1999)
Herroelen, W., Demeulemeester, E., De Reyck, B.: A classification scheme for project scheduling problem. In: Weglarz, J. (ed.) Project Scheduling—Recent Models, Algorithms and Applications, pp. 1–26. Kluwer Academic, Dortrecht (1999)
Jarboui, B., Damak, N., Siarry, P., Rebai, A.: A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Appl. Math. Comput. 195, 299–308 (2008)
Józefowska, J., Mika, M., Rózycki, R., Waligóra, G., Weglarz, J.: Simulated annealing for multi-mode resource-constrained project scheduling. Ann. Oper. Res. 102, 137–155 (2001)
Kelley, J.: The Critical-path Method: Resources Planning and Scheduling. Prentice-Hall, New Jersey (1963)
Knotts, G., Dror, M., Hartman, B.: Agent-based project scheduling. IIE Trans. 32(5), 387–401 (2000)
Kolisch, R., Drexl, A.: Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 29, 987–999 (1997)
Kolisch, R., Hartmann, S.: Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Oper. Res. 174, 23–37 (2006)
Kolisch, R., Sprecher, A.: PSPLIB—a project scheduling problem library. Eur. J. Oper. Res. 96, 205–216 (1996)
Kolisch, R., Sprecher, A., Drexl, A.: Characterization and generation of a general class of resource-constrained project scheduling problems. Manag. Sci. 41, 1693–1703 (1995)
Lova, A., Tormos, P., Barber, F.: Multi-mode resource constrained project scheduling: scheduling schemes, priority rules and mode selection rules. Intel. Artif. 30, 69–86 (2006)
Lova, A., Tormos, P., Cervantes, M., Barber, F.: An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. Int. J. Prod. Econ. 117, 302–316 (2009)
Marti, R., Laguna, M., Glover, F.: Principles of scatter search. Eur. J. Oper. Res. 169, 359–372 (2006)
Mastor, A.: An experimental and comparative evaluation of production line balancing techniques. Manag. Sci. 16, 728–746 (1970)
Montgomery, D.C.: Design and Analysis of Experiments. Wiley, New York (2005)
Mori, M., Tseng, C.: A genetic algorithm for the multi-mode resource constrained project scheduling problem. Eur. J. Oper. Res. 100, 134–141 (1997)
Nonobe, K., Ibaraki, T.: Formulation and tabu search algorithm for the resource constrained project scheduling problem. In: Ribeiro, C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics. Kluwer Academic, Dordrecht (2002)
Özdamar, L.: A genetic algorithm approach to a general category project scheduling problem. IEEE Trans. Syst. Man Cybern. 29, 44–59 (1999)
Özdamar, L., Ulusoy, G.: A local constraint based analysis approach to project scheduling under general resource constraints. Eur. J. Oper. Res. 79, 287–298 (1994)
Patterson, J.: Project scheduling: The effects of problem structure on heuristic scheduling. Nav. Res. Logist. 23, 95–123 (1976)
Pinol, H., Beasley, J.: Scatter search and bionomic algorithms for the aircraft landing problem. Eur. J. Oper. Res. 171, 439–462 (2006)
Ranjbar, M., De Reyck, B., Kianfar, F.: A hybrid scatter-search for the discrete time/resource trade-off problem in project scheduling. Eur. J. Oper. Res. 193, 35–48 (2009)
Slowinski, R., Soniewicki, B., Weglarz, J.: DSS for multi-objective project scheduling subject to multiple-category resource constraints. Eur. J. Oper. Res. 79, 220–229 (1994)
Sprecher, A.: Resource-constrained Project Scheduling: Exact Methods for the Multi-mode Case. Lecture Notes in Economics and Mathematical Systems. Springer, Berlin (1994)
Sprecher, A.: Scheduling resource-constrained projects competitively at modest memory requirements. Manag. Sci. 46, 710–723 (2000)
Sprecher, A., Drexl, A.: Multi-mode resource-constrained project scheduling with a simple, general and powerful sequencing algorithm. Eur. J. Oper. Res. 107, 431–450 (1998)
Sprecher, A., Hartmann, S., Drexl, A.: An exact algorithm for project scheduling with multiple modes. OR Spektrum 19, 195–203 (1997)
Stinson, J., Davis, E., Khumawala, B.: Multiple resource-constrained scheduling using branch-and-bound. IIE Trans. 10, 252–259 (1978)
Tseng, L.Y., Chen, S.C.: Two-phase genetic local search algorithm for the multimode resource-constrained project scheduling problem. IEEE Trans. Evol. Comput. 13, 848–857 (2009)
Van Peteghem, V., Vanhoucke, M.: A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problems. Eur. J. Oper. Res. 201, 409–418 (2010)
Vanhoucke, M., Coelho, J., Debels, D., Maenhout, B., Tavares, L.: An evaluation of the adequacy of project network generators with systematically sampled networks. Eur. J. Oper. Res. 187, 511–524 (2008)
Zhang, H., Tam, C., Li, H.: Multi-mode project scheduling based on particle swarm optimization. Comput.-Aided Civ. Infrastruct. Eng. 21, 93–103 (2006)
Zhu, G., Bard, J., Tu, G.: A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem. J. Comput. 18(3), 377–390 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Van Peteghem, V., Vanhoucke, M. Using resource scarceness characteristics to solve the multi-mode resource-constrained project scheduling problem. J Heuristics 17, 705–728 (2011). https://doi.org/10.1007/s10732-010-9152-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-010-9152-0