Pre-emption in resource-constrained project scheduling. (English) Zbl 1146.90403

Ballestín, Francisco; Valls, Vicente; Quintanilla, Sacramento

Eur. J. Oper. Res. 189, No. 3, 1136-1152 (2008).

Summary: The Resource-Constrained Project Scheduling Project (RCPSP), together with some of its extensions, has been widely studied. A fundamental assumption in this basic problem is that activities in progress are non-preemptable. Very little effort has been made to uncover the potential benefits of discrete activity pre-emption, and the papers dealing with this issue have reached the conclusion that it has little effect on project length when constant resource availability levels are defined. In this paper we show how three basic elements of many heuristics for the RCPSP - codification, serial SGS and double justification - can be adapted to deal with interruption. The paper is mainly focussed on problem 1_PRCPSP, a generalization of the RCPSP where a maximum of one interruption per activity is allowed. However, it is also shown how these three elements can be further adapted to deal with more general pre-emptive problems. Computational experiments on the standard j30 and j120 sets support the conclusion that pre-emption does help to decrease project length when compared to the no-interruption case. They also prove the usefulness of the justification in the presence of pre-emption. The justification is a RCPS technique that can be easily incorporated into a wide range of algorithms for the RCPSP, increasing their solution quality - maintaining the number of schedules calculated.

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

resource constrained project scheduling; heuristic algorithms; pre-emption; double justification; serial SGS

References:

[1]	Ballestín, F. (2002). Nuevos métodos de resolución del problema de secuenciación de proyectos con recursos limitados. Unpublished PhD Dissertation, Universidad de Valencia.
[2]	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
[3]	Bock, D.B.; Patterson, J.H., A comparison of due date setting, resource assignment and job preemption heuristics for the multiproject scheduling problem, Decision sciences, 21, 387-402, (1990)
[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, 11, 3-41, (1999) · Zbl 0937.90030
[5]	Crandall, K.C., Project planning with precedence lead/lag factors, Project management quarterly, 4, 3, 18-27, (1973)
[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]	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
[8]	Demeulemeester, E.; Herroelen, W., Project scheduling - A research handbook, International series in operations research and management science, vol. 49, (2002), Kluwer Academic Publishers · Zbl 1059.90068
[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., Project scheduling under limited resources: models, methods, and applications, Lecture notes in economics and mathematical systems, vol. 478, (1999), Springer Berlin, Germany · Zbl 0957.90059
[11]	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
[12]	Herroelen, W.; Demeulemeester, E.; De Reyck, B., Resource-constrained project scheduling: A survey of recent developments, Computers and operations research, 25, 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]	Kaplan, L.A. (1988). Resource-constrained project scheduling with preemption of jobs. Unpublished PhD Dissertation, University of Michigan.
[15]	Kaplan, L.A. (1991). Resource-constrained project scheduling with setup times. Unpublished paper, Department of Management, University of Tenessee, Knoxville.
[16]	Kolisch, R. (1995) Project Scheduling under resource constraints - Efficient heuristics for several problem classes, Phisica, 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.; Padman, R., An integrated survey of deterministic project scheduling, Omega, 29, 249-272, (2000)
[19]	Lino, P. (1997). Planificación de Proyectos en Diagramas de Precedencias. Unpublished PhD Dissertation, Universidad de Valencia.
[20]	Neumann, K.; Schwindt, C.; Zimmermann, J., Project scheduling with time windows and scarce resources, (2003), Springer · Zbl 1059.90001
[21]	Özdamar, L.; Ulusoy, G., A survey on the resource-constrained project scheduling problem, AIIE transactions, 27, 574-586, (1995)
[22]	Patterson, J.H., A comparison of exact procedures for solving the multiple constrained resource project scheduling problem, Management science, 30, 7, 854-867, (1984)
[23]	Slowinski, R., Two approaches to problems of resource allocation among project activities - A comparative study, Journal of the operational research society, 31, 8, 711-723, (1980) · Zbl 0439.90042
[24]	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
[25]	Tsubakitani, S.; Deckro, R.F., A heuristic for multiproject scheduling with limited resources in the housing industry, European journal of operational research, 49, 80-91, (1990) · Zbl 06908676
[26]	Valls, V., Ballestín, F., Quintanilla, S. (2002). An hybrid genetic algorithm for the RCPSP. Technical Report, Departamento de Estadística e Investigación Operativa, Universidad de Valencia.
[27]	Valls, V.; Ballestín, F.; Quintanilla, S., Justification and RCPSP: A technique that pays, European journal of operational research, 165, 375-386, (2005) · Zbl 1066.90045
[28]	()
[29]	Weglarz, J., Project scheduling with continuously-divisible, doubly constrained resources, Management science, 27, 9, 1040-1053, (1981) · Zbl 0467.90033
[30]	Wiest, J.D., Some properties of schedules for large projects with limited resources, Operations research, 12, 395-418, (1964)