×

Resource-constrained project scheduling: A critical activity reordering heuristic. (English) Zbl 1032.90011

Summary: We present a new metaheuristic algorithm for the resource-constrained project-scheduling problem. The procedure is a non-standard implementation of fundamental concepts of tabu search without explicitly using memory structures embedded in a population-based framework. The procedure makes use of a fan search strategy to intensify the search, whereas a strategic oscillation mechanism loosely related to the forward/backward technique provides the necessary diversification. Our implementation employs the topological order (TO) representation of schedules. To explore the TO vector space we introduce three types of moves, two of them based on the concept of relative criticality, and a third one based on multi-pass sampling ideas. The strategic utilisation of probabilities for move construction is another distinguishing feature of our approach. Extensive computational testing with more than 2000 problem instances shows the merit of the proposed solution method.

MSC:

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

Software:

PSPLIB; Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Blazewicz, J.; Lenstra, J. K.; Rinooy Kan, A. H.G, Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5, 11-24 (1983) · Zbl 0516.68037
[2] Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 2, 154-160 (1994) · Zbl 0807.90060
[3] Bouleimen, K., Lecocq, H., 1998. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem, Technical Report, Service de Robotique et Automatisation, Université de Liège; Bouleimen, K., Lecocq, H., 1998. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem, Technical Report, Service de Robotique et Automatisation, Université de Liège · Zbl 1040.90015
[4] 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, 3-41 (1999) · Zbl 0937.90030
[5] Brucker, P.; Knust, S.; Schoo, A.; Thiele, O., A branch & bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research, 107, 272-288 (1998) · Zbl 0970.90030
[6] Cho, J. H.; Kim, Y. D., A simulated annealing algorithm for resource constrained project scheduling problems, Journal of Operational Research Society, 48, 736-744 (1997) · Zbl 0881.90069
[7] Demeulemeester, E.; Herroelen, W., A branch-and-bound procedure for the multiple resource-constrained project scheduling problem, Management Science, 38, 1803-1818 (1992) · Zbl 0761.90059
[8] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers · Zbl 0930.90083
[9] Hartmann, S., A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics, 45, 733-750 (1998) · Zbl 0936.90024
[10] 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, 2, 394 (2000), 407 · Zbl 0985.90036
[11] Herroelen, W.; De Reyck, B.; Demeulemeester, E., Resource-constrained project scheduling: A survey of recent developments, Computers and Operations Research, 25, 4, 279-302 (1998) · Zbl 1040.90525
[12] Icmeli, O.; Erenguc, S. S.; Zappe, C. J., Project scheduling problems: A survey, International Journal of Operations & Production Management, 13, 11, 80-91 (1993)
[13] Klein, R.; Scholl, A., Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling, European Journal of Operational Research, 112, 322-346 (1999) · Zbl 0938.90030
[14] Kolisch, R.; Hartmann, S., Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis, (Weglarz, J., Project Scheduling. Recent Models, Algorithms and Applications (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 147-178
[15] Kolisch, R., Padman, R., 1997. An integrated survey of project scheduling, Technical report 463, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel; Kolisch, R., Padman, R., 1997. An integrated survey of project scheduling, Technical report 463, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel
[16] Kolish, R.; Sprecher, A., PSPLIB-A project scheduling library, European Journal of Operational Research, 96, 205-216 (1997) · Zbl 0947.90587
[17] Kolish, 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
[18] 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
[19] Leon, V. J.; Ramamoorthy, B., Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling, OR Spektrum, 17, 173-182 (1995) · Zbl 0842.90062
[20] 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
[21] Mingozzi, A.; Maniezzo, V.; Ricciardelli, S.; Bianco, L., An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation, Management Science, 44, 714-729 (1998) · Zbl 1004.90036
[22] 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
[23] Nonobe, K., Ibaraki, T., 1999. Formulation and Tabu search algorithm for the resource constrained project scheduling problem (RCPSP), Technical report 99010; Nonobe, K., Ibaraki, T., 1999. Formulation and Tabu search algorithm for the resource constrained project scheduling problem (RCPSP), Technical report 99010 · Zbl 1048.90116
[24] Özdamar, L.; Ulusoy, G., A survey on the resource-constrained project scheduling problem, AIIE Transactions, 27, 574-586 (1995)
[25] Özdamar, L.; Ulusoy, G., An iterative local constraint based analysis for solving the resource constrained project scheduling problem, Journal of Operations Management, 14, 193-208 (1996)
[26] Sprecher, A., 1996. Solving the RCPSP efficiently at modest memory requirements, Technical report 425, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel; Sprecher, A., 1996. Solving the RCPSP efficiently at modest memory requirements, Technical report 425, Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel
[27] 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
[28] Storer, R. H.; Wu, S. D.; Vaccari, R., New search paces for sequencing problems with application to job shop scheduling, Management Science, 38, 1495-1509 (1992) · Zbl 0759.90048
[29] Valls, V.; Laguna, M.; Lino, P.; Pérez, A.; Quintanilla; S, Project Scheduling with Stochastic Activity Interruptions, (Weglarz, J., Project Scheduling. Recent Models, Algorithms and Applications (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 333-354
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.