Document Open Access Logo

Partially Preemptive Multi Skill/Mode Resource-Constrained Project Scheduling with Generalized Precedence Relations and Calendars

Authors Guillaume Povéda , Nahum Alvarez , Christian Artigues

PDF
Thumbnail PDF

File

LIPIcs.CP.2023.31.pdf
  • Filesize: 1.41 MB
  • 21 pages

Document Identifiers

Author Details

Guillaume Povéda
  • Airbus (AI Research), Toulouse, France
Nahum Alvarez
  • Airbus (AI Research), Toulouse, France
Christian Artigues
  • LAAS-CNRS, Universite de Toulouse, CNRS, Toulouse, France

Funding

This work received the support of the Support from the French ANR-3IA Artificial and Natural Intelligence Toulouse Institute (ANITI).
  • Povéda, Guillaume: ANITI
  • Alvarez, Nahum: ANITI
  • Artigues, Christian: ANITI

Acknowledgements

The authors are grateful to the anonymous reviewers for their constructive comments. In particular, we thank the anonymous reviewer that pointed out the issue linked to preemption in the CP-Base model and made inspiring suggestions that leaded to the CP-SmartPreemption model.

Cite As Get BibTex

Guillaume Povéda, Nahum Alvarez, and Christian Artigues. Partially Preemptive Multi Skill/Mode Resource-Constrained Project Scheduling with Generalized Precedence Relations and Calendars. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CP.2023.31

Abstract

Multi skill resource-constrained project scheduling Problems (MS-RCPSP) have been object of studies from many years. Also, preemption is an important feature of real-life scheduling models. However, very little research has been investigated concerning MS-RCPSPs including preemption, and even less research moving out from academic benchmarks to real problem solving. In this paper we present a solution to those problems based on a hybrid method derived from large neighborhood search incorporating constraint programming components tailored to deal with complex scheduling constraints. We also present a constraint programming model adapted to preemption. The methods are implemented in a new open source python library allowing to easily reuse existing modeling languages and solvers. We evaluate the methods on an industrial case study from aircraft manufacturing including additional complicating constraints such as generalized precedence relations, resource calendars and partial preemption on which the standard CP Optimizer solver, even with the preemption-specific model, is unable to provide solutions in reasonable times. The large neighborhood search method is also able to find new best solutions on standard multi-skill project scheduling instances, performing better than a reference method from the literature.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning and scheduling
  • Applied computing → Industry and manufacturing
  • Theory of computation → Optimization with randomized search heuristics
  • Theory of computation → Constraint and logic programming
