A Hybrid Algorithm Based on Non-Dominatedsorting Ant Colony and Genetic Algorithmsfor Solving Multi-Objective Multi-Mode Projectscheduling Problems Under Resource Constraints

• Autorzy: Jafar Bagherinejad , Fariborz Jolai , Raheleh Abdollahnejad , Mahnaz Shoeib
• Języki publikacji: EN

Abstrakty

EN

A project scheduling problem investigates a set of activities that have to be scheduleddue to precedence priority and resource constraints in order to optimize project-relatedobjective functions. This paper focuses on the multi-mode project scheduling problem concerning resource constraints (MRCPSP). Resource allocation and leveling, renewable andnon-renewable resources, and time-cost trade-off are some essential characteristics which areconsidered in the proposed multi-objective scheduling problem. In this paper, a novel hybridalgorithm is proposed based on non-dominated sorting ant colony optimization and geneticalgorithm (NSACO-GA). It uses the genetic algorithm as a local search strategy in order toimprove the efficiency of the ant colony algorithm. The test problems are generated based onthe project scheduling problem library (PSPLIB) to compare the efficiency of the proposedalgorithm 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-IIalgorithm.(original abstract)

Słowa kluczowe

EN

Project planning; Optimalization; Algorithms

PL

Planowanie projektu; Optymalizacja; Algorytmy

• Czasopismo: Management and Production Engineering Review
• Rocznik: 2020
• Tom: 11
• Numer: nr 2
• Strony: 88--98

Twórcy

autor

Jafar Bagherinejad

• Alzahra University, Tehran, Iran

autor

Fariborz Jolai

• Tehran University, Tehran, Iran

autor

Raheleh Abdollahnejad

• Alzahra University, Tehran, Iran

autor

Mahnaz Shoeib

• Alzahra University, Tehran, Iran

Bibliografia

