Designing a resource-constrained project scheduling model considering multiple routes for flexible project activities: Meta-heuristic algorithms

Document Type : Article

Authors

1 Department of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran.

2 Department of Industrial Engineering, Faculty of Engineering, Shahed University, Tehran, Iran

3 Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, P.O. Box 3419759811, Iran

Abstract

Resource constrained project scheduling problem with multiple routes for flexible project activities (RCPSP-MR) is a generalization of the RCPSP, in which for the implementation of each flexible activity in main structure of the project, several exclusive sub-networks are considered. Each sub-network is regarded as a route for the flexible activity. The routes are considered for each flexible activity that are varied in terms of: 1) Number of activities required to execute; 2) Precedence relationship between activates; 3) Allocation of different renewable and nonrenewable resources to each activity; and 4) Effectiveness on the duration and cost of project completion. In this paper, a new mathematical formulation of RCPSP-MR is firstly presented. Then, two solving approaches based on particle swarm optimization (PSO) and genetic algorithm (GA) are proposed to minimize costs of project completion. To evaluate the effectiveness of these proposed approaches, 50 problems (in very small, small, medium, and large-sized test problems) are designed and then are solved; Finally, comparisons are provided. Computational results show that the proposed GA generates high-quality solutions in a timely fashion.

Keywords

Main Subjects

References

References:
 
[1]    Chand, S., Huynh, Q., Singh, H., Ray, T., and Wagner, M. “On the use of genetic programming to evolve priority rules for resource constrained project scheduling problem”, Information Sciences, 432, pp146-163, (2018). 
[2]    Dorfeshan, Y., Mousavi, S.M.,  Vahdani, B., and Siadat, A. “Determining project characteristics and critical path by a new approach based on modified NWRT method and risk assessment under an interval type-2 fuzzy environment”, Scientia Iranica, (Accepted manuscript), Doi: 10.24200/sci.2018.50091.1503, (2018). 
[3]    Dorfeshan, Y., Mousavi, S.M., Mohagheghi, V., and Vahdani, B. “Selecting project-critical path by a new interval type-2 fuzzy decision methodology based on MULTIMOORA, MOOSRA and TPOP methods”, Computers & Industrial Engineering, 120, pp 160-178, (2018). 
[4]    Dorfeshan Y., and Mousavi, S.M. “A new interval type-2 fuzzy decision method with an extended relative preference relation and entropy to project critical path selection”, International Journal of Fuzzy System Applications, 8 (1), pp 19-47, (2019). 
[5]    Mohagheghi, V., Mousavi, S.M., and Vahdani, B. “Analyzing project cash flow by a new interval type-2 fuzzy model with an application to construction industry”, Neural Computing and Applications, 28, pp 3393-3411, (2017). 
[6]    Mohagheghi V., Mousavi, S.M., Vahdani, B., and Siadat, A. “A mathematical modeling approach for high and new technology-project portfolio selection under uncertain environments”, Journal of Intelligent and Fuzzy Systems, 32, pp 4069-4079, (2017).
[7]    Moradi, N., Mousavi, S.M., and Vahdani, B. “An earned value model with risk analysis for project management under uncertain conditions”, Journal of Intelligent and Fuzzy Systems, 32, pp 97-113, (2017).
[8]    Moradi, N., Mousavi, S.M., and Vahdani, B. “An Interval Type-2 Fuzzy Model for Project-earned Value Analysis Under Uncertainty”, Journal of Multiple-Valued Logic and Soft Computing, 30, 79-103, (2018).
[9]    Vanhoucke, M. “Project Management with Dynamic Scheduling”, Springer, Berlin, Heidelberg, online ISBN: 978-3-642-25175-7, (2013).  
[10]    Hartmann, D., and Briskorn, A. “Survey of variants and extensions of the resource constrained project-scheduling problem”. European Journal of Operational Research, 207 (1), pp 1-14, (2010). 
[11]    Okubo, H., Miyamoto, T., Yoshida, S., Mori, K., Kitamura, S., and Izui, Y. “Project scheduling under partially renewable resources and resource consumption during setup operations”, Computers and Industrial Engineering, 83, pp 91-99, (2015). 
[12]    Szeredi, R., and Schutt, A. “Modeling and solving multi-mode resource-constrained project scheduling”. International Conference on Principles and Practice of Constraint, 9892, pp 483-492, (2016). 
[13]    Habibi, F., Barzinpour, F., and Sadjadi, S.J. “Resource-constrained project scheduling problem: review of past and recent developments”, Journal of Project Management, 3 (2), pp 55-88, (2018). 
[14]    Blazewicz, J., Lenstra, J., and Rinnooy Kan, A. “Scheduling subject to resource constraints: classification and complexity”. Discrete Applied Mathematics, 5 (1), pp 11-24, (1983). 
[15]    Zhu, J., Li, X., and Shen, W. “Effective genetic algorithm for resource-constrained project scheduling with limited preemptions”, International Journal of Machine Learning and Cybernetics, 2 (2), pp 55-65, (2011). 
[16]    Agarwal, A., Colak, S., and Erenguc, S. “A neurogenetic approach for the resource-constrained project scheduling problem”. Computers and Operations Research, 38 (1), pp 44-50, (2011). 
[17]    Fang, C., and Wang, L. “An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem”, Computers and Operations Research, 39 (5), pp 890-901, (2012).  
[18]    Zamani, R. “A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem”. European Journal of Operational Research, 229 (2), pp 552-559, (2013). 
[19]    Zeighami, V., Akbari, R., and Ziarati, K. “Development of a Method Based on Particle Swarm Optimization to Solve Resource Constrained Project Scheduling Problem”, Scientia Iranica, 20 (6), pp 2123-2137, (2013). 
[20]    Sahli, A., Carlier, J., and Moukrim, A. “Comparison of mixed integer linear programming models for the Event Scheduling Problem with Consumption and Production of Resources”, IFAC-PapersOnLine, 49 (12), pp 1044-1049, (2016). 
 [21]    Xiao, J., Wu, Z., Hong, X.X., Tang, J.C., and Tang, Y. “Integration of electromagnetism with multi-objective evolutionary algorithms for RCPSP”. European Journal of Operational Research, 251 (1), pp 22-35, (2016).  