Keywords
  • Large-scale scheduling problem
  • partial preemption
  • multi-skill
  • multi-mode
  • resource calendars
  • constraint programming
  • large neighborhood search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Behrouz Afshar-Nadjafi. Multi-skilling in scheduling problems: A review on models, methods and applications. Computers & Industrial Engineering, 151:107004, 2021. Google Scholar
  2. Bernardo F Almeida, Isabel Correia, and Francisco Saldanha-da Gama. Priority-based heuristics for the multi-skill resource constrained project scheduling problem. Expert Systems with Applications, 57:91-103, 2016. Google Scholar
  3. Bernardo F Almeida, Isabel Correia, and Francisco Saldanha-da Gama. Modeling frameworks for the multi-skill resource-constrained project scheduling problem: a theoretical and empirical comparison. International Transactions in Operational Research, 26(3):946-967, 2019. Google Scholar
  4. Lucio Bianco and Massimiliano Caramia. An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations. European Journal of Operational Research, 219(1):73-85, 2012. Google Scholar
  5. P. Brucker. Complex Scheduling. Springer, 1999. Google Scholar
  6. José Coelho and Mario Vanhoucke. Multi-mode resource-constrained project scheduling using rcpsp and sat solvers. European Journal of Operational Research, 213(1):73-82, 2011. Google Scholar
  7. Erik L Demeulemeester and Willy S Herroelen. An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem. European Journal of Operational Research, 90(2):334-348, 1996. Google Scholar
  8. Emir Demirović, Geoffrey Chu, and Peter J Stuckey. Solution-based phase saving for cp: A value-selection heuristic to simulate local search behavior in complete solvers. In Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings 24, pages 99-108. Springer, 2018. Google Scholar
  9. Andreas Drexl and Juergen Gruenewald. Nonpreemptive multi-mode resource-constrained project scheduling. IIE transactions, 25(5):74-81, 1993. Google Scholar
  10. Davide Giglio, Massimo Paolucci, Abdolreza Roshani, and Flavio Tonelli. Multi-manned assembly line balancing problem with skilled workers: a new mathematical formulation. IFAC-PapersOnLine, 50(1):1211-1216, 2017. Google Scholar
  11. Daniel Godard, Philippe Laborie, and Wim Nuijten. Randomized large neighborhood search for cumulative scheduling. In ICAPS, volume 5, pages 81-89, 2005. Google Scholar
  12. Shima Javanmard, Behrouz Afshar-Nadjafi, and Seyed Taghi Akhavan Niaki. Preemptive multi-skilled resource investment project scheduling problem: Mathematical modelling and solution approaches. Computers & Chemical Engineering, 96:55-68, 2017. Google Scholar
  13. Ahmed Karam, El-Awady Attia, and Philippe Duquenne. A milp model for an integrated project scheduling and multi-skilled workforce allocation with flexible working hours. IFAC-PapersOnLine, 50(1):13964-13969, 2017. Google Scholar
  14. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671-680, 1983. URL: https://doi.org/10.1126/science.220.4598.671.
  15. RAINER KOLISCH and ANDREAS DREXL. Local search for nonpreemptive multi-mode resource-constrained project scheduling. IIE Transactions, 29(11):987-999, 1997. URL: https://doi.org/10.1080/07408179708966417.
  16. Rainer Kolisch and Sönke Hartmann. Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. In Project scheduling, pages 147-178. Springer, 1999. Google Scholar
  17. Stefan Kreter, Andreas Schutt, and Peter J Stuckey. Using constraint programming for solving rcpsp/max-cal. Constraints, 22(3):432-462, 2017. Google Scholar
  18. Philippe Laborie. An update on the comparison of mip, cp and hybrid approaches for mixed resource allocation and scheduling. In Willem-Jan van Hoeve, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 403-411, Cham, 2018. Springer International Publishing. Google Scholar
  19. Haitao Li and Keith Womer. Scheduling projects with multi-skilled personnel by a hybrid milp/cp benders decomposition algorithm. Journal of Scheduling, 12(3):281-298, 2009. Google Scholar
  20. Paweł B. Myszkowski, Maciej Laszczyk, Ivan Nikulin, and Marek Skowronski. imopse: a library for bicriteria optimization in multi-skill resource-constrained project scheduling problem. Soft Computing, 23:3397-3410, 2019. Google Scholar
  21. Mireille Palpant, Christian Artigues, and Philippe Michelon. Lssper: Solving the resource-constrained project scheduling problem with large neighbourhood search. Annals of Operations Research, 131(1):237-257, 2004. Google Scholar
  22. Claude Le Pape and Philippe Baptiste. Heuristic control of a constraint-based algorithm for the preemptive job-shop scheduling problem. Journal of Heuristics, 5(3):305-325, 1999. Google Scholar
  23. Laurent Perron, Paul Shaw, and Vincent Furnon. Propagation guided large neighborhood search. In International Conference on Principles and Practice of Constraint Programming, pages 468-481. Springer, 2004. Google Scholar
  24. Oliver Polo-Mejía, Marie-Christine Anselmet, Christian Artigues, and Pierre Lopez. Mixed-integer and constraint programming formulations for a multi-skill project scheduling problem with partial preemption. In 12th International Conference on Modelling, Optimization and Simulation (MOSIM 2018), pages 367-374, 2018. Google Scholar
  25. Oliver Polo-Mejía, Christian Artigues, Pierre Lopez, and Virginie Basini. Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility. International Journal of Production Research, 58(23):7149-7166, 2020. Google Scholar
  26. Oliver Polo-Mejía, Christian Artigues, Pierre Lopez, Lars Mönch, and Virginie Basini. Heuristic and metaheuristic methods for the multi-skill project scheduling problem with partial preemption. International Transactions in Operational Research, 2021. Google Scholar
  27. Sacramento Quintanilla, Ángeles Pérez, Pilar Lino, and Vicente Valls. Time and work generalised precedence relationships in project scheduling with pre-emption: An application to the management of service centres. European Journal of Operational Research, 219(1):59-72, 2012. Google Scholar
  28. Jerzy Rosłon. The multi-mode, resource-constrained project scheduling problem in construction: state of art review and research challenges problem. Technical Transactions, 2017. URL: https://doi.org/10.4467/2353737XCT.17.070.6427.
  29. Mónica A Santos and Anabela P Tereso. On the multi-mode, multi-skill resource constrained project scheduling problem-a software application. In Soft computing in industrial applications, pages 239-248. Springer, 2011. Google Scholar
  30. Andreas Schutt, Thibaut Feydy, Peter J Stuckey, and Mark G Wallace. Explaining the cumulative propagator. Constraints, 16(3):250-282, 2011. Google Scholar
  31. Andreas Schutt, Thibaut Feydy, Peter J. Stuckey, and Mark G. Wallace. Solving rcpsp/max by lazy clause generation. J. Sched., 16(3):273-289, 2013. URL: https://doi.org/10.1007/s10951-012-0285-x.
  32. Andreas Schutt, Thibaut Feydy, Peter J Stuckey, and Mark G Wallace. Solving rcpsp/max by lazy clause generation. Journal of scheduling, 16(3):273-289, 2013. Google Scholar
  33. Jakob Snauwaert and Mario Vanhoucke. A new algorithm for resource-constrained project scheduling with breadth and depth of skills. European Journal of Operational Research, 292(1):43-59, 2021. URL: https://doi.org/10.1016/j.ejor.2020.10.032.
  34. Jakob Snauwaert and Mario Vanhoucke. A classification and new benchmark instances for the multi-skilled resource-constrained project scheduling problem. European Journal of Operational Research, 2022. URL: https://doi.org/10.1016/j.ejor.2022.05.049.
  35. Tianshu Song, Ke Xu, Jiangneng Li, Yiming Li, and Yongxin Tong. Multi-skill aware task assignment in real-time spatial crowdsourcing. GeoInformatica, 24(1):153-173, 2020. Google Scholar
  36. Ria Szeredi and Andreas Schutt. Modelling and solving multi-mode resource-constrained project scheduling. In International Conference on Principles and Practice of Constraint Programming, pages 483-492. Springer, 2016. Google Scholar
  37. Tony Wauters, Joris Kinable, Pieter Smet, Wim Vancroonenburg, Greet Vanden Berghe, and Jannes Verstichel. The multi-mode resource-constrained multi-project scheduling problem. Journal of Scheduling, 19(3):271-283, 2016. Google Scholar
  38. Kenneth Young, Thibaut Feydy, and Andreas Schutt. Constraint programming applied to the multi-skill project scheduling problem. In Principles and Practice of Constraint Programming - 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings, pages 308-317, August 2017. URL: https://doi.org/10.1007/978-3-319-66158-2_20.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact