A hybrid algorithm based on non-dominated sorting ant colony and genetic algorithmsfor solving multi-objective multi-mode project scheduling problems under resource constraints

• Autorzy: Bagherinejad Jafar , Jolai Fariborz , Abdollahnejad Raheleh , Shoeib Mahnaz

Identyfikatory

DOI

10.24425/mper.2020.133731

• Języki publikacji: EN

Abstrakty

EN

A project scheduling problem investigates a set of activities that have to be scheduled due to precedence priority and resource constraints in order to optimize project-related objective functions. This paper focuses on the multi-mode project scheduling problem concerning resource constraints (MRCPSP). Resource allocation and leveling, renewable and non-renewable resources, and time-cost trade-off are some essential characteristics which are considered in the proposed multi-objective scheduling problem. In this paper, a novel hybrid algorithm is proposed based on non-dominated sorting ant colony optimization and genetic algorithm (NSACO-GA). It uses the genetic algorithm as a local search strategy in order to improve the efficiency of the ant colony algorithm. The test problems are generated based on the project scheduling problem library (PSPLIB) to compare the efficiency of the proposed algorithm with the non-dominated sorting genetic algorithm (NSGA-II). The numerical result verifies the efficiency of the proposed hybrid algorithm in comparison to the NSGA-II algorithm.

Słowa kluczowe

EN

multi-objectives project scheduling; ant colony algorithm; time-cost trade-off; resource leveling

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2020
• Tom: Vol. 11, No. 2
• Strony: 88--98
• Opis fizyczny: Bibliogr. 44 poz., rys., tab., wykr.

Twórcy

autor

Bagherinejad Jafar

• Department of Industrial Engineering, Faculty of Engineering, Alzahra University, Tehran, Iran

autor

Jolai Fariborz

• Department of Industrial Engineering, Faculty of Engineering, Alzahra University, Tehran, Iran

autor

Abdollahnejad Raheleh

• Department of Industrial Engineering, Faculty of Engineering, Alzahra University, Tehran, Iran

autor

Shoeib Mahnaz

• Department of Industrial Engineering, Faculty of Engineering, Alzahra University, Tehran, Iran

Bibliografia

