Abstract
A fundamental assumption in the basic RCPSP is that activities in progress are non-preemptable. Some papers reveal the potential benefits of allowing activity interruptions in the schedule when the objective is the makespan minimization. In this chapter we consider the Maxnint_PRCPSP in which it is assumed that activities can be interrupted at any integer time instant with no cost incurred, that each activity can be split into a maximum number of parts, and that each part has a minimum duration established. We show how some procedures developed for the RCPSP can be adapted to work with the Maxnint_PRCPSP and we introduce some procedures specifically designed for this problem. Furthermore, precedence relationships between activities can refer to portions of work content or periods of time. In single-modal project scheduling when interruption is not allowed, both are equivalent but not when preemption is considered. We present a study of generalized work and time precedence relationships and all conversions amongst them.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ballestín F, Valls V, Quintanilla S (2008) Preemption in resource-constrained project scheduling. Eur J Oper Res 189:1636–1152
Ballestín F, Valls V, Quintanilla S (2009) Scheduling projects with limited number of preemptions. Comput Oper Res 36:2913–2925
Ballestín F, Barrios A, Valls V (2013) Looking for the best modes helps solving the MRCPSP/max. Int J Prod Res 51:813–827
Bartusch M, Möhring RH, Radermacher FJ (1988) Scheduling project networks with resource constraints and time windows. Ann Oper Res 16:201–240
Błażewicz J, Lenstra JK, RinooyKan AHG (1983) Scheduling subject to resource constraints: classification and complexity. Discrete Appl Math 5:11–24
Demeulemeester E, Herroelen W (1996) An efficient optimal procedure for the preemptive resource-constrained project scheduling problem. Eur J Oper Res 90:334–48
Demeulemeester E, Herroelen W (2002) Project scheduling: a research handbook. Kluwer Academic, Norwell
Hartmann, S (1998) A competitive genetic algorithm for resource-constrained project scheduling. Nav Res Logist 45:733–750
Hartmann S, Kolisch R (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur J Oper Res 127:394–407
Kaplan LA (1988) Resource-constrained project scheduling with pre-emption of jobs. Unpublished Ph.D. dissertation, University of Michigan, Ann Arbor
Kaplan LA (1991) Resource-constrained project scheduling with setup times. Unpublished paper, Department of Management, University of Tennessee, Knoxville
Kolisch R, Hartmann S (2006) Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur J Oper Res 174(1):23–37
Kolisch R, Sprecher A, Drexl A (1995) Characterization and generation of a general class of resource-constrained project scheduling problems. Manag Sci 41:1693–703
Li F, Lai Ch, Shou Y (2011) Particle swarm optimization for preemptive project scheduling with resource constraints. In: Proceedings of the IEEM 2011. IEEE, Singapore, pp 869–871
Michalewicz Z (1994) Genetic algorithms + data structures = evolution programs. Springer, New York
Neumann K, Schwindt C, Zimmermann J (2003) Project scheduling with time windows and scarce resources. Springer, Berlin
Patterson JH (1984) A comparison of exact procedures for solving the multiple constrained resource project scheduling problem. Manag Sci 30(7):854–867
Quintanilla S, Pérez A, Lino P, Valls V (2012) Time and work generalised precedence relationships in project scheduling with pre-emption: an application to the management of service centres. Eur J Oper Res 219:59–72
Valls V, Ballestín F, Quintanilla S (2005) Justification and RCPSP: a technique that pays. Eur J Oper Res 165(2):375–386
Valls V, Ballestín F, Quintanilla S (2008) A hybrid genetic algorithm for the resource-constrained project scheduling problem. Eur J Oper Res 85(2):495–508
Van Peteghem V, Vanhoucke M (2010) A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem. Eur J Oper Res 201:409–418
Acknowledgements
This research was partially supported by Ministerio de Ciencia e Innovación, MTM2011-23546.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Quintanilla, S., Lino, P., Pérez, Á., Ballestín, F., Valls, V. (2015). Integer Preemption Problems. In: Schwindt, C., Zimmermann, J. (eds) Handbook on Project Management and Scheduling Vol.1. International Handbooks on Information Systems. Springer, Cham. https://doi.org/10.1007/978-3-319-05443-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-05443-8_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05442-1
Online ISBN: 978-3-319-05443-8
eBook Packages: Business and EconomicsBusiness and Management (R0)