Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: A dandelion solution approach

Document Type : Research Paper

Authors

Department of Industrial Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran

Abstract

This paper proposes a new mixed-integer model for the multi-skill resource-constrained project scheduling problem (MSRCPSP). The interactions between workers are represented as undirected networks. Therefore, for each required skill, an undirected network is formed which shows the relations of human resources. In this paper, community detection in networks is used to find the most compatible working groups to perform project activities. In this respect, a greedy algorithm (GRA) is proposed to detect the most compatible communities of workers. The proposed greedy algorithm maximizes modularity as a well-known objective to find high-quality communities of workers. Besides, a new heuristic is developed to assign workers to activities based on the communities obtained by the GRA. The MSRCPSP is an NP-hard optimization problem with the objective of minimizing the makespan of the project. Therefore, a dandelion algorithm (DA), which is a meta-heuristic, is proposed to solve the problem. The dandelion algorithm is used to solve test problems of the iMOPSE dataset. To validate the outputs of the proposed method, three other meta-heuristics including genetic algorithm (GA), harmony search (HS) algorithm, and differential evolution (DE) method are employed. The Taguchi method is hired to tune all algorithms. These algorithms are compared with each other in terms of several performance measures. The results show the superiority of the dandelion algorithm in terms of all performance measures.

Keywords

Main Subjects

References

