Abstract
The Multi-Skill Project Scheduling Problem is a variant of the well-studied Resource Constrained Project Scheduling Problem, in which the resources are assumed to be multi-skilled. Practical applications of this problem occur when the resources considered are a multi-skilled workforce or multi-purpose machines. This variant introduces a set of assignment decisions between the resources and activities, further to the usual scheduling decisions. This additional layer of complexity results in the problem becoming far more difficult to solve. We investigate different constraint programming models and searches tailored for solvers with nogood learning. These models and searches are then evaluated on instances available from the literature as well as newly generated ones. Using the best performing model and search, we are able to close at least 87 open instances from the literature.
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
Almeida, B.F., Correia, I., Saldanha-da Gama, F.: An instance generator for the multi-skill resource-constrained project scheduling problem (2015). https://ciencias.ulisboa.pt/sites/default/files/fcul/unidinvestig/cmaf-cio/SGama.pdf. Accessed 26 Apr 2017
Almeida, B.F., Correia, I., Saldanha-da Gama, F.: Priority-based heuristics for the multi-skill resource constrained project scheduling problem. Expert Syst. Appl. 57, 91–103 (2016)
Artigues, C., Demassey, S., Néron, E.: Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications. ISTE/Wiley, Hoboken (2008)
Bellenguez-Morineau, O.: Methods to solve multi-skill project scheduling problem. 4OR 6(1), 85–88 (2008)
Bellenguez-Morineau, O., Néron, E.: A branch-and-bound method for solving multi-skill project scheduling problem. RAIRO - Oper. Res. 41(2), 155–170 (2007)
Chu, G.G.: Improving Combinatorial Optimization. Ph.D. thesis, The University of Melbourne (2011). http://hdl.handle.net/11343/36679
Correia, I., Saldanha-da-Gama, F.: A modeling framework for project staffing and scheduling problems. In: Schwindt, C., Zimmermann, J. (eds.) Handbook on Project Management and Scheduling Vol.1. IHIS, pp. 547–564. Springer, Cham (2015). doi:10.1007/978-3-319-05443-8_25
Correia, I., Loureno, L.L., Saldanha-da Gama, F.: Project scheduling with flexible resources: formulation and inequalities. OR Spectr. 34(3), 635–663 (2012)
Dhib, C., Kooli, A., Soukhal, A., Néron, E.: Lower bounds for a multi-skill project scheduling problem. In: Klatte, D., Lüthi, H.J., Schmedders, K. (eds.) OR 2011. ORP, pp. 471–476. Springer, Heidelberg (2012)
Feydy, T., Goldwaser, A., Schutt, A., Stuckey, P.J., Young, K.D.: Priority search with MiniZinc. In: ModRef 2017: The Sixteenth International Workshop on Constraint Modelling and Reformulation at CP2017 (2017)
Hartmann, S., Briskorn, D.: A survey of variants and extensions of the resource-constrained project scheduling problem, Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA) (2008). https://ideas.repec.org/p/zbw/hsbawp/022008.html
Kolisch, R., Sprecher, A.: PSPLIB - a project scheduling problem library. Eur. J. Oper. Res. 96(1), 205–216 (1997)
Kreter, S., Schutt, A., Stuckey, P.J.: Modeling and solving project scheduling with calendars. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 262–278. Springer, Cham (2015). doi:10.1007/978-3-319-23219-5_19
Montoya, C.: New methods for the multi-skills project scheduling problem. Ph.D. thesis, Ecole des Mines de Nantes (2012)
Montoya, C., Bellenguez-Morineau, O., Pinson, E., Rivreau, D.: Branch-and-price approach for the multi-skill project scheduling problem. Optim. Lett. 8(5), 1721–1734 (2014)
Montoya, C., Bellenguez-Morineau, O., Pinson, E., Rivreau, D.: Integrated column generation and lagrangian relaxation approach for the multi-skill project scheduling problem. In: Schwindt, C., Zimmermann, J. (eds.) Handbook on Project Management and Scheduling Vol.1. IHIS, pp. 565–586. Springer, Cham (2015). doi:10.1007/978-3-319-05443-8_26
Néron, E.: Lower bounds for the multi-skill project scheduling problem. In: Proceedings of 8th International Workshop on Project Management and Scheduling, pp. 274–277 (2002)
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74970-7_38
Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation via lazy clause generation. Constraints 14(3), 357–391 (2009)
Schutt, A., Chu, G., Stuckey, P.J., Wallace, M.G.: Maximising the net present value for resource-constrained project scheduling. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds.) Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, pp. 362–378. Springer, Heidelberg (2012)
Schutt, A., Feydy, T., Stuckey, P.J.: Scheduling optional tasks with explanation. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 628–644. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40627-0_47
Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G.: Explaining the cumulative propagator. Constraints 16(3), 250–282 (2011)
Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G.: Solving RCPSP/max by lazy clause generation. J. Sched. 16(3), 273–289 (2013)
Schutt, A., Stuckey, P.J., Verden, A.R.: Optimal carpet cutting. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 69–84. Springer, Heidelberg (2011). doi:10.1007/978-3-642-23786-7_8
Schutt, A., Feydy, T., Stuckey, P.J.: Explaining time-table-edge-finding propagation for the cumulative resource constraint. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 234–250. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38171-3_16
Szeredi, R., Schutt, A.: Modelling and solving multi-mode resource-constrained project scheduling. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 483–492. Springer, Cham (2016). doi:10.1007/978-3-319-44953-1_31
Wȩglarz, J., Józefowska, J., Mika, M., Waligóra, G.: Project scheduling with finite or infinite number of activity processing modes a survey. Eur. J. Oper. Res. 208(3), 177–205 (2011)
Young, K.D.: Multi-skill project scheduling problem instance library (2017). https://github.com/youngkd/MSPSP-InstLib
Acknowledgments
This work was partially supported by the Asian Office of Aerospace Research and Development grant 15-4016.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Young, K.D., Feydy, T., Schutt, A. (2017). Constraint Programming Applied to the Multi-Skill Project Scheduling Problem. In: Beck, J. (eds) Principles and Practice of Constraint Programming. CP 2017. Lecture Notes in Computer Science(), vol 10416. Springer, Cham. https://doi.org/10.1007/978-3-319-66158-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-66158-2_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-66157-5
Online ISBN: 978-3-319-66158-2
eBook Packages: Computer ScienceComputer Science (R0)