Abstract
In this paper, we address a multi-project scheduling and multi-skilled employees assignment problem with hard and soft constraints. The goal is to assign employees to project tasks in a way that minimizes the total weighted tardiness and the undesirable goal deviations. Employees are assigned to projects with fixed percentages of time, and they must complete all projects within the desired time horizon. Each project is broken down into a set of preemptive tasks with release and due dates, without explicit precedence constraints. Each task must be performed by a single employee owning several skills and an efficiency level per skill, i.e., the processing time of the task may be reduced according to the efficiency level of the employee assigned to this task. As specified later, the studied problem comes from an industrial case in an IT company. All the constraints and the goal to achieve have been discussed with the projects managers. For this problem, we present a mixed-integer goal programming (MIGP) formulation to produce an optimal schedule. Furthermore, a local search algorithm and a tabu search algorithm are proposed to tackle large-scale instances. We compare the performance of the heuristic algorithms against the corresponding MIGP formulation with simulated instances derived from real-world instances got from the partner company.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agnetis A, Billaut JC, Gawiejnowicz S et al (2014) Multiagent Scheduling: Models and Algorithms. Springer, Berlin, Heidelberg,. https://doi.org/10.1007/978-3-642-41880-8
Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Pearson Education, London
Almeida BF, Correia I, da Gama FS (2016) Priority-based heuristics for the multi-skill resource constrained project scheduling problem. Expert Syst Appl 57:91–103. https://doi.org/10.1016/j.eswa.2016.03.017
Almeida BF, Correia I, Saldanha-da Gama F (2018) A biased random-key genetic algorithm for the project scheduling problem with flexible resources. TOP 26(2):283–308. https://doi.org/10.1007/s11750-018-0472-9
Alonso-Pecina F, Pecero J, D.Romero (2013) A three-phases based algorithm for the multi-mode resource-constrained multi-project scheduling problem. In: 6th Multidisciplinary international scheduling conference (MISTA), pp 812–814
Bellenguez O, Néron E (2005) Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills. In: Practice and theory of automated timetabling V. Springer, Berlin, pp 229–243. https://doi.org/10.1007/11593577_14
Bellenguez O, Néron E (2007) A branch-and-bound method for solving multi-skill project scheduling problem. RAIRO Oper Res 41(2):155–170. https://doi.org/10.1051/ro:2007015
Bernhard K, Jens V (2006) Bin-Packing, vol 21. Springer, pp 426–441. https://doi.org/10.1007/978-3-642-25401-7_18
Blazewicz J, Lenstra JK, Kan AHGR (1983) Scheduling subject to resource constraints: classification and complexity. Discret Appl Math 5(1):11–24. https://doi.org/10.1016/0166-218X(83)90012-4
Brucker P, Bernd BJ, Krämer A (1997) Complexity of scheduling problems with multi-purpose machines. Ann Oper Res 70:57–73. https://doi.org/10.1023/A:1018950911030
Chen R, Liang C, Gu D et al (2017) A multi-objective model for multi-project scheduling and multi-skilled staff assignment for it product development considering competency evolution. Int J Prod Res 55(21):6207–6234. https://doi.org/10.1080/00207543.2017.1326641
Choi I, Choi D (2002) A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups. Comput Ind Eng 42:43–58. https://doi.org/10.1016/S0360-8352(02)00002-5
Correia I, da Gama FS (2014) The impact of fixed and variable costs in a multi-skill project scheduling problem: an empirical study. Comput Ind Eng 72:230–238. https://doi.org/10.1016/j.cie.2014.03.020
Correia I, Lourenço LL, da Gama FS (2012) Project scheduling with flexible resources: formulation and inequalities. OR Spectrum 34:635–663. https://doi.org/10.1007/s00291-010-0233-0
Cui L, Liu X, Lu S et al (2021) A variable neighborhood search approach for the resource-constrained multi-project collaborative scheduling problem. Appl Soft Comput 107(107):480. https://doi.org/10.1016/j.asoc.2021.107480
Dai H, Cheng W (2019) A memetic algorithm for multiskill resource-constrained project scheduling problem under linear deterioration. Math Probl Eng. https://doi.org/10.1155/2019/9459375
Dhib C, Soukhal A, Néron E (2015) Mixed-integer linear programming formulation and priority-rule methods for a preemptive project staffing and scheduling problem, vol 1. Springer, Cham, pp 603–617. https://doi.org/10.1007/978-3-319-05443-8_28
Drezet LE, Billaut JC (2008) A project scheduling problem with labour constraints and time-dependent activities requirements. Int J Prod Econ 112(1):217–225. https://doi.org/10.1016/j.ijpe.2006.08.021 (special Section on Recent Developments in the Design, Control, Planning and Scheduling of Productive Systems)
Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems 19:248–264. https://doi.org/10.1145/321694.321699
Felberbauer T, Gutjahr WJ, Doerner KF (2019) Stochastic project management: multiple projects with multi-skilled human resources. J Sched 22:271–288. https://doi.org/10.1007/s10951-018-0592-y
Fırat M, Hurkens CA (2012) An improved mip-based approach for a multi-skill workforce scheduling problem. J Sched. https://doi.org/10.1007/s10951-011-0245-x
Glover F, Kelly J, Laguna M (1995) Genetic algorithms and tabu search: Hybrids for optimization. Comput Oper Res 22(1):111–134. https://doi.org/10.1016/0305-0548(93)E0023-M
Gutjahr WJ, Katzensteiner S, Reiter P et al (2010) Multi-objective decision analysis for competence-oriented project portfolio selection. Eur J Oper Res 205(3):670–679. https://doi.org/10.1016/j.ejor.2010.01.041
Haitao L, Keith W (2008) Scheduling projects with multi-skilled personnel by a hybrid milp/cp benders decomposition algorithm. J Sched 12:281. https://doi.org/10.1007/s10951-008-0079-3
Heimerl C, Kolisch R (2010) Scheduling and staffing multiple projects with a multi-skilled workforce. OR Spectrum 32(2):19–25. https://doi.org/10.1007/s00291-009-0169-4
Hematian M, Esfahani M, Mahdavi I et al (2020) A multiobjective integrated multiproject scheduling and multiskilled workforce assignment model considering learning effect under uncertainty. Comput Intell 36(1):276–296. https://doi.org/10.1111/coin.12260
Ishibuchi H, Murata T (1998) A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans Syst Man Cybern Part C (Applications and Reviews) 28(3):392–403. https://doi.org/10.1109/5326.704576
Ji M, Wang JY, Lee WC (2013) Minimizing resource consumption on uniform parallel machines with a bound on makespan. Comput Oper Res 40(12):2970–2974. https://doi.org/10.1016/j.cor.2013.06.011
Kaabi J, Harrath Y (2019) Scheduling on uniform parallel machines with periodic unavailability constraints. Int J Prod Res 57(1):216–227. https://doi.org/10.1080/00207543.2018.1471242
Kolisch R, Heimerl C (2012) An efficient metaheuristic for integrated scheduling and staffing it projects based on a generalized minimum cost flow network. Nav Res Logist (NRL) 59(2):111–127. https://doi.org/10.1002/nav.21476
Labetoulle J, Lawler E, Lenstra J, et al (1984) Preemptive scheduling of uniform machines subject to release dates. In: Progress in combinatorial optimization. Academic Press, New York, pp 245–261. https://doi.org/10.1016/B978-0-12-566780-7.50020-9
Laszczyk M, Myszkowski PB (2019) Improved selection in evolutionary multi-objective optimization of multi-skill resource-constrained project scheduling problem. Inf Sci 481:412–431. https://doi.org/10.1016/j.ins.2019.01.002
Lin SW, Ying KC (2017) Uniform parallel-machine scheduling for minimizing total resource consumption with a bounded makespan. IEEE Access 5:15,791-15,799. https://doi.org/10.1109/ACCESS.2017.2735538
Lin J, Zhu L, Gao K (2020) A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Syst Appl 140(112):915. https://doi.org/10.1016/j.eswa.2019.112915
Maghsoudlou H, Afshar-Nadjafi B, Akhavan Niaki ST (2017) Multi-skilled project scheduling with level-dependent rework risk; three multi-objective mechanisms based on cuckoo search. Appl Soft Comput 54:46–61. https://doi.org/10.1016/j.asoc.2017.01.024
Maghsoudlou H, Afshar-Nadjafi B, Niaki S (2019) Preemptive multi-skilled resource constrained project scheduling problem with hard/soft interval due dates. RAIRO Oper Res 53:1877–1898. https://doi.org/10.1051/ro/2018103
Mei B, Lambrechts A, Verkest D et al (2005) Architecture exploration for a reconfigurable architecture template. IEEE Des Test Comput 22(2):90–101. https://doi.org/10.1109/MDT.2005.27
Mika M, Waligóra G, Wȩglarz J (2008) Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times. Eur J Oper Res 187(3):1238–1250. https://doi.org/10.1016/j.ejor.2006.06.069
Montoya C, Bellenguez O, Pinson E et al (2014) Branch-and-price approach for the multi-skill project scheduling problem. Optimiz Lettersh 8:1721–1734. https://doi.org/10.1007/s11590-013-0692-8
Myszkowski PB, Laszczyk M, Kalinowski D (2017) Co-evolutionary algorithm solving multi-skill resource-constrained project scheduling problem. In: 2017 Federated conference on computer science and information systems (FedCSIS), pp 75–82. https://doi.org/10.15439/2017F318
Myszkowski PB, Olech ŁP, Laszczyk M et al (2018) Hybrid differential evolution and greedy algorithm (degr) for solving multi-skill resource-constrained project scheduling problem. Appl Soft Comput 62:1–14. https://doi.org/10.1016/j.asoc.2017.10.014
Néron E, Baptista D (2002) Lower bounds for the multi-skill project scheduling problem. In: the Eighth international workshop on project management and scheduling, pp 274–277
Pan N, Hsaio P, Chen K (2008) A study of project scheduling optimization using tabu search algorithm. Eng Appl Artif Intell 21(7):1101–1112. https://doi.org/10.1016/j.engappai.2007.11.006
Polo-Mejía O, Artigues C, Lopez P et al (2019) Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility. Int J Prod Res 58(23):7149–7166. https://doi.org/10.1080/00207543.2019.1693654
Snauwaert J, Vanhoucke M (2021) A new algorithm for resource-constrained project scheduling with breadth and depth of skills. Eur J Oper Res 292(1):43–59. https://doi.org/10.1016/j.ejor.2020.10.032
Tseng L, Lin Y (2009) A hybrid genetic local search algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 198:84–92. https://doi.org/10.1016/j.ejor.2008.08.023
Valls V, Pérez Á, Quintanilla S (2009) Skilled workforce scheduling in service centres. Eur J Oper Res 193(3):791–804. https://doi.org/10.1016/j.ejor.2007.11.008
Walter M (2015) Multi-project management with a multi-skilled workforce. Springer Gabler, Wiesbaden. https://doi.org/10.1007/978-3-658-08036-5
Walter M, Zimmermann J (2016) Minimizing average project team size given multi-skilled workers with heterogeneous skill levels. Comput Oper Res 70:163–179. https://doi.org/10.1016/j.cor.2015.11.011
Wang L, long Zheng X (2018) A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm Evol Comput 38:54–63. https://doi.org/10.1016/j.swevo.2017.06.001
Wu MC, Sun SH (2006) A project scheduling and staff assignment model considering learning effect. Int J Adv Manuf Technol 28:1190–1195. https://doi.org/10.1007/s00170-004-2465-0
Xiao J, Ao XT, Tang Y (2013) Solving software project scheduling problems with ant colony optimization. Comput Oper Res 40(1):33–46. https://doi.org/10.1016/j.cor.2012.05.007
Yannibelli V, Amandi A (2013) Hybridizing a multi-objective simulated annealing algorithm with a multi-objective evolutionary algorithm to solve a multi-objective project scheduling problem. Expert Syst Appl 40(7):2421–2434. https://doi.org/10.1016/j.eswa.2012.10.058
Yeh WC, Chuang MC, Lee WC (2015) Uniform parallel machine scheduling with resource consumption constraint. Appl Math Model 39(8):2131–2138. https://doi.org/10.1016/j.apm.2014.10.012
yu Zheng H, Wang L, long Zheng X (2017) Teaching-learning-based optimization algorithm for multi-skill resource constrained project scheduling problem. Soft Comput 21:1537–1548. https://doi.org/10.1007/s00500-015-1866-3
Zeng Y, Che A, Wu X (2018) Bi-objective scheduling on uniform parallel machines considering electricity cost. Eng Optim 50(1):19–36. https://doi.org/10.1080/0305215X.2017.1296437
Zhu L, Lin J, Wang ZJ (2019) A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem. Appl Soft Comput 85(105):805. https://doi.org/10.1016/j.asoc.2019.105805
Zhu L, Lin J, Li YY et al (2021) A decomposition-based multi-objective genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Knowl-Based Syst 225(107):099. https://doi.org/10.1016/j.knosys.2021.107099
Acknowledgements
The authors are grateful to the Cooperation and Cultural Action Service (SCAC) of the French embassy in Mauritania for funding part of this work. We would like to thank the reviewers for their insightful suggestions and comments.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Haroune, M., Dhib, C., Neron, E. et al. Multi-project scheduling problem under shared multi-skill resource constraints. TOP 31, 194–235 (2023). https://doi.org/10.1007/s11750-022-00633-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-022-00633-5