Abstract
In this paper, we introduce an extension of the classical Resource-Constrained Project Scheduling Problem: the Multi-skill Project Scheduling Problem. We consider a project made up of activities that must be implemented by a staff: every member of this staff masters one or more skill(s). An activity needs a given amount of each skill with a fixed minimum level of mastering. For each unit of a skill needed, we have to assign an employee who masters the required level of this skill during the whole processing time of the activity. The objective is to minimize the duration of the project, i.e. the makespan. We introduce here two lower bounds used to evaluate the minimum duration.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alvarez-Valdes, R., Martin, G., Tamarit, J.M.: Constructing Good Solutions for a School Timetabling Problem. J. Oper. Res. Soc. 47, 1203–1215 (1996)
Bailey, J.: Optimization and Heuristic Models to Integrate Project Task and Manpower scheduling. Comput. Indust. Eng. 29, 473–476 (1995)
Baptiste, P., Le Pape, C., Nuijten, W.: Satisfiability Tests and Time Bound Adjustments for Cumulative Scheduling Problems. Ann. Oper. Res. 92, 305–333 (1999)
Baptiste, P., Demassey, S.: Tight LP Bounds for Resource Constrained Project Scheduling. OR Spectrum 26, 251–262 (2004)
Bellenguez, O., Néron, E.: An Exact Method for Solving the Multi-skill Project Scheduling Problem. In: Operations Research Conference, Tilburg, pp. 97–98 (2004)
Bellenguez, O., Néron, E.: Methods for Solving the Multi-skill Project Scheduling Problem. In: 9th Int. Workshop on Project Management and Scheduling, Nancy, pp. 66–69 (2004)
Brucker, P., Knust, S.: Lower Bounds for Resource-Constrained Project Scheduling Problems. Eur. J. Oper. Res. 149, 302–313 (2003)
Burke, E.K., De Causmaecker, P., Vanden Berghe, G., Van Landeghem, H.: The State of the Art of Nurse Rostering. J. Scheduling 7, 441–499 (2004)
Dauzère-Pérès, S., Roux, J., Lasserre, J.B.: Multi-resource Shop Scheduling with Resource Flexibility. Eur. J. Oper. Res. 107, 289–305 (1998)
Demassey, S., Artigues, C., Michelon, P.: Constraint-Propagation-Based Cutting Planes: An Application to the Resource-Constrained Project-Scheduling Problem. INFORMS J. Comput. (2003) (in press)
Demeulemeester, E., Herroelen, W.: New Benchmark Results for the Resource-Constrained Project Scheduling Problem. Manage. Sci. 43, 1485–1492 (1997)
De Reyck, B., Herroelen, W.: The Multi-mode Resource-Constrained Project Scheduling Problem with Generalized Precedence Relations. Eur. J. Oper. Res. 119, 538–556 (1999)
Hartmann, S., Drexl, A.: Project Scheduling with Multiple Modes: A Comparison of Exact Algorithms. Networks 32, 283–297 (1998)
Haase, K., Latteier, J., Schirmer, A.: The Course Scheduling Problem at the Lufthansa Technical Training. Eur. J. Oper. Res. 110, 441–456 (1998)
Hanne, T., Nickel, S.: A Multiobjective Evolutionary Algorithm for Scheduling and Inspection Planning in Software Development Projects. Eur. J. Oper. Res. 167, 663–678 (2005)
Josefowska, J., Mika, M., Rozycki, R., Waligora, G., Weglarz, J.: Simulated Annealing for Multi-mode Resource-Constrained Project Scheduling Problem. Ann. Oper. Res. 102, 137–155 (2001)
Klein, R.: Project Scheduling with Time-Varying Resource Constraints. Int. J. Prod. Res. 38, 3937–3952 (2000)
Kolisch, R., Drexl, A.: Local Search for Non-preemptive Multi-mode Resource-Constrained Project Scheduling Problem. IIE Trans. 29, 987–999 (1997)
Kolisch, R., Sprecher, A.: PSPLIB—A Project Scheduling Problem Library. Eur. J. Oper. Res. 96, 205–216 (1997)
Kolisch, R., Sprecher, A.: PSPLIB—A Project Scheduling Problem Library (2000), ftp://ftp.bwl.uni-kiel.de/pub/operations-research/psplib/html/indes.html
Lopez, P., Erschler, J., Esquirol, P.: Ordonnancement de Tâches sous Contraintes: Une Approche Énergétique. RAIRO-APII 26, 453–481 (1992)
Mingozzi, A., Maniezzo, V., Riciardelli, S., Bianco, L.: An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation. Manage. Sci. 44, 714–729 (1998)
Özdamar, L.: A Genetic Algorithm Approach to a General Category Project Scheduling Problem. IEEE Trans. on Systems, Man, and Cybernetics (forthcoming)
Sprecher, A., Drexl, A.: Multi-mode Resource Constrained Project Scheduling Problem by a Simple, General and Powerful Sequencing Algorithm. Eur. J. Oper. Res. 107, 431–450 (1998)
Toroslu, I.: Personnel Assignment Problem with Hierarchical Ordering Constraints. Comput. Indust. Eng, 493–510 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bellenguez, O., Néron, E. (2005). Lower Bounds for the Multi-skill Project Scheduling Problem with Hierarchical Levels of Skills. In: Burke, E., Trick, M. (eds) Practice and Theory of Automated Timetabling V. PATAT 2004. Lecture Notes in Computer Science, vol 3616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11593577_14
Download citation
DOI: https://doi.org/10.1007/11593577_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30705-1
Online ISBN: 978-3-540-32421-8
eBook Packages: Computer ScienceComputer Science (R0)