MEMINV: A hybrid efficient approximation method solving the multi skill-resource constrained project scheduling problem

Huu Dang Quoc; Huu Dang Quoc

doi:10.3934/mbe.2023688

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 8: 15407-15430. doi: 10.3934/mbe.2023688

Previous Article Next Article

Research article Special Issues

MEMINV: A hybrid efficient approximation method solving the multi skill-resource constrained project scheduling problem

Huu Dang Quoc ^,

Department of Economic Information System and Electronic Commerce, Thuong Mai University, 79 Ho Tung Mau, Cau Giay, Ha Noi, Viet Nam

Received: 28 February 2023 Revised: 18 June 2023 Accepted: 16 July 2023 Published: 24 July 2023

The Multi-Skill Resource-Constrained Project Scheduling Problem (MS-RCPSP) is an NP-Hard problem that involves scheduling activities while accounting for resource and technical constraints. This paper aims to present a novel hybrid algorithm called MEMINV, which combines the Memetic algorithm with the Inverse method to tackle the MS-RCPSP problem. The proposed algorithm utilizes the inverse method to identify local extremes and then relocates the population to explore new solution spaces for further evolution. The MEMINV algorithm is evaluated on the iMOPSE benchmark dataset, and the results demonstrate that it outperforms. The solution of the MS-RCPSP problem using the MEMINV algorithm is a schedule that can be used for intelligent production planning in various industrial production fields instead of manual planning.
- memetic algorithm,
- evolutionary computing,
- optimization,
- MS-RCPSP problem
Citation: Huu Dang Quoc. MEMINV: A hybrid efficient approximation method solving the multi skill-resource constrained project scheduling problem[J]. Mathematical Biosciences and Engineering, 2023, 20(8): 15407-15430. doi: 10.3934/mbe.2023688

Related Papers:

Abstract

The Multi-Skill Resource-Constrained Project Scheduling Problem (MS-RCPSP) is an NP-Hard problem that involves scheduling activities while accounting for resource and technical constraints. This paper aims to present a novel hybrid algorithm called MEMINV, which combines the Memetic algorithm with the Inverse method to tackle the MS-RCPSP problem. The proposed algorithm utilizes the inverse method to identify local extremes and then relocates the population to explore new solution spaces for further evolution. The MEMINV algorithm is evaluated on the iMOPSE benchmark dataset, and the results demonstrate that it outperforms. The solution of the MS-RCPSP problem using the MEMINV algorithm is a schedule that can be used for intelligent production planning in various industrial production fields instead of manual planning.

References

