Logo PTI Logo FedCSIS

Communication Papers of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 37

Parallelized Population-Based Multi-Heuristic System with Reinforcement Learning for Solving Multi-Skill Resource-Constrained Project Scheduling Problem with Hierarchical Skills

,

DOI: http://dx.doi.org/10.15439/2023F2826

Citation: Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 37, pages 243–250 ()

Full text

Abstract. In this paper the Parallelized Population-based Multi-Heuristic System controlled by the Reinforcement Learning based strategy is proposed to solve the Multi-Skill Resource Constrained Scheduling Problem with Hierarchical Skills, denoted as MS-RCPSP. It is an extension of the classical RCPSP where some given pool of skills has been assigned to the resources. The MS-RCPSP as well as the RCPSP belong to the class of strongly NP-hard optimization problems. To solve the MS-RCPSP the approach consisting of evolving a population of solutions and using a set of several heuristic algorithms controlled by the reinforcement learning strategy, and executed in parallel, has been proposed. To implement the system and take advantage of the speed-up offered by the parallel computations the Apache Spark platform has been used. The system has been tested experimentally using benchmark problem instances from the iMOPSE dataset with the makespan as the optimization criterion. The proposed approach produces good quality solutions often outperforming the existing approaches.

References

  1. B. F. Almeida, I. Correia and F. Saldanha-da Gama, “Modeling frameworks for the multi-skill resource-constrained project scheduling problem: A theoretical and empirical comparison.”, International Transactions in Operational Research, vol. 26 (3), 2019, pp. 946–967, https://doi.org/10.1111/itor.12568
  2. O. Bellenguez and E. Néron, “Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills”, in Proceedings of the international conference on the practice and theory of automated timetabling, Lecture Notes in Computer Science, vol. 3616, Springer, 2004, pp. 229—243, https://doi.org/10.1007/11593577_14
  3. F. Bellifemine, G. Caire and D. Greenwood, “Developing multi-agent systems with JADE.” John Wiley & Sons, Chichester, 2007, http://dx.doi.org/10.1002/9780470058411
  4. J. Błażewicz, J. Lenstra and A. Rinnooy, “Scheduling subject to resource constraints: Classification and complexity”, Discrete Applied Mathematics, vol. 5, 1983, pp. 11–24, https://doi.org/10.1016/0166-218X(83)90012-4
  5. S. Hartmann and D. Briskorn, “A survey of variants and extensions of the resource-constrained project scheduling problem”, European Journal of Operational Research, vol. 207 (1), 2010, pp. 1–14, https://doi.org/10.1016/j.ejor.2009.11.005
  6. S. Hartmann and D. Briskorn, “An updated survey of variants and extensions of the resource-constrained project scheduling problem”, In European journal of operational research, vol. 297 (1), 2021, pp. 1–14, https://doi.org/10.1016/j.ejor.2021.05.004
  7. W. Herroelen, E. Demeulemeester, and B. De Reyck, “A classification scheme for project scheduling,” Project scheduling, 1999, Springer, pp. 1–26, https://doi.org/10.1007/978-1-4615-5533-9_1
  8. A. H. Hosseinian and V. Baradaran, “An evolutionary algorithm based on a hybrid multi-attribute decision making method for the multi-mode multi-skilled resource-constrained project scheduling problem”, Journal of Optimization in Industrial Engineering, 12 (2), 2019, pp. 155—178, http://dx.doi.org/10.22094/JOIE.2018.556347.1531
  9. P. Jędrzejowicz and E. Ratajczak, “Population Learning Algorithm for Resource-Constrained Project Scheduling,” in Pearson D.W., Steele N.C., Albrecht R.F. (eds) Artificial Neural Nets and Genetic Algorithms, Springer, Viena, 2003, pp. 223-228, https://doi.org/10.1007/978-3-7091-0646-4_40
  10. P. Jędrzejowicz and P. and E. Ratajczak-Ropel, “Reinforcement Learning Strategies for A-Team Solving the Resource-Constrained Project Scheduling Problem.” Neurocomputing, vol. 146, 2014, pp. 301–307, http://dx.doi.org/10.1016/j.neucom.2014.05.070
  11. P. Jędrzejowicz and E. Ratajczak-Ropel, “Dynamic cooperative interaction strategy for solving RCPSP by a team of agents.” in Nguyen, N.T., Manolopoulos, Y., Iliadis, L., Trawiński, B. (eds) Computational Collective Intelligence. Lecture Notes in Artificial Intelligence, vol. 9875, 2016, pp. 454–463, https://doi.org/10.1007/978-3-319-45243-2_42
  12. P. Jędrzejowicz and E. Ratajczak-Ropel, “A-Team solving multi-skill resource-constrained project scheduling problem”, Procedia Computer Science, vol. 207, 2022, pp. 3294-–3303 [26th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems (KES 2022)], https://doi.org/10.1016/j.procs.2022.09.388
  13. R. Kolisch, “Efficient Priority Rules for the Resource-Constrained Project Scheduling Problem” Journal of Operations Management, vol. 14, 1996, 179–192, https://doi.org/10.1016/0272-6963(95)00032-1
  14. R. Kolisch, “Serial and Parallel Resource-Constrained Project Scheduling Methods Revisited: Theory and Computation” European Journal of Operational Research, vol. 90, 1996, pp. 320–333, https://doi.org/10.1016/0377-2217(95)00357-6
  15. R. Kolisch and S. Hartmann, “Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update”, European Journal of Operational Research, vol. 174 (1), 2006, pp. 23–37, https://doi.org/10.1016/j.ejor.2005.01.065
  16. J. Lin, L. Zhu, K. Gao, “A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem”, Expert Syst. Appl., vol. 140, 2020, art. 112915, https://doi.org/10.1016/j.eswa.2019.112915
  17. C. Montoya, O. Bellenguez-Morineau, E. Pinson and D. Rivreau, ”Branch-and-price approach for the multi-skill project scheduling problem.” Optimization Letters, vol. 8 (5), 2014, pp. 1721–1734, https://doi.org/10.1007/s11590-013-0692-8
  18. P. B. Myszkowski, M. E. Skowroński and Ł. Podlodowski, “Novel heuristic solutions for Multi–Skill Resource–Constrained Project Scheduling Problem”, in M. Ganzha, L. Maciaszek, M. Paprzycki (eds) Proceedings of the 2013 Federated Conference on Computer Science and Information Systems FedCSIS, IEEE, 2013, pp. 159–166, ISBN 978-1-4673-4471-5
  19. P. B. Myszkowski, M. E. Skowroński and K. Sikora, “A new benchmark dataset for Multi-Skill Resource-Constrained Project Scheduling Problem” in M. Ganzha, L. Maciaszek, M. Paprzycki (eds) Proceedings of the 2015 federated conference on computer science and information systems, ACSIS, vol. 5, 2015, pp. 129-–138, http://dx.doi.org/10.15439/2015F273
  20. P. B. Myszkowski, “Hybrid ant colony optimization in solving multi–skill resource–constrained project scheduling problem” Soft Computing, vol. 19 (12), 2015, pp. 3599—3619, https://doi.org/10.1007/s00500-014-1455-x
  21. P. B. Myszkowski and J.J. Siemieński, “GRASP applied to MultiSkill Resource-Constrained Project Scheduling Problem”, in Nguyen, NT., Iliadis, L., Manolopoulos, Y., Trawiński, B. (eds) Computational Collective Intelligence (ICCCI 2016), Lecture Notes in Computer Science, vol. 9875, 2016, pp. 402—411, https://doi.org/10.1007/978-3-319-45243-2_37
  22. P. B. Myszkowski, Ł.P. Olech, M. Laszczyk and M. E. Skowroński, “Hybrid Differential Evolution and Greedy Algorithm (DEGR) for Solving Multi-Skill Resource-Constrained Project Scheduling Problem”, Applied Soft Computing, vol. 62, 2018, pp. 1–14, https://doi.org/10.1016/j.asoc.2017.10.014
  23. P. B. Myszkowski, M. Laszczyk, I. Nikulin and M. Skowroński, “iMOPSE: a library for bicriteria optimization in Multi-Skill Resource-Constrained Project Scheduling Problem”, Soft Computing, vol. 23 (10), pp. 3397–3410, https://doi.org/10.1007/s00500-017-2997-5
  24. E. Néron and D. Baptista, “Heuristics for multi-skill project scheduling problem”, International Symposium on Combinatorial Optimization (CO’2002), 2002.
  25. R. Pellerin, N. Perrier, F. Berthaut, “A survey of hybrid metaheuristics for the resource-constrained project scheduling problem”, European Journal of Operational Research, vol. 280, 2020), pp. 395–416, http://dx.doi.org/10.1016/j.ejor.2019.01.063
  26. E. Ratajczak-Ropel, “Agent-Based Approach to the Single and Multi-mode Resource-Constrained Project Scheduling. Population-Based Approaches to the Resource-Constrained and Discrete-Continuous Schedul- ing,” in Janusz Kacprzyk (ed.) Studies in Systems Decision and Control, vol. 108, Springer International Publishing, 2018, pp. 1–100. http://dx.doi.org/10.1007/978-3-319-62893-6.
  27. J. Snauwaert, and M. Vanhoucke, “A classifiction and new benchmark instances for the multi-skilled resource-constrained project scheduling problem,” European Journal of Operational Research, vol. 307, 2023, pp. 1–19, https://doi.org/10.1016/j.ejor.2022.05.049
  28. Hy. Zheng, L. Wang and Xl. Zheng, “Teaching–learning based optimization algorithm for multi-skill resource constrained project scheduling problem,” Soft Computing, vol. 21, 2017, pp. 1537–1548. doi.org/10.1007/s00500-015-1866-3
  29. L. Zhu, J. Lin, Y.-Y. Li, and Z. J. Wang, “A decomposition-based multi-objective genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem,” Knowledge-Based Systems, vol. 225, 2021, art. 107099, https://doi.org/10.1016/j.knosys.2021.107099
  30. iMOPSE (intelligent Multi Objective Project Scheduling Environment) project homepage, containing description of investigated methods, dataset definition, solution validators, references and best found solutions. http://imopse.ii.pwr.wroc.pl/