• Dumić M., Sisejković D., Corić R., Jakobović D., Evolving priority rules for resource-constrained project scheduling problem with genetic program- ming, Future Generation Computer Systems, 86, 211-221, 2018.
• Elsayed S., Sarker R., Ray T., Coello C.C., Consolidated optimization algorithm for resource- constrained project scheduling problems, Informa- tion Sciences, 418-419, 346-362, 2017.
• Zhi C., Demeulemeester E, Sijun B., Yuntao G., Efficient priority rules for the stochastic resource- constrained project scheduling problem, European Journal of Operational Research, 270, 3, 957-967, 2018.
• Creemers S. The preemptive stochastic resource con- strained project scheduling problem, European Jour- nal of Operational Research, 277, 1, 238-247, 2019.
• Elmaghraby S.E., Activity networks: Project plan- ning and control by network models, Wiley, New York, 1977.
• Chand S., Singh H., Ray T., Evolving heuristics for the resource-constrained project scheduling problem with dynamic resource disruptions, Swarm and Evo- lutionary Computation, 44, 897-912, 2019.
• Singh G., Ernst A.T., Resource constraint schedul- ing with a fractional shared resource, Operations Research Letters, 39, 5, 363-368, 2011.
• 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.
• Sprecher A., Hartmann S., Drexl A., An exact al- gorithm for project scheduling with multiple modes, OR Spektrum, 19, 3, 195-230, 1997.
• Hartmann S., Drexl A., Project scheduling with mul- tiple modes: a comparison of exact algorithms, Net- works: An International Journal, 32, 4, 283-297, 1998.
• Sprecher A., Drexl A., Multi-mode resource- constrained project scheduling by a simple, general and powerful sequencing algorithm, European Jour- nal of Operational Research, 107, 2, 431-450, 1998.
• Zhu G., Bard J.F., Yu G., A branch-and-cut proce- dure for the multi-mode resource-constrained project scheduling problem, Informs Journal on Computing, 18, 3, 377-390, 2006.
• Ozdamar L., Ulusoy G., A local constraint based analysis approach to project scheduling under general resource constraints, European Journal of Op- erational Research, 79, 2, 287-298, 1994.
• Drexl A., Grunewald J., Nonpreemptive multi-mode resource- constrained project scheduling, IIE Trans- actions, 25, 5, 74-81, 1993.
• 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.
• Lova A., Tormos P., Cervantes M., Barber F., An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple exe- cution modes, International Journal of Production Economics, 117, 2, 302-316, 2009.
• 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 al- gorithm, Automation in Construction, 30, 216-227, 2013.
• Kellenbrink C., Helber S., Scheduling resource- constrained projects with a flexible project structure, European Journal of Operational Research, 246, 2, 379-391, 2015.
• 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.
• 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.
• Li H., Zhang H., Ant colony optimization - based multi-mode scheduling under renewable and nonre- newable resource constraints, Automation in Con- struction, 35, 431-438, 2013.
• Chen R.M., Particle swarm optimization with jus- tification and designed mechanisms for resource- constrained project scheduling problem, Expert Systems with Applications, 38, 6, 7102-7111, 2011.
• Pellerin R., Perrier N., Berthaut F.A., Survey of hybrid metaheuristics for the resource-constrained project scheduling problem, European Journal of Op- erational Research, 280, 2, 395-416, 2020.
• Tao S., Dong Z.S., Multi-mode resource-constrained project scheduling problem with alternative project structures, Computers and Industrial Engineering, 125, 333-347, 2018.
• Ke H., Liu B., Project scheduling problem with stochastic activity duration times, Applied Mathematics and Computation, 168, 1, 342-353, 2005.
• Eshtehardian E., Afshar A., Abbasnia R., Fuzzy- based MOGA approach to stochastic time-cost trade- off problem, Automation in Construction, 18, 5, 692-701, 2009.
• Kalhor E., Khanzadi M., Eshtehardian E., Afshar A., Stochastic time-cost optimization using non-dominated archiving ant colony approach, Automa- tion in Construction, 20, 8, 1193-1203, 2011.
• 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.
• Sonmez R., Bettemir O.H., A hybrid genetic algo rithm for the discrete time-cost trade-off problem, Expert Systems with Applications, 39, 13, 1142811434, 2012.
• El-kholy A.M., Time-cost trade-off analysis con- sidering funding variability and time uncertainty, Alexandria Engineering Journal, 52, 1, 113-121, 2013.
• Fen C.W., Liu L., Burns S.A., Using genetic algorithm to solve construction time-cost trade-off prob- lems, Journal of Computing in Civil Engineering, 11, 3, 184-189, 1997.
• Zheng D., Ng S., Kumaraswamy M., Applying a ge- netic algorithm-based multi-objective approach for time-cost optimization, Journal of Construction En- gineering and Management, 130, 2, 168-176, 2004.
• 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.
• Afshar A., Ziaraty A., Kaveh A., Sharifi F., Non- dominated archiving multi-colony ant algorithm in time-cost trade-off optimization, Journal of Construction Engineering and Management, 135, 7, 668-674, 2009.
• Tavana M., Abtahi A.R., Khalili-Damghani K., A new multi-objective multi-mode model for solv- ing preemptive time-cost-quality trade-off project scheduling problems, Expert Systems with Applica- tions, 41, 4, 1830-1846, 2014.
• Ponz-Tienda J.L., Yepes V., Pellicer E., Moreno- Flores J., The Resource Leveling Problem with multiple resources using an adaptive genetic algorithm, Automation in Construction, 29, 161-172, 2013.
• Nudtasomboon N., Randhawa S.U., Resource- constrained project scheduling with renewable and non-renewable resources and time-resource trade- offs, Computers and Industrial Engineering, 32, 1, 227-242, 1997.
• Alsayegh H., Hariga M., Hybrid meta-heuristic methods for the multi-resource leveling problem with activity splitting, Automation in Construction, 27, 89-98, 2012.
• 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.
• Chiang C.W., Huang Y.Q., Wang W.Y., Ant colony optimization with parameter adaptation for multimode resource-constrained project scheduling, Journal of Intelligent and Fuzzy Systems, 19, 4, 345-358, 2008.
• Dorigo M., Optimization, learning and natural algorithms, Ph.D.Thesis Politecnico di Milano, Italy, 1992.
• Dorigo M., Birattari M., Stutzle T., Ant colony optimization, IEEE Computational Intelligence Magazine, 1, 4, 28-39, 2006.
• Akpinar 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.
• 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.
• ---

Identyfikatory

DOI

0.24425/mper.2020.133731