This paper addresses the Multi-Skill Resource-Constrained Project Scheduling Problem with Transfer Times (MSRCPSP-TT). A new model has been developed that incorporates the presence of transfer times within the multi-skill RCPSP. The proposed model aims to minimize project’s duration and cost, concurrently. The MSRCPSP-TT is an NP-hard problem; therefore, a Multi-Objective Multi-Agent Optimization Algorithm (MOMAOA) is proposed to acquire feasible schedules. In the proposed algorithm, each agent represents a feasible solution that works with other agents in a grouped environment. The agents evolve due to their social, autonomous, and self-learning behaviors. Moreover, the adjustment of environment helps the evolution of agents as well. Since the MSRCPSP-TT is a multi-objective optimization problem, the Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) is used in different procedures of the MOMAOA. Another novelty of this paper is the application of TOPSIS in different procedures of the MOMAOA. These procedures are utilized for: (1) detecting the leader agent in each group, (2) detecting the global best leader agent, and (3) the global social behavior of the MOMAOA. The performance of the MOMAOA has been analyzed by solving several benchmark problems. The results of the MOMAOA have been validated through comparisons with three other meta-heuristics. The parameters of algorithms are determined by the Response Surface Methodology (RSM). The Kruskal–Wallis test is implemented to statistically analyze the efficiency of methods. Computational results reveal that the MOMAOA can beat the other three methods according to several testing metrics. Furthermore, the impact of transfer times on project’s duration and cost has been assessed. The investigations indicate that resource transfer times have significant impact on both objectives of the proposed model.
Keywords: Multi-agent systems, multi-objective optimization, multi-skill RCPSP, resource transfer times, TOPSIS
@article{RO_2021__55_4_2093_0,
author = {Hosseinian, Amir Hossein and Baradaran, Vahid},
title = {A multi-objective multi-agent optimization algorithm for the multi-skill resource-constrained project scheduling problem with transfer times},
journal = {RAIRO. Operations Research},
pages = {2093--2128},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021087},
mrnumber = {4282589},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021087/}
}
TY - JOUR AU - Hosseinian, Amir Hossein AU - Baradaran, Vahid TI - A multi-objective multi-agent optimization algorithm for the multi-skill resource-constrained project scheduling problem with transfer times JO - RAIRO. Operations Research PY - 2021 SP - 2093 EP - 2128 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021087/ DO - 10.1051/ro/2021087 LA - en ID - RO_2021__55_4_2093_0 ER -
%0 Journal Article %A Hosseinian, Amir Hossein %A Baradaran, Vahid %T A multi-objective multi-agent optimization algorithm for the multi-skill resource-constrained project scheduling problem with transfer times %J RAIRO. Operations Research %D 2021 %P 2093-2128 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021087/ %R 10.1051/ro/2021087 %G en %F RO_2021__55_4_2093_0
Hosseinian, Amir Hossein; Baradaran, Vahid. A multi-objective multi-agent optimization algorithm for the multi-skill resource-constrained project scheduling problem with transfer times. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2093-2128. doi: 10.1051/ro/2021087
[1] , and , A multi-agent system for distributed multi-project scheduling: an auction-based negotiation approach. Eng. Appl. Artif. Intell. 25 (2012) 1738–1751. | DOI
[2] and , An introduction to multi-agent systems, edited by and . In: Vol. 310 ofInnovations in Multi-Agent Systems and Applications – 1. Studies in Computational Intelligence. Springer, Berlin, Heidelberg (2010). DOI: 10.1007/978-3-642-14435-61.
[3] and , Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills, edited by and . In: Vol. 3616 of Practice and Theory of Automated Timetabling V. PATAT 2004. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg (2005) 229–243. | DOI
[4] , and , Scheduling subject to resource constraints: classification and complexity. Disc. Appl. Math. 5 (1983) 11–24. | MR | Zbl | DOI
[5] , and , A multi-agent approach for the capacity allocation problem. Int. J. Prod. Econ. 66 (2000) 269–285. | DOI
[6] , and , Using a multi-agent approach to optimize the train coupling and sharing system. Eur. J. Oper. Res. 134 (2001) 242–252. | Zbl | DOI
[7] , , and , A robust genetic algorithm to solve multi-skill resource constrained project scheduling problem with transfer time and uncertainty skills. In: 2020 IEEE 16th International Conference on Control & Automation (ICCA), Singapore, 9–11 Oct. (2020). DOI: 10.1109/ICCA51439.2020.9264319. | DOI
[8] , , and , -out-of- systems: an exact formula for the stationary availability and multi-objective configuration design based on mathematical programming and TOPSIS. J. Comput. Appl. Math. 330 (2018) 1007–1015. | MR | DOI
[9] and , Framework of agent-based intelligence system with two-stage decision-making process for distributed dynamic scheduling. Appl. Soft Comput. 7 (2007) 229–245. | DOI
[10] , , , and , An efficient hybrid algorithm for resource-constrained project scheduling. Inf. Sci. 180 (2010) 1031–1039. | DOI
[11] , , and , A multi-objective model for multi-project scheduling and multi-skilled staff assignment for IT product development considering competency evolution. Int. J. Prod. Res. 55 (2017) 6207–6234. | DOI
[12] , and , A market-based multi-agent system model for decentralized multi-project scheduling. Ann. Oper. Res. 150 (2007) 115–135. | MR | Zbl | DOI
[13] and , The impact of fixed and variable costs in a multi-skill project scheduling problem: an empirical study. Comput. Ind. Eng. 72 (2014) 230–238. | DOI
[14] , , and , New effective differential evolution algorithm for the project scheduling problem. In: 2020 2nd International Conference on Computer Communication and the Internet (ICCCI), Nagoya, Japan, 26–29 June (2020). DOI: 10.1109/ICCCI49374.2020.9145982. | DOI
[15] , , and , 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, 14–15 Oct. (2020). DOI: 10.1109/RIVF48685.2020.9140728. | DOI
[16] , , and , Effective evolutionary algorithm for solving the real-resource-constrained scheduling problem. J. Adv. Transp. 2020 (2020). DOI: 10.1155/2020/8897710. | DOI
[17] , and , An improved tabu search for multi-skill resource-constrained project scheduling problems under step-deterioration. Arab. J. Sci. Eng. 43 (2018) 3279–3290. | DOI
[18] , , and , A general variable neighbourhood search for multi-skill resource-constrained project scheduling problem with step-deterioration. Int. J. Ind. Syst. Eng. 34 (2020) 145–164.
[19] , , and , A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6 (2000) 182–197. | DOI
[20] , , , and , Two-agent stochastic flow shop deteriorating scheduling via a hybrid multi-objective evolutionary algorithm. J. Intell. Manuf. 30 (2019) 2257–2272. | DOI
[21] , and , An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem. Int. J. Prod. Res. 51 (2013) 641–651. | DOI
[22] , , , and , Competence-driven project portfolio selection, scheduling and staff assignment. Cent. Eur. J. Oper. Res. 16 (2008) 281–306. | MR | Zbl | DOI
[23] , and , A novel Pareto-based multi-objective vibration damping optimization algorithm to solve multi-objective optimization problems. Sci. Iran. Trans. E 21 (2014) 2368–2378.
[24] , , , , and , A multi-agent-based system for two-stage scheduling problem of offshore project. Adv. Mech. Eng. 9 (2017) 1–17.
[25] and , A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207 (2010) 1–14. | MR | Zbl | DOI
[26] and , Experimental investigation of heuristics for resource-constrained project scheduling: an update. Eur. J. Oper. Res. 174 (2006) 23–37. | Zbl | DOI
[27] , and , A study on the project scheduling based on multi-agent systems. Math. Pract. Theory 1 (2005) 43–47.
[28] and , Scheduling and staffing multiple projects with a multi-skilled workforce. OR Spectr. 32 (2010) 343–368. | MR | Zbl | DOI
[29] , A multi-agent system for the decentralized resource-constrained multi-project scheduling problem. Int. Trans. Oper. Res. 14 (2007) 565–599. | Zbl | DOI
[30] and , A multi-objective multi-agent optimization algorithm for the community detection problem. J. Inf. Syst. Telecommun. 6 (2019) 169–179.
[31] and , Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: a dandelion solution approach. J. Ind. Syst. Eng. (JISE) 12 (2019) 72–99.
[32] and , An evolutionary algorithm based on a hybrid multi-attribute decision making method for the multi-mode multi-skilled resource-constrained project scheduling problem. J. Optim. Ind. Eng. 12 (2019) 155–178.
[33] and , P-GWO and MOFA: two new algorithms for the MSRCPSP with the deterioration effect and financial constraints (case study of a gas treating company). Appl. Intell. 50 (2020) 2151–2176. | DOI
[34] and , Modified Pareto archived evolution strategy for the multi-skill project scheduling problem with generalized precedence relations. J. Ind. Eng. Manage. Stud. (JIEMS) 7 (2020) 59–86.
[35] , and , Modeling of the time-dependent multi-skilled RCPSP considering learning effect: an evolutionary solution approach. J. Model. Manage. (JM2) 14 (2019) 521–558. | DOI
[36] , and , Preemptive multi-skilled resource investment project scheduling problem; mathematical modelling and solution approaches. Comput. Chem. Eng. 96 (2016) 55–68. | DOI
[37] , and , A roadmap of agent research and development. Auton. Agents Multi-Agent Syst. 1 (1998) 7–38. | DOI
[38] and , An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: the single mode case. Eur. J. Oper. Res. 265 (2018) 454–462. | MR | DOI
[39] , , and , A differential evolution algorithm to solve multi-skilled project portfolio scheduling problems. Int. J. Adv. Manuf. Tech. 64 (2013) 1099–1111. | DOI
[40] and , Agent-based project scheduling: computational study of large problems. IIE Trans. 35 (2003) 143–159. | DOI
[41] , and , Agent-based project scheduling. IIE Trans. 32 (2000) 387–401. | DOI
[42] and , A heuristic solution framework for the resource constrained (multi-) project scheduling problem with sequence-dependent transfer times. Eur. J. Oper. Res. 197 (2009) 492–508. | Zbl | DOI
[43] and , Managing and modelling general resource transfers in (multi-) project scheduling. OR Spectr. 32 (2010) 369–394. | MR | Zbl | DOI
[44] and , Improved selection in evolutionary multi-objective optimization of multi-skill resource-constrained project scheduling problem. Inf. Sci. 481 (2019) 412–431. | MR | DOI
[45] , and , Multi-agent based dynamic resource scheduling for distributed multiple project using a market mechanism. J. Intell. Manuf. 14 (2003) 471–484. | DOI
[46] and , An iterative scheduling technique for resource constrained project scheduling. Eur. J. Oper. Res. 56 (1992) 370–379. | Zbl | DOI
[47] and , Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm. J. Sched. 12 (2009) 281–298. | MR | Zbl | DOI
[48] , and , Multi-agent oriented constraint satisfaction. Artif. Intell. 136 (2002) 101–144. | MR | Zbl | DOI
[49] , and , A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Syst. App. 140 (2020) 112915. | DOI
[50] and , Optimizing linear project scheduling with multi-skilled crews. Autom. Construct. 24 (2012) 16–23. | DOI
[51] , and , A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem. Comput. Chem. Eng. 8 (2016) 157–169. | DOI
[52] , and , Multi-skilled project scheduling with level-dependent rework risk; three multi-objective mechanisms based on cuckoo search. Appl. Soft Comput. 54 (2017) 46–61. | DOI
[53] , and , Application of response surface methodology for Glucan production from leuconostoc dextranicum and its structural characterization. Carbohydr. Polym. 75 (2009) 150–156. | DOI
[54] , , , , and , A multi-agent based cooperative approach to scheduling and routing. Eur. J. Oper. Res. 254 (2016) 169–178. | MR | Zbl | DOI
[55] , and , A bi-objective aggregate production planning problem with learning effect and machine deterioration: modeling and solution. Comput. Oper. Res. 91 (2018) 21–36. | MR | Zbl | DOI
[56] and , 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 (2013). DOI: 10.1109/IEEM.2013.6962442.
[57] , , and , Branch-and-price approach for the multi-skill project scheduling problem. Optim. Lett. 8 (2014) 1721–1734. | MR | Zbl | DOI
[58] , , and , Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem. Soft Comput. 19 (2015) 3599–3619. | DOI
[59] , , and , Hybrid differential evolution and greedy algorithm (DEGR) for solving multi-skill resource-constrained project scheduling problem. Appl. Soft Comput. 62 (2018) 1–14. | DOI
[60] , and , Multi-skill project scheduling problem and total productive maintenance. In: Proceedings of 3rd Multidisciplinary International Conference on Scheduling: Theory and Application (MISTA 2007), Paris, France (2007) 608–610.
[61] and , A flow-based tabu search algorithm for the RCPSP with transfer times. OR Spectr. 38 (2016) 305–335. | MR | Zbl | DOI
[62] , , , and , A biogeography-based optimisation algorithm for a realistic no-wait hybrid flow shop with unrelated parallel machines to minimise mean tardiness. Int. J. Comput. Integr. Manuf. 29 (2016) 1007–1024. | DOI
[63] , and , A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem. Appl. Soft Comput. 13 (2013) 1728–1740. | DOI
[64] , Fault tolerant design using single and multicriteria genetic algorithms optimization, Master’s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA (1995).
[65] , and , A two-phase method for a multi-skilled project scheduling problem with discounted cash flows. Sci. Iran. 21 (2014) 1083–1095.
[66] , , and , QMAEA: a quantum multi-agent evolutionary algorithm for multi-objective combinatorial optimization. Simulation 90 (2014) 182–204. | DOI
[67] , , , and , Novel feedback-based operators in solving multi-skill resource-constrained project scheduling problem. In: 2020 Chinese Control And Decision Conference (CCDC), Hefei, China, 2020, 22–24 Aug. (2020) 296–301. DOI: 10.1109/CCDC49329.2020.9164711. | DOI
[68] , and , A hybrid metaheuristic for resource-constrained project scheduling with flexible resource profiles. Eur. J. Oper. Res. 262 (2017) 262–273. | MR | Zbl | DOI
[69] and , A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm Evol. Comput. 38 (2018) 54–63. | DOI
[70] and , Intelligent agents: theory and practice. Knowl. Eng. Rev. 10 (1995) 115–152. | DOI
[71] , and , Application of multi-agent system in project management. Int. J. Prod. Econ. 68 (2000) 185–197. | DOI
[72] , A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem. Eur. J. Oper. Res. 229 (2013) 552–559. | MR | Zbl | DOI
[73] and , A multi-agent optimization algorithm for resource constrained project scheduling problem. Expert Syst. App. 42 (2015) 6039–6049. | DOI
[74] , and , Teaching–learning-based optimization algorithm for multi-skill resource constrained project scheduling problem. Soft Comput. 21 (2015) 1537–1548. | DOI
[75] , , and , A multi-agent genetic algorithm for global numerical optimization. IEEE Trans. Syst. Man Cybern. B, Cybern. 34 (2004) 229–244. | DOI
[76] , and , A discrete oppositional multi-verse optimization algorithm for multi-skill resource constrained project scheduling problem. Appl. Soft Comput. 85 (2019) 105805. | DOI
[77] and , Multi-objective optimization using evolutionary algorithms a comparative case study, edited by , , and . In: Fifth International Conference on Parallel Problem Solving from Nature (PPSN-V). Berlin, Germany (1998) 292–301. | DOI
Cité par Sources :
