A Constraint Programming Approach to Solve Multi-skill Resource-constrained Project Scheduling Problem with Calendars

Document Type : Original Article

Authors

1 Faculty of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran

2 System Engineering Department, École de technologie supérieure, Montreal, Canada

Abstract

The multi-skill resource constrained project scheduling is an important and challenging problem in project management. Two key issues that turn this topic into a challenging problem are the assumptions that are considered to approximate the model to a real-world problem and exact solution approach for the model. In this paper, we deal with this two issues. To consider real-word situations, we take into account calendars specifying time intervals during which the resources are available. We proposed a constraint programming approach to solve the problem exactly. The problem with and without resource calendars are modeled with mathematical programming (MP) and constraint programming (CP). In addition, the performance of CP approach is evaluated by comparing Time-Indexed Model (TIM) and Branch and Price (B&P) approaches. Computational results show that the proposed approach can efficiently solve real-size instances.

Keywords

Main Subjects

References

  1. Hartmann, S. and Briskorn, D., "An updated survey of variants and extensions of the resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 297, No. 1, (2022), 1-14, https://doi.org/10.1016/j.ejor.2021.05.004
  2. Rezaei, F., Najafi, A.A. and Ramezanian, R., "Mean-conditional value at risk model for the stochastic project scheduling problem", Computers & Industrial Engineering, Vol. 142, (2020), 106356, https://doi.org/10.1016/j.cie.2020.106356
  3. Niaki, S., Najafi, A.A., Zoraghi, N. and Abbasi, B., "Resource constrained project scheduling with material ordering: Two hybridized meta-heuristic approaches", International Journal of Engineering, Transactions C: Aspects, Vol. 28, No. 6, (2015), 896-902, doi: 10.5829/idosi.ije.2015.28.06c.10.
  4. Khalili, S., Najafi, A.A. and Niaki, S.T.A., "Bi-objective resource constrained project scheduling problem with makespan and net present value criteria: Two meta-heuristic algorithms", The International Journal of Advanced Manufacturing Technology, Vol. 69, No. 1, (2013), 617-626, https://doi.org/10.1007/s00170-013-5057-z
  5. Rezaei, F., Najafi, A.A., Ramezanian, R. and Demeulemeester, E., "Simulation-based priority rules for the stochastic resource-constrained net present value and risk problem", Computers & Industrial Engineering, Vol. 160, No., (2021), 107607, https://doi.org/10.1016/j.cie.2021.107607
  6. Mollaei, H., Tavakkoli-Moghaddam, R. and Toloie-Eshlaghy, A., "A new multi-objective model for multi-mode project planning with risk", International Journal of Engineering, Transactions B: Applications, Vol. 31, No. 5, (2018), 770-779, doi: 10.5829/ije.2018.31.05b.12.
  7. Franck, B., Neumann, K. and Schwindt, C., "Project scheduling with calendars", OR-Spektrum, Vol. 23, No. 3, (2001), 325-334, http://dx.doi.org/10.1007/PL00013355
  8. Kreter, S., Rieck, J. and Zimmermann, J., "Models and solution procedures for the resource-constrained project scheduling problem with general temporal constraints and calendars", European Journal of Operational Research, Vol. 251, No. 2, (2016), 387-403, https://doi.org/10.1016/j.ejor.2015.11.021
  9. Ahmadpour, S. and Ghezavati, V., "Modeling and solving multi-skilled resource-constrained project scheduling problem with calendars in fuzzy condition", Journal of Industrial Engineering International, Vol. 15, No. 1, (2019), 179-197, http://dx.doi.org/10.1007/s40092-019-00328-w
  10. Afshar-Nadjafi, B., "Multi-skilling in scheduling problems: A review on models, methods and applications", Computers & Industrial Engineering, Vol. 151, (2021), 107004, https://doi.org/10.1016/j.cie.2020.107004
  11. Correia, I. and Saldanha-da-Gama, F., A modeling framework for project staffing and scheduling problems, in Handbook on project management and scheduling vol. 1. 2015, Springer.547-564.
  12. Bellenguez-Morineau, O. and Néron, E., "A branch-and-bound method for solving multi-skill project scheduling problem", RAIRO-operations Research, Vol. 41, No. 2, (2007), 155-170, http://dx.doi.org/10.1051/ro:2007015
  13. Avramidis, A.N., Chan, W., Gendreau, M., L’ecuyer, P. and Pisacane, O., "Optimizing daily agent scheduling in a multiskill call center", European Journal of Operational Research, Vol. 200, No. 3, (2010), 822-832, http://dx.doi.org/10.1016/j.ejor.2009.01.042
  14. Cai, X. and Li, K., "A genetic algorithm for scheduling staff of mixed skills under multi-criteria", European Journal of Operational Research, Vol. 125, No. 2, (2000), 359-369, https://doi.org/10.1016/S0377-2217(99)00391-4
  15. Wongwai, N. and Malaikrisanachalee, S., "Augmented heuristic algorithm for multi-skilled resource scheduling", Automation in Construction, Vol. 20, No. 4, (2011), 429-445, https://doi.org/10.1016/j.autcon.2010.11.012
  16. Walter, M. and Zimmermann, J., "Minimizing average project team size given multi-skilled workers with heterogeneous skill levels", Computers & Operations Research, Vol. 70, (2016), 163-179, https://doi.org/10.1016/j.cor.2015.11.011
  17. Heimerl, C. and Kolisch, R., "Scheduling and staffing multiple projects with a multi-skilled workforce", OR spectrum, Vol. 32, No. 2, (2010), 343-368, http://dx.doi.org/10.1007/s00291-009-0169-4
  18. De Bruecker, P., Van den Bergh, J., Beliën, J. and Demeulemeester, E., "Workforce planning incorporating skills: State of the art", European Journal of Operational Research, Vol. 243, No. 1, (2015), 1-16, https://doi.org/10.1016/j.ejor.2014.10.038
  19. Montoya, C., Bellenguez-Morineau, O., Pinson, E. and Rivreau, D., "Branch-and-price approach for the multi-skill project scheduling problem", Optimization Letters, Vol. 8, No. 5, (2014), 1721-1734, http://dx.doi.org/10.1007/s11590-013-0692-8
  20. Sabin, D. and Freuder, E.C., "Contradicting conventional wisdom in constraint satisfaction", in International Workshop on Principles and Practice of Constraint Programming, Springer. (1994), 10-20.
  21. Baumgärtner, S., Becker, C., Frank, K., Müller, B. and Quaas, M., "Relating the philosophy and practice of ecological economics: The role of concepts, models, and case studies in inter-and transdisciplinary sustainability research", Ecological Economics, Vol. 67, No. 3, (2008), 384-393, http://dx.doi.org/10.1016/j.ecolecon.2008.07.018
  22. Baptiste, P., Le Pape, C. and Nuijten, W., "Constraint-based scheduling: Applying constraint programming to scheduling problems, Springer Science & Business Media, Vol. 39,  (2001).
International Journal of Engineering
Volume 35, Issue 8
TRANSACTIONS B: Applications
August 2022
Pages 1579-1587

Files

Cited by

Share

How to cite

Statistics