×

Justification and RCPSP: a technique that pays. (English) Zbl 1066.90045

Summary: The objective of this paper is to show that justification is a simple technique that can be easily incorporated in diverse algorithms for the resource-constrained project scheduling problem–improving the quality of the schedules generated without generally requiring more computing time. The results of incorporating this technique in 22 different algorithms are shown. Fifteen of the new algorithms that use double justification outperform seven of the best heuristic algorithms that do not use justification. The tests have been performed on the standard test set j120 for the RCPSP generated using ProGen.

MSC:

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

Software:

PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

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] Ballestı́n, F., 2001. Nuevos métodos de resolución del problema de secuenciación de proyectos con recursos limitados, Ph.D. Thesis, Departamento de Estadı́stica e Investigación Operativa, Universidad de Valencia, Spain; Ballestı́n, F., 2001. Nuevos métodos de resolución del problema de secuenciación de proyectos con recursos limitados, Ph.D. Thesis, Departamento de Estadı́stica e Investigación Operativa, Universidad de Valencia, Spain
[3] 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
[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 and bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational Research, 107, 272-288 (1998) · Zbl 0970.90030
[6] 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
[7] Dorndorf, U.; Pesch, E.; Phan-Huy, T., A branch-and-bound algorithm for the resource-constrained project scheduling problem, Mathematical Methods of Operations Research, 52, 413-439 (2000) · Zbl 1023.90024
[8] Drexl, A., Scheduling of project networks by job assignment, Management Science, 37, 1590-1602 (1991) · Zbl 0729.91011
[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., A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistic, 49, 433-448 (2002) · Zbl 1013.90062
[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 and Production Management, 13, 11, 80-91 (1993)
[13] Kelley, J. E., The critical-path method: Resources planning and scheduling, (Muth, J. F.; Thompson, G. L., Industrial Scheduling (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), 347-365
[14] Klein, R., Scheduling of resource-constrained projects (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0949.90042
[15] Klein, R.; Scholl, A., Scattered branch and bound: An adaptive search strategy applied to resource-constrained project scheduling, Central European Journal of Operations Research, 7, 177-201 (1999) · Zbl 0940.90035
[16] Kolich, R., 1995. Project scheduling under resource constraints-efficient heuristics for several problem classes, Phisica-Verlag, Heidelberg; Kolich, R., 1995. Project scheduling under resource constraints-efficient heuristics for several problem classes, Phisica-Verlag, Heidelberg
[17] 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
[18] 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, MA), 147-178
[19] Kolisch, R.; Padman, R., An integrated survey of deterministic project scheduling, Omega, 29, 249-272 (2001)
[20] Kolisch, R., Sprecher, A., 1997. PSPLIB-A project scheduling library, European Journal of Operational Research 96, 205-216. (downloadable from http://www.bwl.uni-kiel.de/Prod/psplib/index.html; Kolisch, R., Sprecher, A., 1997. PSPLIB-A project scheduling library, European Journal of Operational Research 96, 205-216. (downloadable from http://www.bwl.uni-kiel.de/Prod/psplib/index.html · Zbl 0947.90587
[21] 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
[22] 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
[23] Merkle, D., Middendorf, M., Schmeck, H., 2000. Ant colony optimization for resource-constrained project scheduling. In: Proceedings of the Genetic and Evolutionary Computation Conference, Las Vegas, NV, 2000, pp. 893-900; Merkle, D., Middendorf, M., Schmeck, H., 2000. Ant colony optimization for resource-constrained project scheduling. In: Proceedings of the Genetic and Evolutionary Computation Conference, Las Vegas, NV, 2000, pp. 893-900
[24] 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
[25] Möhring, R. H.; Schulz, A. S.; Stork, F.; Uetz, M., Solving project scheduling problems by minimum cut computations, Management Science, 49, 3, 330-350 (2003) · Zbl 1232.90213
[26] Nonobe, K.; Ibaraki, T., Formulation and Tabu search algorithm for the resource constrained project scheduling problem (RCPSP), (Ribeiro, C. C.; Hansen, P., Essays and Surveys in Metaheuristics (2001), Kluwer Academic Publishers), 557-588 · Zbl 1048.90116
[27] Özdamar, L.; Ulusoy, G., A survey on the resource-constrained project scheduling problem, AIIE Transactions, 27, 574-586 (1995)
[28] Ö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
[29] Sprecher, A., Solving the RCPSP efficiently at modest memory requirements, Management Science, 46, 5, 710-723 (2000) · Zbl 1231.90217
[30] 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
[31] 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
[32] Valls, V.; Quintanilla, S.; Ballestı́n, F., Resource-constrained project scheduling: A critical activity reordering heuristic, European Journal of Operational Research, 149, 2, 282-301 (2003) · Zbl 1032.90011
[33] Valls, V., Ballestı́n, F., Quintanilla, S., 2004. A population-based approach to the resource-constrained project scheduling problem, Annals of Operations Research, in press; Valls, V., Ballestı́n, F., Quintanilla, S., 2004. A population-based approach to the resource-constrained project scheduling problem, Annals of Operations Research, in press
[34] Wiest, J. D., Some properties of schedules for large projects with limited resources, Operations Research, 12, 3, 395-418 (1964)
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.