Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. (English) Zbl 0985.90036

Hartmann, Sönke; Kolisch, Rainer

Eur. J. Oper. Res. 127, No. 2, 394-407 (2000).

Summary: We consider heuristic algorithms for the resource-constrained project scheduling problem. Starting with a literature survey, we summarize the basic components of heuristic approaches. We briefly describe so-called \(X\)-pass methods which are based on priority rules as well as metaheuristic algorithms. Subsequently, we present the results of our in-depth computational study. Here, we evaluate the performance of several state-of-the-art heuristics from the literature on the basis of a standard set of test instances and point out to the most promising procedures. Moreover, we analyze the behavior of the heuristics with respect to their components such as priority rules and metaheuristic strategy. Finally, we examine the impact of problem characteristics such as project size and resource scarceness on the performance.

MSC:

90B35	Deterministic scheduling theory in operations research
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

resource-constrained project scheduling; heuristics; experimental evaluation

Software:

SPSS; PSPLIB

References:

[1]	Alvarez-Valdés, R.; Tamarit, J.M., Algoritmos heurísticos deterministas y aleatorios en secuenciacón de proyectos con recursos limitados, Qüestiió, 13, 173-191, (1989) · Zbl 1167.90499
[2]	Alvarez-Valdés, R.; Tamarit, J.M., Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis, (), 113-134
[3]	Baar, T.; Brucker, P.; Knust, S., Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem, (), 1-8 · Zbl 1074.90563
[4]	Boctor, F.F., Some efficient multi-heuristic procedures for resource-constrained project scheduling, European journal of operational research, 49, 3-13, (1990) · Zbl 1403.90305
[5]	K. Bouleimen, H. Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem, Technical Report, Service de Robotique et Automatisation, Université de Liège, 1998 · Zbl 1040.90015
[6]	Brucker, P.; Drexl, A.; Möhring, R.; Neumann, K.; Pesch, E., Resource-constrained project scheduling: notation, classification, models, and methods, European journal of operational research, 112, 1, 3-41, (1999) · Zbl 0937.90030
[7]	Cho, J.-H.; Kim, Y.-D., A simulated annealing algorithm for resource constrained project scheduling problems, Journal of the operational research society, 48, 735-744, (1997) · Zbl 0881.90069
[8]	Conway, R.W.; Maxwell, W.L.; Miller, L.W., Theory of scheduling, (1967), Addison-Wesley Reading, MA · Zbl 1058.90500
[9]	Cooper, D.F., Heuristics for scheduling resource-constrained projects: an experimental investigation, Management science, 22, 11, 1186-1194, (1976) · Zbl 0326.90029
[10]	Davis, E.W.; Patterson, J.H., A comparison of heuristic and optimum solutions in resource-constrained project scheduling, Management science, 21, 944-955, (1975)
[11]	Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval research logistics, 45, 733-750, (1998) · Zbl 0936.90024
[12]	Herroelen, W.; Demeulemeester, E.; De Reyck, B., Resource-constrained project scheduling - A survey of recent developments, Computers & operations research, 25, 4, 279-302, (1998) · Zbl 1040.90525
[13]	Icmeli, O.; Erenguc, S.S.; Zappe, C.J., Project scheduling problems: A survey, International journal of operations & production management, 13, 11, 80-91, (1993)
[14]	Kohlmorgen, U.; Schmeck, H.; Haase, K., Experiences with fine-grained parallel genetic algorithms, Annals of operations research, 90, 203-219, (1999) · Zbl 0937.90092
[15]	Kolisch, R., Project scheduling under resource constraints – efficient heuristics for several problem classes, (1995), Physica Heidelberg
[16]	Kolisch, R., Efficient priority rules for the resource-constrained project scheduling problem, Journal of operations management, 14, 3, 179-192, (1996)
[17]	Kolisch, R., Serial and parallel resource-constrained project scheduling methods revisited: theory and computation, European journal of operational research, 90, 320-333, (1996) · Zbl 0916.90151
[18]	Kolisch, R.; Drexl, A., Adaptive search for solving hard project scheduling problems, Naval research logistics, 43, 23-40, (1996) · Zbl 0870.90069
[19]	Kolisch, R.; Hartmann, S., Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis, (), 147-178
[20]	R. Kolisch, R. Padman, An integrated survey of deterministic project scheduling, Technical Report 463, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, 1997
[21]	Kolisch, R.; Schwindt, C.; Sprecher, A., Benchmark instances for project scheduling problems, (), 197-212
[22]	Kolisch, R.; Sprecher, A., PSPLIB - a project scheduling problem library, European journal of operational research, 96, 205-216, (1996) · Zbl 0947.90587
[23]	Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management science, 41, 10, 1693-1703, (1995) · Zbl 0870.90070
[24]	Lee, J.-K.; Kim, Y.-D., Search heuristics for resource constrained project scheduling, Journal of the operational research society, 47, 678-689, (1996) · Zbl 0863.90090
[25]	Leon, V.J.; Ramamoorthy, B., Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling, OR spektrum, 17, 2/3, 173-182, (1995) · Zbl 0842.90062
[26]	Li, R.K.-Y.; Willis, J., An iterative scheduling technique for resource-constrained project scheduling, European journal of operational research, 56, 370-379, (1992) · Zbl 0825.90536
[27]	Naphade, K.S.; Wu, S.D.; Storer, R.H., Problem space search algorithms for resource-constrained project scheduling, Annals of operations research, 70, 307-326, (1997) · Zbl 0893.90093
[28]	Norušis, M.J., The SPSS guide to data analysis, (1990), SPSS Inc Chicago
[29]	Özdamar, L.; Ulusoy, G., A survey on the resource-constrained project scheduling problem, IIE transactions, 27, 574-586, (1995)
[30]	Özdamar, L.; Ulusoy, G., A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and willis, European journal of operational research, 89, 400-407, (1996) · Zbl 0922.90087
[31]	E. Pinson, C. Prins, F. Rullier, Using tabu search for solving the resource-constrained project scheduling problem, in: Proceedings of the Fourth International Workshop on Project Management and Scheduling, Leuven, 1994, pp. 102-106
[32]	Sampson, S.E.; Weiss, E.N., Local search techniques for the generalized resource constrained project scheduling problem, Naval research logistics, 40, 665-675, (1993) · Zbl 0776.90039
[33]	A. Schirmer, Case-based reasoning and improved adaptive search for project scheduling, Technical Report 472, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, 1998 · Zbl 0956.90011
[34]	A. Schirmer, S. Riesenberg, Parameterized heuristics for project scheduling – biased random sampling methods, Technical Report 456, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, 1997
[35]	Sprecher, A.; Kolisch, R.; Drexl, A., Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem, European journal of operational research, 80, 94-102, (1995) · Zbl 0927.90054
[36]	Stinson, J.P.; Davis, E.W.; Khumawala, B.M., Multiple resource-constrained scheduling using branch and bound, AIIE transactions, 10, 252-259, (1978)
[37]	Thomas, P.R.; Salhi, S., An investigation into the relationship of heuristic performance with network-resource characteristics, Journal of the operational research society, 48, 1, 34-43, (1997) · Zbl 0881.90076
[38]	Thomas, P.R.; Salhi, S., A tabu search approach for the resource constrained project scheduling problem, Journal of heuristics, 4, 2, 123-139, (1998) · Zbl 0913.90184
[39]	Ulusoy, G.; Özdamar, L., Heuristic performance and network/resource characteristics in resource-constrained project scheduling, Journal of the operational research society, 40, 12, 1145-1152, (1989) · Zbl 0687.90048