Afruzi, E., Najafi, A.A., Roghanian, E., & Mazinani, M. (2014). A Multi-Objective Imperialist Competitive Algorithm for solving discrete time, cost and quality trade-off problems with mode-identity and resource-constrained situations. Computers & Operations Research, 50, 80-96.
Afshar-Nadjafi, B., Karimi, H., Rahimi, A., & Khalili, S. (2015). Project scheduling with limited resources using an efficient differential evolution algorithm. Journal of King Saud University, 27(2), 176-184.
Bellenguez, O., & Néron, E. (2005). Lower Bounds for the Multi-skill Project Scheduling Problem with Hierarchical Levels of Skills. Practice and Theory of Automated Timetabling V, 3616, 229-243.
Blazewicz, J., Lenstra, J.K. & Kan, A. (1983). Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics, 5, 11-24.
Brandes, U., Delling, D., & Gaetler, M. (2008). On Modularity Clustering. Transactions on Knowledge and Data Engineering, 20(2), 172-188.
Chand, S., Huynh, Q., Singh, H., Ray, T., & Wagner, M. (2018). On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems. Information Sciences, 432, 146-163.
Chen, M., Kuzmin, K., Boleslaw, K., & Szymanski, F. (2014). Community Detection via Maximization of Modularity and Its Variants. IEEE Transactions on Computational Social Systems, 1(1), 46-65.
Chen, R., Liang, C., Gu, D., & Leung, J. (2017). A multi-objective model for multi-project scheduling and multi-skilled staff assignment for IT product development considering competency evolution. International Journal of Production Research, 55(21), 6207-6234.
Cordeau, J., Laporte, G., Pasin, F., & Ropke, S. (2010). Scheduling technicians and tasks in a telecommunications company. Journal of Scheduling, 13(4), 393-409.
Corominas, A., Ojeda, J., & Pastor, R. (2005). Multi-objective allocation of multi-function workers with lower bounded capacity. Journal of the Operational Research Society, 56, 738-743
Correia, I., & Saldanha-da-Gama, F. (2014). The impact of fixed and variable costs in a multi-skill project scheduling problem: An empirical study. Computers & Industrial Engineering, 72, 230-238.
Dai, H., Cheng, W., & Guo, P. (2018). An Improved Tabu Search for Multi-skill Resource-Constrained Project Scheduling Problems under Step-Deterioration. Arabian Journal for Science and Engineering, 1, 1-12.
Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3), 1–100.
Gao, J., Chen, R., & Deng, W., (2013). An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 51, 641-651.
Giran, O., Temur, R., & Bekdas, G. (2017). Resource constrained project scheduling by harmony search algorithm. KSCE Journal of Civil Engineering, 21(2), 479-487.
Gong, C., Han, S., Li, X., Zhao, L., & Liu, X. (2017). A new dandelion algorithm and optimization for extreme learning machine. Journal of Experimental & Theoretical Artificial Intelligence, 30(1), 39-52.
Handl, J., & Knowles, J. (2007). An evolutionary approach to multiobjective clustering, IEEE transactions on Evolutionary Computation, 11, 56-76.
Hartmann, S. (1998). A competitive genetic algorithm for resource‐constrained project scheduling. Naval Research Logistics, 45(7), 733-750.
Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 207, 1-14.
Javanmard, S., Afshar-Nadjafi, B., & Niaki, S.T.A. (2016). Preemptive multi-skilled resource investment project scheduling problem; mathematical modelling and solution approaches. Computers and Chemical Engineering, 96, 55-68.
Kazemipoor, H., Tavvakoli-Moghaddam, R., & Shahnazari-Shahrezaei, P. (2013). Solving a novel multi-skilled project scheduling model by scatter search. South African Journal of Industrial Engineering, 24, 121-135.
Kolisch, R., & Hartmann, S. (1999). Heuristic Algorithms for the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis. In: Węglarz J. (eds) Project Scheduling. International Series in Operations Research & Management Science, vol 14. Springer, Boston, MA.
Leyman, P., Van Driessche, N., Vanhoucke, M., & De Causmaecker, P. (2019). The impact of solution representations on heuristic net present value optimization in discrete time/cost trade-off project scheduling with multiple cash flow and payment models. Computers & Operations Research, 103, 184-197.
Li, H., & Womer, K. (2009). Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm. Journal of Scheduling, 12, 281-298.
Li, X., Han, S., Zhao, L., Gong, C., Liu, X. (2017). New Dandelion Algorithm Optimizes Extreme Learning Machine for Biomedical Classification Problems. Computational Intelligence and Neuroscience, 1, 1-13.
Maenhout, B., & Vanhoucke, M. (2018). A perturbation matheuristic for the integrated personnel shift and task re-scheduling problem. European Journal of Operational Research, 269(3), 806-823.
Maghsoudlou, H.M., Afshar-Nadjafi, B., & Niaki, S.T.A. (2016). A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem. Computers and Chemical Engineering, 8, 157-169.
Maghsoudlou, H.M., Afshar-Nadjafi, B., & Niaki, S.T.A. (2017). Multi-skilled project scheduling with level-dependent rework risk; three multi-objective mechanisms based on cuckoo search. Applied Soft Computing, 54, 46-61.
Mehmanchi, E., & Shadrokh, S. (2013). Solving a New Mixed Integer Non-Linear Programming Model of the Multi-Skilled Project Scheduling Problem Considering Learning and Forgetting Effect. In: Proceedings of the 2013 IEEE IEEM, Bangkok, Thailand, 1-5.
Montoya, C., Bellenguez, O., Pinson, E., & Rivera, D. (2014). Branch-and-price approach for the multi-skill project scheduling problem. Optimization Letters, 8(5), 1721-1734.
Mousavi, S.M., Alikar, N., & Niaki, S.T.A. (2016). An improved fruit fly optimization algorithm to solve the homogeneous fuzzy series–parallel redundancy allocation problem under discount strategies. Soft Computing, 20(6), 2281-2307.
Myszkowski, P., Olech, L.P., Laszczyk, M., & Skowronski, M. (2018). Hybrid Differential Evolution and Greedy Algorithm (DEGR) for solving Multi-Skill Resource-Constrained Project Scheduling Problem. Applied Soft Computing, 63, 1-14.
Myszkowski, P., Skowronski, M., Olech, L.P., & Oslizlo, K. (2015). Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem. Soft Computing, 19, 3599-3619.
Newman, M., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 1-15.
Pessan, C., Morineau, O., & Néron, E. (2007). Multi-skill Project Scheduling Problem and Total Productive Maintenance. In: Proceedings of 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA 2007), 608-610, Paris, France.
Rahimi, S., Abdollahpouri, A., & Moradi, P. (2018). A multi-objective particle swarm optimization algorithm for community detection in complex networks. Swarm and Evolutionary Computation, 39, 297-309.
Rostami, S., Creemers, S., & Leus, R. (2018). New strategies for stochastic resource-constrained project scheduling. Journal of Scheduling, 21(3), 349-365.
Shi, C., Yan, Z., Wang, Y., Cai, Y., & Wu, B. (2010). A Genetic Algorithm for Detecting Communities in Largescale Complex Networks. Advance in Complex System, 13(1), 3-17.
Tabrizi, B.H., Tavvakoli-Moghaddam, R., & Ghaderi, S.F. (2014). A two-phase method for a multi-skilled project scheduling problem with discounted cash flows. Scientia Iranica, 21, 1083-1095.
Valls, V., Perez, A., & Quintanilla, S. (2009). Skilled workforce scheduling in Service Centers. European Journal of Operational Research, 193, 791-804.
Van Den Eeckhout, M., Maenhout, B., & Vanhoucke, M. (2019). A heuristic procedure to solve the project staffing problem with discrete time/resource trade-offs and personnel scheduling constraints. Computers & Operations Research, 101, 144-161.
Wang, L., & Zheng, X.L. (2018). A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm and Evolutionary Computation, 38, 54-63.
Wu, M., & Sun, S. (2006). A project scheduling and staff assignment model considering learning effect. The International Journal of Advanced Manufacturing Technology, 28, 1190-1195.
Zammori, F., & Bertolini, M. (2015). A Conceptual Framework for Project Scheduling with Multi-skilled Resources. International Conference on Artificial Intelligence and Industrial Engineering (AIIE 2015), 375-378, Phuket, Thailand.
Zheng, H., Wang, L., & Zheng, X., (2015). Teaching–learning-based optimization algorithm for multiskill resource constrained project scheduling problem. Soft Computing, 21, 1537-1548.

Files

History

  • Receive Date: 22 July 2018
  • Revise Date: 09 December 2018
  • Accept Date: 24 December 2018

Share

How to cite

Statistics