An Evolutionary Algorithm Based on a Hybrid Multi-Attribute Decision Making Method for the Multi-Mode Multi-Skilled Resource-constrained Project Scheduling Problem
الموضوعات :
Amir Hossein Hosseinian
1
,
Vahid Baradaran
2
1 - Department of Industrial Engineering, Faculty of Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran
2 - Department of Industrial Engineering, Faculty of Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran
الکلمات المفتاحية: Meta-heuristics, Optimization, MADM, RCPSP, Multi-skilled resources,
ملخص المقالة :
This paper addresses the multi-mode multi-skilled resource-constrained project scheduling problem. Activities of real world projects often require more than one skill to be accomplished. Besides, in many real-world situations, the resources are multi-skilled workforces. In presence of multi-skilled resources, it is required to determine the combination of workforces assigned to each activity. Hence, in this paper, a mixed-integer formulation called the MMSRCPSP is proposed to minimize the completion time of project. Since the MMSRCPSP is strongly NP-hard, a new genetic algorithm is developed to find optimal or near-optimal solutions in a reasonable computation time. The proposed genetic algorithm (PGA) employs two new strategies to explore the solution space in order to find diverse and high-quality individuals. Furthermore, the PGA uses a hybrid multi-attribute decision making (MADM) approach consisting of the Shannon’s entropy method and the VIKOR method to select the candidate individuals for reproduction. The effectiveness of the PGA is evaluated by conducting numerical experiments on several test instances. The outputs of the proposed algorithm is compared to the results obtained by the classical genetic algorithm, harmony search algorithm, and Neurogenetic algorithm. The results show the superiority of the PGA over the other three methods. To test the efficiency of the PGA in finding optimal solutions, the make-span of small size benchmark problems are compared to the optimal solutions obtained by the GAMS software. The outputs show that the proposed genetic algorithm has obtained optimal solutions for 70% of test problems.
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., Rahimi, A., & Karimi, H., (2012). An Exact Algorithm for the Mode Identity Project Scheduling Problem, Journal of Optimization in Industrial Engineering, 10, 55-63.
Agarwal, A., Colak, S., & Erenguc, S., (2011). A Neurogenetic approach for the resource-constrained project scheduling problem, Computers & Operations Research, 38, 44-50.
Agarwal, A., Colak, S., & Erenguc, S., (2015). Metaheuristic Methods, in: Schwindt, C., Zimmermann, J., (Eds.), Handbook on Project Management and Scheduling Vol.1, Springer International Publishing. New York, 57-74.
Al-Anzi, F.S., Al-Zame, K., & Allahverdi, A., (2010). Weighted Multi-Skill Resources Project Scheduling, Journal of Software Engineering & Applications, 3(12), 1125-1130.
Almeida, B.F., Correia, I., & Saldanha-da-Gama, F., (2016). Priority-based heuristics for the multi-skill resource constrained project scheduling problem, Expert Systems with Applications, 57(15), 91–103.
Azaron, A., Katagiri, H., Sakawa, M., Kato, K., & Memariani, A., (2006). A multi-objective resource allocation problem in PERT networks. European Journal of Operational Research, 172(3), 838-854.
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.
Bellenguez, O., & Néron, E., (2007). A branch-and-bound method for solving multi-skill project scheduling problem, Rairo Operations Research, 41, 155-170.
Blazewicz, J., Lenstra, J.K. & Kan, A., (1983). Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5(1), 11-24.
Bouleimen, K., & Lecocq, H., (2003). A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version, European Journal of Operational Research, 149(2), 268-281.
Chen, R., Liang, C., Gu, D., and 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), 1-29.
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(6), 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.
Deb K., Pratap, A., Agrawal S., & Meyarivan, T., (2002). A Fast and Elitist Multi-objective Genetic Algorithm: NSGA-II, IEEE transactions on evolutionary computation, 6(2), 182-197.
Firat, M., & Hurkens, C.A.J., (2012). An improved MIP-based approach for a multi-skill workforce scheduling problem, Journal of Scheduling, 15(3), 363-380.
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(3), 641-651.
Gomar, J., Haas, C., & Morton, D., (2002). Assignment and Allocation Optimization of Partially Multiskilled Workforce, Journal of construction engineering and management, 128(2), 103-109.
Gutjahr, W.J., Katzensteiner, S., Reiter, P., Stummer, C., & Denk, M., (2008). Competence-driven project portfolio selection, scheduling and staff assignment, Central European Journal of Operations Research, 16(3), 281-306.
Gutjahr, W. J., Katzensteiner, S., Reiter, P., Stummer, C., & Denk, M., (2010). Multi-objective decision analysis for competence-oriented project portfolio selection, European Journal of Operational Research, 205(3), 670-679.
Hassanpour, J., Ghodoosi, M., & Hosseini, Z.S., (2017). Optimizing a Bi-objective Preemptive Multi-mode Resource-Constrained Project Scheduling Problem: NSGA-II and MOICA Algorithms, Journal of Optimization in Industrial Engineering, 21, 79-91.
Hartmann, S., & Kolisch, R., (2000). Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem, European Journal of Operational Research, 127, 394-407.
Hegazy, T., Shabeeb, K., Elbeltagi, E., & Cheema, T., (2000). Algorithm for scheduling with multiskilled constrained resources, Journal of construction engineering and management, 126(6), 414-421.
Hermerl, C., & Kolisch, R., (2010). Scheduling and staffing multiple projects with a multi-skilled workforce, OR Spectrum, 32, 343-368.
Hosseini, Z.S., Hassanpour, J., & Roghanian, E., (2014). A Bi-objective Pre-emption Multi-mode Resource Constrained Project Scheduling Problem with due Dates in the Activities, Journal of Optimization in Industrial Engineering, 15, 15-25.
Javanmard, S., 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(1), 55-68.
Kadrou, Y., & Najid, N.M., (2006). Tabu Search Algorithm for the MRCPSP with Multi-Skilled Labor, in: Proc. Comput. Eng. Syst. Appl., IMACS Multi-conference, 1302-1309.
Kazemipoor, H., Tavakkoli-Moghaddam, R., Shahnazari-Shahrezaei, P., & Azaron, A., (2013). A differential evolution algorithm to solve multi-skilled project portfolio scheduling problems, The International Journal of Advanced Manufacturing Technology, 64(5-8), 1099-1111.
Kazemipoor, H., Tavvakoli-Moghaddam, E., & Sharezaei, P., (2013). Solving a novel multi-skilled project scheduling model by scatter search, South African Journal of Industrial Engineering, 24(1), 121-135.
Li, H., & Womer, K., (2009). A Decomposition Approach for Shipboard Manpower Scheduling, Military Operations Research, 14, 1-25.
Li, W., & Womer, K., (2009). Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm, Journal of Scheduling, 12, 281-298.
Lotfi, F.H., & Fallahnejad, R., (2010). Imprecise Shannon’s Entropy and Multi Attribute Decision Making, Entropy, 12, 53-62.
Maghsoudlou, H.M., 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(1), 157-169.
Maghsoudlou, H.M., 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, Proceedings of the 2013 IEEE IEEM, Bangkok, Thailand.
Mehdizadeh, E., & Kivi, A.F., (2014). Three Metaheuristic Algorithms for Solving the Multi-item Capacitated Lot-sizing Problem with Product Returns and Remanufacturing, Journal of Optimization in Industrial Engineering, 16, 41-53.
Miller, B., & Goldberg, D.E., (1996). Genetic algorithms, selection schemes, and the varying effects of noise, Evolutionary Computation, 4(2), 113-131.
Montoya, C., Bellenguez-Morineau, O., Pinson, E., & Rivera. D., (2014). Branch-and-price approach for the multi-skill project scheduling problem, Optimization Letters, 8(5), 1721-1734.
Myszkowski, P.B, & Skowronski, M., (2013). Specialized genetic operators for multi skill resource-constrained project scheduling problem, 19th International Conference on Soft Computing MENDEL, 57-62.
Myszkowski, P.B., Skowronski, M., & Podlodowski, L., (2013). Novel heuristic solutions for Multi–Skill Resource–Constrained Project Scheduling Problem, Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, 159-166.
Myszkowski, P.B., Skowronski, M., Olech, L.P., & Oslizlo, K., (2015). Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem, Soft Computing, 19(12), 3599-3619.
Nader, B., (2013). The Project Portfolio Selection and Scheduling Problem: Mathematical Model and Algorithms, Journal of Optimization in Industrial Engineering, 13, 65-72.
Najafi, A.A., & Salimi, M., (2018). Modeling and Solution Procedure for a Preemptive Multi-Objective Multi-Mode Project Scheduling Model in Resource Investment Problems, Journal of Optimization in Industrial Engineering, 11(1), 181-190.
Opricovic, S., & Tzeng, G. H., (2004). Compromise Solution by MCDM Methods: A comparative analysis of VIKOR and TOPSIS, European Journal of Operational Research, 156, 445-455.
Opricovic, S., & Tzeng, G. H., (2007). Extended VIKOR method in comparison with outranking methods, European Journal of Operational Research, 178, 514–529.
Ranjbar, M., Kianfar, F., & Shadrokh, S., (2008). Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm, Applied Mathematics and Computation, 196, 879-888.
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(3), 1083-1095.
Valls, V., Perez, A., & Quintanilla, S., (2009). Skilled workforce scheduling in Service Centers, European Journal of Operational Research, 193(3), 791-804.
Walter, M., & Zimmermann, J., (2016). Minimizing average project team size given multi-skilled workers with heterogeneous skill levels. Computers & Operations Research, 70, 163–179.
Wu, M., & Sun, S., (2006). A project scheduling and staff assignment model considering learning effect, The International Journal of Advanced Manufacturing Technology, 28(11), 1190-1195.
Yaghoubi, S., Noori, S., Azaron, A., & Tavakkoli-Moghaddam, R., (2011). Resource allocation in dynamic PERT networks with finite capacity, European Journal of Operational Research, 215(3), 670-678.
Yaghoubi, S., Noori, S., Azaron, A., & Fynes, B., (2015). Resource allocation in multi-class dynamic PERT networks with finite capacity, European Journal of Operational Research, 247(3), 879-894.
Zheng, H., Wang, L., & Zheng, X., (2015). Teaching–learning-based optimization algorithm for multiskill resource constrained project scheduling problem, Soft Computing, 21(6), 1537-1548.