[22]    Vanhoucke, M., and Coelho, J. “An approach using SAT solvers for the RCPSP with logical constraints”. European Journal of Operational Research, 249 (2), pp 577-591, (2016).  
[23]    Bibiks, Hu, F., K., Li, J.P., and Smith, A. “Discrete Cuckoo Search for Resource-Constrained Project Scheduling Problem”, IEEE 18th International Conference on Computational Science and Engineering, Doi: 10.1109/CSE.2015.39, (2015).
[24]    Bibiks, K., Hu, Y.F., Li, J.P., Pillai, P., and Smith, A. “Improved discrete cuckoo search for the resource-constrained project scheduling problem”, Applied Soft Computing, 69, pp 493-503, (2018). 
[25]    Fathallahi, F., and Najafi, A. “A hybrid genetic algorithm to maximize net present value of project cash flows in resource-constrained project scheduling problem with fuzzy parameters”, Scientia Iranica, 23 (4), pp 1893-1903, (2016). 
[26]    Gonzalez-Pardo, A., Del Ser, J., and Camacho, D. “Comparative study of pheromone control heuristics in ACO algorithms for solving RCPSP problems”. Applied Soft Computing, 60, pp 241-255, (2017).  
[27]    Kadri, R.L., and Boctor, F.F. “An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case”, European Journal of Operational Research, 265 (2), pp 454 - 462, (2018).
[28]    Coelho, J., and Vanhoucke, M. “An exact composite lower bound strategy for the resource-constrained project scheduling problem”, Computers and Operations Research, 93, pp 135-150, (2018).  
[29]    Chakrabortty, R.K., Sarker, R.A., and Essam, D.L. “Multi-Mode Resource Constrained Project Scheduling Under Resource Disruptions”. Computers and Chemical Engineering, 88, 13-29, (2016). 
[30]    Kopanos, G.M., Kyriakidis, T.S., and Georgiadis, M.C. “New continuous-time and 2 discrete-time mathematical formulations for resource-constrained project scheduling problems”. Computers and Chemical Engineering, 68, pp 96-106, (2014).
[31]    Peteghem, V.V., and Vanhoucke, M. “An experimental investigation of Meta heuristics for the multi-mode resource constrained project-scheduling problem on new dataset instances”. European Journal of Operational Research, 235 (1), pp 62-72, (2014).
[32]    Besikci, U., Bilge, U., and Ulusoy, G. “Multi mode resource constrained multi-project scheduling and resource portfolio problem”. European Journal of Operational Research, 240 (1), pp 22-31, (2015). 
[33]    Fernandes Muritiba, A.E., Rodrigues, C.D., and Da Costa, F.A. “A Path-Relinking algorithm for the multi-mode resource-constrained project scheduling problem”, Computers and Operations Research, 92, pp 145-154, (2018).  
[34]    Van Den Eeckhout, M., Maenhout, B., and Vanhoucke, M. “A heuristic procedure to solve the project staffing problem with discrete time/resource trade-offs and personnel scheduling constraints”, Computers and Operations Research, 101, pp 144-161, (2019). 
[35]    Bellenguez-Morineau, O., and Neron, E. “A Branch-and-Bound Method for Solving Multi-Skill Project Scheduling Problem”, RAIRO Operations Research, 41 (2), pp 155-170, (2007).
[36]    Correia, I., and Saldanha-da-Gama, F. “The impact of fixed and variable costs in a multi-skill project-scheduling problem: An empirical study”, Computers and Industrial Engineering, 72, pp 230-238, (2014). 
[37]    Correia, I., and Saldanha-da-Gama, F. “A modeling framework for project staffing and scheduling problems”. In: Schwindt C., Zimmermann J. (eds) Handbook on Project Management and Scheduling, International Handbooks on Information Systems. Springer, Cham, 1, pp 547-564, (2015). 
[38]    Maghsoudlou, H., Afshar-Nadjafi, B., and Akhavan Niaki, S.T. “A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem”, Computers and Chemical Engineering, 88, pp 157-169, (2016). 
[39]    Javanmard, S., Afshar Nadjafi, B., and Akhavan Niaki, S.T. “Preemptive multi-skilled resource investment project scheduling problem: Mathematical modelling and solution approaches”, Computers and Chemical Engineering, 96, pp 55-68, (2017).  
[40]    Wang, L., and Zheng, X.L. “A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem”. Swarm and Evolutionary Computation, 38, pp 54-63, (2018). 
[41]    Myszkowski, P., Olech, L., Laszczyk, M., and Skowroński, M. “Hybrid Differential Evolution and Greedy Algorithm (DEGR) for solving Multi-Skill Resource-Constrained Project Scheduling Problem”. Applied Soft Computing, 62, pp 1-14, (2018). 
[42]    Benjaafar. S., Talavage. J., and Ramakrishnan, R. “The effect of routing and machine flexibility on the performance of manufacturing systems”. International Journal of Computer Integrated Manufacture, 8 (4), pp 265-276, (1995). 
[43]    Chan, F.T.S. “The effects of routing flexibility on a flexible manufacturing system”, International Journal of Computer Integrated Manufacturing, 14 (5), pp 431-445, (2001). 
[44]    Yu, X., Ram, B. “Bio-inspired scheduling for dynamic job shops with flexible routing and sequence-dependent setups”. International Journal of Production Research, 44 (22), pp 4793-4813, (2006). 
[45]    Golmakani, H.R., and Birjandi, A.R. “A two-phase algorithm for multiple-route job shop scheduling problem subject to makespan”, International Journal of Advanced Manufacturing Technology, 67 (1-4), pp 203-216, (2013). 
[46]    Golmakani, H.R., and Birjandi, A.R. “Multiple route job shop scheduling using particle swarm optimisation approach”, International Journal of Procurement Management, 7 (2), pp 119-144, (2014). 
[47]    Golmakani, H.R., Mills, J.K., and Benhabib, B. “Deadlock-free scheduling and control of flexible manufacturing cells using Automata theory”, IEEE Transactions Systems, 36, pp 327-337, (2006). 
[48]    Golmakani, H.R., Mills, J.K., and Benhabib, B. “On-line scheduling and control of flexible manufacturing cells using Automata theory”, International Journal of Computer Integrated Manufacture, 19 (2), pp 178-193, (2007). 
[49]    Golmakani, H.R., and Namazi, A. “An artificial immune algorithm for multiple-route job shop scheduling problem”, International Journal of Advanced Manufacturing Technology, 63, pp 77-86, (2012). 
[50]    Kellenbrink, C., and Helber, S. “Scheduling resource-constrained projects with a flexible project structure”, European Journal of Operational Research, 246 (2), pp 379-391, (2015).  
[51]    Tao, S., and Dong, Z.S. “Multi-mode resource constrained project scheduling problem with alternative project structure”, Computers and Industrial Engineering, 125, pp 333-347, (2018).  
[52]    Nonaka, Y., Erdos, G., Kis, T., Nakano, T., and Vancza, J. “Scheduling with alternative routings in CNC workshops”, CIRP Annals Manufacture Technology, 61 (1), pp 449-454, (2012). 
[53]    Ozguven, C., Ozbakır, L., and Yavuz, Y. “Mathematical models for job-shop scheduling problems with routing and process plan flexibility”, Applied Mathematical Modelling, 34 (1), pp 1539-1548, (2010). 
[54]    Rajabinasab, A., and Mansour, S. “Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach”, International Journal of Advanced Manufacture Technology, 54 (9-12), pp 1091-1107, (2011). 
[55]    Rossi, A., and Dini, G. “Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method”, Robotics and Computer-Integrated Manufacturing, 23 (5), pp 503-516, (2007). 
[56]    Roshanaei, V., Vahdani, B., Mousavi, S.M., Mousakhani, M., and Zhang, G. “CAD/CAM System Selection: A Multi-Component Hybrid Fuzzy MCDM Model”, Arabian Journal for Science and Engineering, 38 (9), pp 2579-2594, (2013).
[57]    Tavakkoli-Moghaddam, R., Heydar, M., and Mousavi, S.M. “A hybrid genetic algorithm for a bi-objective scheduling problem in a flexible manufacturing cell”, International Journal of Engineering, Transaction A: Basics, 23 (3-4), pp 235-252, (2010).
[58]    Sharma, D., Singh, V., and Sharma, C. “GA Based Scheduling of FMS Using Roulette Wheel Selection Process”, Proceedings of the International Conference on SocProS, AISC, 131, pp 931-940, (2011). 
[59]    Holland, J.H., and Koza, J.R. “Genetic Programming: On the Programming of Computers by Means of Natural Selection”. MIT Press, ISBN: 0-262-61084-1, (1998).
[60]    Yassine, A.A., Mostafa, O., and Browning, T.R. “Scheduling Multiple, Resource-Constrained, Iterative, Product Development Projects with Genetic Algorithms”, Computers and Industrial Engineering, 107, pp 39-56, (2017). 
[61]    Zhang, H., Xie, J., Ge, J., Zhang, Z., and Zong, B. “A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar”, European Journal of Operational Research, 272 (3), pp 868-878, (2019). 
[62]    Kennedy, J., and Eberhart, R. “Particle swarm optimization”, Proceedings of IEEE International Conference on Neural Networks, 4, pp 1942-1948, (1995). 
[63]    Mousavi, S.M., Vahdani, B., and Abdollahzade, M. “An intelligent model for cost prediction in new product development projects”, Journal of Intelligent and Fuzzy Systems, 29 (5), pp 2047-2057, (2015). 
[64]    Bewoor, L.A., Prakash, V.C., and Sapkal, S.U. “Production scheduling optimization in foundry using hybrid Particle Swarm Optimization algorithm”, Procedia Manufacturing, 22, pp 57-64, (2018). 
[65]    Joy, J., Rajeev, S., and Narayanan, V. “Particle Swarm Optimization for Resource Constrained-project Scheduling Problem with Varying Resource Levels”, Procedia Technology, 25, pp 948-954, (2016). 
[66]    Poli, R., Kennedy, J. and Blackwell, T. “Particle swarm optimization: an overview”, Swarm Intelligence Journal, 1 (1), pp 33-57, (2007). 
[67]    Li, J.Q., Pan, Q.K., Xie, S.X., Jia, B.X., and Wang, Y.T. “A hybrid particle swarm optimization and tabu search algorithm for flexible job-shop scheduling problem”, The International Journal of Computer Theory and Engineering, 2 (2), pp 189-194, (2010). 
Scientia Iranica
Volume 27, Issue 5 - Serial Number 5
Transactions on Industrial Engineering (E)
September and October 2020
Pages 2572-2591

Files

History

  • Receive Date: 13 April 2018
  • Revise Date: 30 October 2018
  • Accept Date: 16 February 2019

Share

How to cite

Statistics