• [1] Dumić M., Šišejković D., Čorić R., Jakobović D., Evolving priority rules for resource-constrained project scheduling problem with genetic programming, Future Generation Computer Systems, 86, 211–221, 2018.
• [2] Elsayed S., Sarker R., Ray T., Coello C.C., Consolidated optimization algorithm for resourceconstrained project scheduling problems, Information Sciences, 418–419, 346–362, 2017.
• [3] Zhi C., Demeulemeester E, Sijun B., Yuntao G., Efficient priority rules for the stochastic resourceconstrained project scheduling problem, European Journal of Operational Research, 270, 3, 957–967, 2018.
• [4] Creemers S. The preemptive stochastic resource constrained project scheduling problem, European Journal of Operational Research, 277, 1, 238–247, 2019.
• [5] Elmaghraby S.E., Activity networks: Project planning and control by network models, Wiley, New York, 1977.
• [6] Chand S., Singh H., Ray T., Evolving heuristics for the resource-constrained project scheduling problem with dynamic resource disruptions, Swarm and Evolutionary Computation, 44, 897–912, 2019.
• [7] Singh G., Ernst A.T., Resource constraint scheduling with a fractional shared resource, Operations Research Letters, 39, 5, 363–368, 2011.
• [8] Weglarz J., Jozefowska J., Mika M., Waligora G., Project scheduling with finite or infinite number of activity processing modes – A survey, European Journal of Operational Research, 208, 3, 177–205, 2011.
• [9] Sprecher A., Hartmann S., Drexl A., An exact algorithm for project scheduling with multiple modes, OR Spektrum, 19, 3, 195–230, 1997.
• [10] Hartmann S., Drexl A., Project scheduling with multiple modes: a comparison of exact algorithms, Networks: An International Journal, 32, 4, 283–297, 1998.
• [11] Sprecher A., Drexl A., Multi-mode resourceconstrained project scheduling by a simple, general and powerful sequencing algorithm, European Journal of Operational Research, 107, 2, 431–450, 1998.
• [12] Zhu G., Bard J.F., Yu G., A branch-and-cut procedure for the multi-mode resource-constrained project scheduling problem, Informs Journal on Computing, 18, 3, 377–390, 2006.
• [13] Ozdamar L., Ulusoy G., A local constraint based analysis approach to project scheduling under general resource constraints, European Journal of Operational Research, 79, 2, 287–298, 1994.
• [14] Drexl A., Grunewald J., Nonpreemptive multi-mode resource-constrained project scheduling, IIE Transactions, 25, 5, 74–81, 1993.
• [15] Peteghem V.V., Vanhoucke M., A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem, European Journal of Operational Research, 201, 2, 409–418, 2010.
• [16] Lova A., Tormos P., Cervantes M., Barber F., An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes, International Journal of Production Economics, 117, 2, 302–316, 2009.
• [17] Ghoddousi P., Eshtehardian E., Jooybanpour Sh., Javanmardi A., Multi-mode resource-constrained discrete time-cost-resource optimization in project scheduling using non-dominated sorting genetic algorithm, Automation in Construction, 30, 216–227, 2013.
• [18] Kellenbrink C., Helber S., Scheduling resourceconstrained projects with a flexible project structure, European Journal of Operational Research, 246, 2, 379–391, 2015.
• [19] Baradaran S., Fatemi Ghomi S.M.T., Ranjbar M., Hashemin S.S., Multi-mode renewable resource constrained allocation in PERT networks, Applied Soft Computing, 12, 1, 82–90, 2012.
• [20] Mika M., Waligóra G., Węglarz J., Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times, European Journal of Operational Research, 187, 3, 1238–1250, 2008.
• [21] Li H., Zhang H., Ant colony optimization – based multi-mode scheduling under renewable and nonrenewable resource constraints, Automation in Construction, 35, 431–438, 2013.
• [22] Chen R.M., Particle swarm optimization with justification and designed mechanisms for resourceconstrained project scheduling problem, Expert Systems with Applications, 38, 6, 7102–7111, 2011.
• [23] Pellerin R., Perrier N., Berthaut F.A., Survey of hybrid metaheuristics for the resource-constrained project scheduling problem,EuropeanJournalofOperational Research, 280, 2, 395–416, 2020.
• [24] Tao S., Dong Z.S., Multi-mode resource-constrained project scheduling problem with alternative project structures, Computers and Industrial Engineering, 125, 333–347, 2018.
• [25] Ke H., Liu B., Project scheduling problem with stochastic activity duration times, Applied Mathematics and Computation, 168, 1, 342–353, 2005.
• [26] Eshtehardian E., Afshar A., Abbasnia R., Fuzzybased MOGA approach to stochastic time-cost tradeoff problem, Automation in Construction, 18, 5, 692–701, 2009.
• [27] Kalhor E., Khanzadi M., Eshtehardian E., Afshar A., Stochastic time-cost optimization using nondominated archiving ant colony approach, Automation in Construction, 20, 8, 1193–1203, 2011.
• [28] Chen S.P., Tsai M.J., Time-cost trade-off analysis of project networks in fuzzy environments, European Journal of Operational Research, 212, 2, 386–397, 2011.
• [29] Sonmez R., Bettemir O.H., A hybrid genetic algorithm for the discrete time-cost trade-off problem, Expert Systems with Applications, 39, 13, 11428– 11434, 2012.
• [30] El-kholy A.M., Time-cost trade-off analysis considering funding variability and time uncertainty, Alexandria Engineering Journal, 52, 1, 113–121, 2013.
• [31] Fen C.W., Liu L., Burns S.A., Using genetic algorithm to solve construction time-cost trade-off problems, Journal of Computing in Civil Engineering, 11, 3, 184–189, 1997.
• [32] Zheng D., Ng S., Kumaraswamy M., Applying a genetic algorithm-based multi-objective approach for time-cost optimization, Journal of Construction Engineering and Management, 130, 2, 168–176, 2004.
• [33] Ng S., Zhang Y., Optimizing construction time and cost using ant colony optimization approach, Journal of Construction Engineering and Management, 134, 9, 721–728, 2008.
• [34] Afshar A., Ziaraty A., Kaveh A., Sharifi F., Nondominated archiving multi-colony ant algorithm in time-cost trade-off optimization, Journal of Construction Engineering and Management, 135, 7, 668–674, 2009.
• [35] Tavana M., Abtahi A.R., Khalili-Damghani K., A new multi-objective multi-mode model for solving preemptive time-cost-quality trade-off project scheduling problems, Expert Systems with Applications, 41, 4, 1830–1846, 2014.
• [36] Ponz-Tienda J.L., Yepes V., Pellicer E., MorenoFlores J., The Resource Leveling Problem with multiple resources using an adaptive genetic algorithm, Automation in Construction, 29, 161–172, 2013.
• [37] Nudtasomboon N., Randhawa S.U., Resourceconstrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs, Computers and Industrial Engineering, 32, 1, 227–242, 1997.
• [38] Alsayegh H., Hariga M., Hybrid meta-heuristic methods for the multi-resource leveling problem with activity splitting, Automation in Construction, 27, 89–98, 2012.
• [39] Geng J.O., Weng L.P., Liu S.H., An improved ant colony optimization algorithm for nonlinear resource-leveling problems, Computers and Mathematics with Applications, 61, 8, 2300–2305, 2011.
• [40] Chiang C.W., Huang Y.Q., Wang W.Y., Ant colony optimization with parameter adaptation for multi-mode resource-constrained project scheduling, Journal of Intelligent and Fuzzy Systems, 19, 4, 345–358, 2008.
• [41] Dorigo M., Optimization, learning and natural algorithms, Ph.D.Thesis Politecnico di Milano, Italy, 1992.
• [42] Dorigo M., Birattari M., Stutzle T., Ant colony optimization, IEEE Computational Intelligence Magazine, 1, 4, 28–39, 2006.
• [43] Akpınar A., Bayhan G.M., Baykasoglu A., Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence dependent setup times between tasks, Applied Soft Computing, 13, 1, 574–589, 2013.
• [44] Nabipoor Afruzi E., Roghanian E., Najafi A.A., Mazinani M., A multi-mode resource-constrained discrete time-cost tradeoff problem solving using an adjusted fuzzy dominance genetic algorithm, Scientia Iranica, 20, 3, 931–944, 2013.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).