[1]	R. Klein, Scheduling of Resource-Constrained Projects, Springer Science & Business Media., 10 (2012).
[2]	D. Q. Huu, N. T. Loc, N. D. Cuong, An effective hybrid algorithm based on particle swarm optimization with migration method for solving the multiskill resource-constrained project scheduling problem, Appl. Comput. Intell. Soft Comput., 2022 (2022), Article ID 6230145. https://doi.org/10.1155/2022/6230145 doi: 10.1155/2022/6230145
[3]	D. Q. Huu, N. T. Loc, N. D. Cuong, P. T. Toan, New effective differential evolution algorithm for the multi-skill resource constrained project scheduling problem, in 2020 2nd International Conference on Computer Communication and the Internet (ICCCI 2020)., Published by IEEE, Nagoya, Japan, June 26–29, (2020). https://doi.org/10.1109/ICCCI49374.2020.9145982
[4]	P. B. Myszkowski, M. Laszczyk, Investigation of benchmark dataset for many-objective multi-skill resource constrained project scheduling problem, Appl. Soft Comput., 127 (2022), 109253. https://doi.org/10.1016/j.asoc.2022.109253 doi: 10.1016/j.asoc.2022.109253
[5]	P. B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, iMOPSE: A library for bicriteria optimization in Multi-Skill Resource-Constrained Project Scheduling Problem, Soft Comput. J., 23 (2019). https://doi.org/10.1007/s00500-017-2997-5 doi: 10.1007/s00500-017-2997-5
[6]	A. J. Wilson, D. R. Pallavi, M. Ramachandran, S. Chinnasamy, S. Sowmiya, A review on memetic algorithms and its developments, Electr. Autom. Eng., 1 (2022), 7–12. https://doi.org/10.46632/eae/1/1/2 doi: 10.46632/eae/1/1/2
[7]	S. Afsar, J. J. Palacios, J. Puente, C. R. Vela, I. González-Rodríguez, Multi-objective enhanced memetic algorithm for green job shop scheduling with uncertain times, Swarm Evolut. Comput., 68 (2022), 101016. https://doi.org/10.1016/j.swevo.2021.101016 doi: 10.1016/j.swevo.2021.101016
[8]	W. Seo, M. Park, D. W. Kim, J. Lee, Effective memetic algorithm for multilabel feature selection using hybridization-based communication, Expert Syst. Appl., 201 (2022), 117064. https://doi.org/10.1016/j.eswa.2022.117064 doi: 10.1016/j.eswa.2022.117064
[9]	J. Piotr, E. Ratajczak-Ropel, A-team solving multi-skill resource-constrained project scheduling problem, Proced. Computer Sci., 207 (2022), 3300–3309. https://doi.org/10.1016/j.procs.2022.09.388 doi: 10.1016/j.procs.2022.09.388
[10]	M. Laszczyk, P. B. Myszkowski, Improved selection in evolutionary multi–objective optimization of multi–skill resource–constrained project scheduling problem, Inform. Sci., 481 (2019), 412–431. https://doi.org/10.1016/j.ins.2019.01.002 doi: 10.1016/j.ins.2019.01.002
[11]	J. Lin, L. Zhu, K. Gao, A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem, Expert Syst. Appl., 140 (2020), 112915. https://doi.org/10.1016/j.eswa.2019.112915 doi: 10.1016/j.eswa.2019.112915
[12]	M. Asadujjaman, H. F. Rahman, R. K. Chakrabortty, M. J. Ryan, An Immune Genetic Algorithm for Solving NPV-Based Resource Constrained Project Scheduling Problem, IEEE Access, 9 (2021), 26177–26195. https://doi.org/10.1109/ACCESS.2021.3057366 doi: 10.1109/ACCESS.2021.3057366
[13]	M. Đumić, D. Jakobović, Ensembles of priority rules for resource constrained project scheduling problem, Appl. Soft Comput., 110 (2021), 107606. https://doi.org/10.1016/j.asoc.2021.107606 doi: 10.1016/j.asoc.2021.107606
[14]	O. Shuvo, S. Golder, M. R. Islam, A hybrid metaheuristic method for solving resource constrained project scheduling problem, Evolut. Intell., 16 (2023), 519–537. https://doi.org/10.1007/s12065-021-00675-x doi: 10.1007/s12065-021-00675-x
[15]	H. M. H. Saad, R. K. Chakrabortty, S. Elsayed, M. J. Ryan, Quantum-Inspired Genetic Algorithm for Resource-Constrained Project-Scheduling, IEEE Access, 9 (2021), 38488–38502. https://doi.org/10.1109/ACCESS.2021.3062790 doi: 10.1109/ACCESS.2021.3062790
[16]	R. L. Lilia Kadri, F. F. Boctor, An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case, European J. Operat. Res., 265 (2018), 454–462. https://doi.org/10.1016/j.ejor.2017.07.027 doi: 10.1016/j.ejor.2017.07.027
[17]	J. Lin, L. Zhu, K. Gao, A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem, Expert Syst. Appl., 140 (2020), 112915. https://doi.org/10.1016/j.eswa.2019.112915 doi: 10.1016/j.eswa.2019.112915
[18]	J. Snauwaert, M. Vanhoucke, A new algorithm for resource-constrained project scheduling with breadth and depth of skills, European J. Operat. Res., 292 (2021), 43–59. https://doi.org/10.1016/j.ejor.2020.10.032 doi: 10.1016/j.ejor.2020.10.032
[19]	L. Zhu, J. Lin, Y. Y. Li, Z. J. Wang, A decomposition-based multi-objective genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem, Knowledge-Based Syst., 225 (2021), 107099. https://doi.org/10.1016/j.knosys.2021.107099 doi: 10.1016/j.knosys.2021.107099
[20]	T. Zhou, Q. Long, K. M. Y. Law, C. Wu, Multi-objective stochastic project scheduling with alternative execution methods: An improved quantum-behaved particle swarm optimization approach, Expert Syst. Appl., 203 (2022), 117029. https://doi.org/10.1016/j.eswa.2022.117029 doi: 10.1016/j.eswa.2022.117029
[21]	C. Stiti, O. B. Driss, A new approach for the multi-site resource-constrained project scheduling problem, Proceed. Computer Sci., 164 (2019), 478–484. https://doi.org/10.1016/j.procs.2019.12.209 doi: 10.1016/j.procs.2019.12.209
[22]	D. Q. Huu, N. T. Loc, N. D. Cuong, The R-PSO algorithm solving multi-skill resource-constrained project scheduling problem, J. Milit. Sci. Technol., 5 (2021), 71–82. https://doi.org/10.54939/1859-1043.j.mst.CSCE5.2021.71-82 doi: 10.54939/1859-1043.j.mst.CSCE5.2021.71-82
[23]	J. Joy, S. Rajeev, V. Narayanan, Particle swarm optimization for resource constrained-project scheduling problem with varying resource levels, Proceed. Technol., 25 (2016), 948–954. https://doi.org/10.1016/j.protcy.2016.08.185 doi: 10.1016/j.protcy.2016.08.185
[24]	K. M. Sallam, R. K. Chakrabortty, M. J. Ryan, A two-stage multi-operator differential evolution algorithm for solving Resource Constrained Project Scheduling problems, Future Gener. Computer Syst., 108 (2020), 432–444. https://doi.org/10.1016/j.future.2020.02.074 doi: 10.1016/j.future.2020.02.074
[25]	L. Wu, Y. Wang, S. Zhou, Improved differential evolution algorithm for resource-constrained project scheduling problem, J. Syst. Eng. Electron., 21 (2010), 798–805. https://ieeexplore.ieee.org/abstract/document/6075518
[26]	H. Kazemipoor, R. Tavakkoli-Moghaddam, P. Shahnazari-Shahrezaei, A. Azaron, A differential evolution algorithm to solve multi-skilled project portfolio scheduling problems, Int. J. Adv. Manuf. Technol., 64 (2013), 1099–1111. https://doi.org/10.1007/s00170-012-4045-z doi: 10.1007/s00170-012-4045-z
[27]	J. Sun, Z. Peng, J. Cai, Problem specific genetic differential evolution algorithm for multi-skill resource-constrained project scheduling of collaborative multi-robot systems for search and rescue, in 2021 40th Chinese Control Conference (CCC)., Shanghai, China, (2021), pp. 1808–1813. https://doi.org/10.23919/CCC52363.2021.9549589
[28]	N. T. Loc, Q. D. Pham, A-DEM: The adaptive approximate approach for the real scheduling problem, in: Intelligence of Things: Technologies and Applications (eds N. T. Nguyen, N. N. Dao, Q. D. Pham and H. A. Le), ICIT 2022 Lecture Notes on Data Engineering and Communications Technologies., 148 (2022), Springer, Cham. https://doi.org/10.1007/978-3-031-15063-0_10
[29]	X. S. Yang, Nature-Inspired Metaheuristic Algorithms, Luniver Press, ISBN-13: 978-1-905986-28-6, (2010).
[30]	X. S. Yang, S. Deb, Cuckoo search via Lévy flights, Proc. World Congress Nat. Biol. Inspired Computing (NaBIC 2009), USA, (2009), pp. 210–214. https://doi.org/10.1109/NABIC.2009.5393690
[31]	D. Q. Huu, N. T. Loc, N. D. Cuong, P. T. Toan, New cuckoo search algorithm for the resource constrained project scheduling problem, in 2020 RIVF International Conference on Computing and Communication Technologies (RIVF)., Ho Chi Minh City, Vietnam, (2020), pp. 1–3. https://doi.org/10.1109/RIVF48685.2020.9140728
[32]	H. Maghsoudlou, B. Afshar-Nadjafi, S. T. A. Niaki, Multi-skilled project scheduling with level-dependent rework risk, three multi-objective mechanisms based on cuckoo search, Appl. Soft Comput., 54 (2017), 46–61. https://doi.org/10.1016/j.asoc.2017.01.024 doi: 10.1016/j.asoc.2017.01.024
[33]	Y. Tian, T. Xiong, Z. Liu, Y. Mei, L. Wan, Multi-objective multi-skill resource-constrained project scheduling problem with skill switches: Model and evolutionary approaches, Comput. Industr. Eng., 167, (2022), 107897. https://doi.org/10.1016/j.cie.2021.107897 doi: 10.1016/j.cie.2021.107897
[34]	L. Zhu, J. Lin, Z. J. Wang, A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem, Appl. Soft Comput., 85 (2019), 105805. https://doi.org/10.1016/j.asoc.2019.105805 doi: 10.1016/j.asoc.2019.105805
[35]	R. Kolisch, A. Sprecher, PSPLIB-a project scheduling problem library: or software-ORSEP operations research software exchange program, European J. Oper. Res., 96 (1997), 205–216. https://doi.org/10.1016/S0377-2217(96)00170-1 doi: 10.1016/S0377-2217(96)00170-1
[36]	GArunner tool. Available from: http://imopse.ii.pwr.wroc.pl/rcpsp_spsp_library.html

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)