A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. (English) Zbl 1175.90205

van Peteghem, Vincent; Vanhoucke, Mario

Eur. J. Oper. Res. 201, No. 2, 409-418 (2010).

Summary: We present a genetic algorithm for the multi-mode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. We also introduce the preemptive extension of the problem which allows activity splitting (P-MRCPSP). To solve the problem, we apply a bi-population genetic algorithm, which makes use of two separate populations and extend the serial schedule generation scheme by introducing a mode improvement procedure. We evaluate the impact of preemption on the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that our procedure is amongst the most competitive algorithms.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

project scheduling; genetic algorithm; multi-mode RCPSP; preemption

Software:

Genocop; PSPLIB

References:

[1]	Alcaraz, J.; Maroto, C., A robust genetic algorithm for resource allocation in project scheduling, Annals of operations research, 102, 83-109, (2001) · Zbl 1024.90036
[2]	Alcaraz, J.; Maroto, C.; Ruiz, R., Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms, Journal of the operational research society, 54, 614-626, (2003) · Zbl 1095.90541
[3]	Ballestin, F.; Valls, V.; Quintanilla, S., Pre-emption in resource-constrained project scheduling, European journal of operational research, 189, 1136-1152, (2008) · Zbl 1146.90403
[4]	Bedworth, D.; Bailey, J., Integrated production control systems – management, analysis, design, (1982), Wiley New York
[5]	Blazewicz, J.; Lenstra, J.; Rinnooy Kan, A., Scheduling subject to resource constraints: classification and complexity, Discrete applied mathematics, 5, 11-24, (1983) · Zbl 0516.68037
[6]	Boctor, F., Heuristics for scheduling projects with resource restrictions and several resource-duration modes, International journal of production research, 31, 11, 2547-2558, (1993)
[7]	Boctor, F., An adaption of the simulated annealing for solving resource-constrained project scheduling problems, International journal of production research, 34, 2335-2351, (1996) · Zbl 0930.90041
[8]	Boctor, F., A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European journal of operational research, 90, 349-361, (1996) · Zbl 0916.90143
[9]	Bouleimen, K.; Lecocq, H., A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, European journal of operational research, 149, 268-281, (2003) · Zbl 1040.90015
[10]	Brucker, P.; Drexl, A.; Möhring, R.; Neuman, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European journal of operational research, 112, 3-41, (1999) · Zbl 0937.90030
[11]	Buddhakulsomsiri, J.; Kim, D., Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting, European journal of operational research, 175, 279-295, (2006) · Zbl 1137.90483
[12]	Damay, J.; Quilliot, A.; Sanlaville, E., Linear programming based algorithms for preemptive and non-preemptive rcpsp, European journal of operational research, 182, 1012–1022, (2007) · Zbl 1121.90055
[13]	Debels, D.; Vanhoucke, M., A bi-population based genetic algorithm for the resource-constrained project scheduling problem, Lecture notes on computer science, 3483, 378-387, (2005)
[14]	Debels, D.; Vanhoucke, M., A decomposition-based genetic algorithm for the resource-constrained project-scheduling problem, Operations research, 55, 3, 457-469, (2007) · Zbl 1167.90664
[15]	Debels, D.; De Reyck, B.; Leus, R.; Vanhoucke, M., A hybrid scatter-search/electromagnetism meta-heuristic for the resource-constrained project scheduling problem, European journal of operational research, 169, 3, 638-653, (2006) · Zbl 1079.90051
[16]	Demeulemeester, E.; Herroelen, W., An efficient optimal procedure for the preemptive resource-constrained project scheduling problem, European journal of operational research, 90, 334-348, (1996) · Zbl 0916.90149
[17]	Drexl, A.; Grünewald, J., Nonpreemptive multi-mode resource-constrained project scheduling, IIE transactions, 25, 74-81, (1993)
[18]	Hartmann, S., Project scheduling with multiple modes: A genetic algorithm, Annals of operations research, 102, 111-135, (2001) · Zbl 1024.90039
[19]	Hartmann, S.; Drexl, A., Project scheduling with multiple modes: A comparison of exact algorithms, Networks, 32, 283-297, (1998) · Zbl 1002.90025
[20]	Hartmann, S.; Kolisch, R., Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem, European journal of operational research, 127, 394-407, (2000) · Zbl 0985.90036
[21]	Hartmann, S.; Sprecher, A., A note on hierarchical models for multi-project planning and scheduling, European journal of operational research, 94, 377-383, (1996) · Zbl 0953.90518
[22]	Herroelen, W.; De Reyck, B.; Demeulemeester, E., A classification scheme for project scheduling, (), 1-26
[23]	Holland, H., Adaption in natural and artifical systems, (1975), University of Michigan Press
[24]	Jarboui, B.; Damak, N.; Siarry, P.; Rebai, A., A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems, Applied mathematics and computation, 195, 299-308, (2008) · Zbl 1180.90125
[25]	Jozefowska, J.; Mika, M.; Rozycki, R.; Waligora, G.; Weglarz, J., Simulated annealing for multi-mode resource-constrained project scheduling, Annals of operations research, 102, 137-155, (2001) · Zbl 0990.90513
[26]	Kaplan, L., 1988. Resource-Constrained Project Scheduling with Preemption of Jobs. Ph.D. Thesis, University of Michigan.
[27]	Kelley, J.E., The critical-path method: resources planning and scheduling, (), 347-365
[28]	Knotts, G.; Dror, M.; Hartman, B., Agent-based project scheduling, IIE transactions, 32, 5, 387-401, (2000)
[29]	Kolisch, R., Serial and parallel resource-constrained project scheduling methods revisited: theory and computation, European journal of operational research, 43, 23-40, (1996)
[30]	Kolisch, R.; Drexl, A., Local search for nonpreemptive multi-mode resource-constrained project scheduling, IIE transactions, 29, 987-999, (1997)
[31]	Kolisch, R.; Hartmann, S., Heuristic algorithms for solving the resource-constrained project scheduling problem, (), 147-178
[32]	Kolisch, R.; Hartmann, S., Experimental investigation of heuristics for resource-constrained project scheduling: an update, European journal of operational research, 174, 23-37, (2006) · Zbl 1116.90047
[33]	Kolisch, R.; Sprecher, A., PSPLIB - A project scheduling problem library, European journal of operational research, 96, 205-216, (1996) · Zbl 0947.90587
[34]	Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management science, 41, 1693-1703, (1995) · Zbl 0870.90070
[35]	Li, K.; Willis, R., An iterative scheduling technique for resource-constrained project scheduling, European journal of operational research, 56, 370-379, (1992) · Zbl 0825.90536
[36]	Lova, A.; Tormos, P.; Barber, F., Multi-mode resource constrained project scheduling: scheduling schemes, priority rules and mode selection rules, Inteligencia artificial, 30, 69-86, (2006)
[37]	Lova, A.; Tormos, P.; Cervantes, M.; Barber, F., An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, International journal of production economics, 117, 2, 302-316, (2009)
[38]	Maroto, C.; Tormos, P., Project management: an evaluation of software quality, International transactions in operational research, 1, 209-221, (1994)
[39]	Mori, M.; Tseng, C., A genetic algorithm for multi-mode resource constrained project scheduling problem, European journal of operational research, 100, 134-141, (1997) · Zbl 0947.90589
[40]	Nonobe, K., Ibaraki, T., 2001. Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). Technical Report, Kyoto University. · Zbl 1048.90116
[41]	Özdamar, L., A genetic algorithm approach to a general category project scheduling problem, IEEE transactions on systems, man, and cybernetics, part C: applications and reviews, 29, 44-59, (1999)
[42]	Özdamar, L.; Ulusoy, G., A local constraint based analysis approach to project scheduling under general resource constraints, European journal of operational research, 79, 287-298, (1994) · Zbl 0815.90096
[43]	Patterson, J.; Slowinski, R.; Talbot, F.; Weglarz, J., An algorithm for a general class of precedence and resource constrained scheduling problem, (), 3-28
[44]	Ranjbar, M.; De Reyck, B.; Kianfar, F., A hybrid scatter-search for the discrete time/resource trade-off problem in project scheduling, European journal of operational research, 193, 1, 35-48, (2009) · Zbl 1152.90464
[45]	Slowinski, R., Two approaches to problems of resource allocation among project activities - A comparative study, Journal of operational research society, 8, 711-723, (1980) · Zbl 0439.90042
[46]	Slowinski, R.; Soniewicki, B.; Weglarz, J., DSS for multiobjective project scheduling, European journal of operational research, 79, 220-229, (1994) · Zbl 0815.90099
[47]	Speranza, M.; Vercellis, C., Hierarchical models for multi-project planning and scheduling, European journal of operational research, 64, 312-325, (1993) · Zbl 0779.90046
[48]	Sprecher, A., Resource-constrained project scheduling: exact methods for the multi-mode case, () · Zbl 0809.90084
[49]	Sprecher, A.; Drexl, A., Solving multi-mode resource-constrained project scheduling problems by a simple, general and powerful sequencing algorithm, European journal of operational research, 107, 431-450, (1998) · Zbl 0943.90042
[50]	Sprecher, A.; Hartmann, S.; Drexl, A., An exact algorithm for the project scheduling with multiple modes, OR spektrum, 19, 195-203, (1997) · Zbl 0885.90059
[51]	Talbot, F., Resource-constrained project scheduling with time-resource tradeoffs: the nonpreemptive case, Management science, 28, 10, 1197-1210, (1982) · Zbl 0493.90042
[52]	Tormos, P.; Lova, A., A competitive heuristic solution technique for resource-constrained project scheduling, Annals of operations research, 102, 65-81, (2001) · Zbl 1024.90045
[53]	Valls, V.; Laguna, M.; Lino, P.; Prez, A.; Quintanilla, S., Project scheduling with stochastic activity interruptions, (), 333-354
[54]	Valls, V.; Ballestin, F.; Quintanilla, S., Justification and RCPSP: A technique that pays, European journal of operational research, 165, 2, 375-386, (2005) · Zbl 1066.90045
[55]	Valls, V.; Ballestín, F.; Quintanilla, S., A hybrid genetic algorithm for the resource constrained project scheduling problem, European journal of operational research, 185, 2, 495-508, (2008) · Zbl 1137.90526
[56]	Vanhoucke, M.; Debels, D., The impact of various activity assumptions on the lead time and resource utilization of resource-constrained projects, Computers and industrial engineering, 54, 140-154, (2008)
[57]	Vanhoucke, M.; Coelho, J.; Debels, D.; Maenhout, B.; Tavares, L., An evaluation of the adequacy of project network generators with systematically sampled networks, European journal of operational research, 187, 2, 511-524, (2008) · Zbl 1149.90066
[58]	Zhang, H.; Tam, C.; Li, H., Multimode project scheduling based on particle swarm optimization, Computer-aided civil and infrastructure engineering, 21, 93-103, (2006)
[59]	Zhu, G.; Bard, J.; Tu, G., A branch-and-cut procedure for the multimode resource-constrained project-scheduling problem, Journal on computing, 18, 3, 377-390, (2006) · Zbl 1241.90168