Optimizing and Solving Project Scheduling Problem for Flexible Networks with Multiple Routes in Production Environments

Document Type : Research Paper


1 Faculty of Industrial Engineering, South Tehran Branch, Islamic Azad University

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

3 azad university of ghazvin


In production environments, multi-route Resource-Constrained Project Scheduling Problem (RCPSP) is more complex and consists of two types of flexible and fixed parts. The flexible parts comprise the semi-finished products and each part has multiple routes denoted independently with activities and predictive relationships. This research develops a new Mixed‐Integer Nonlinear Programming (MINLP) model to minimize the makespan. The proposed mathematical model identifies the optimal routes and, consequently, determines the optimal project network. Also, it allocates renewable resources to each production activity. Production sequencing of activities is optimized by the proposed model. A new hybrid approach by regarding GA and PSO in a binary solving space is introduced to handle two main sub-problems of RCPSP-MR in production environments, namely route selection and production scheduling. To evaluate the presented optimization model and algorithm, 60 test problems in various sizes are reported in detail.


Altaf, M., S., Bouferguene, A., Liu, H., Al-Hussein, M., & Yu, H. (2018). Integrated production planning and control system for a panelized home prefabrication facility using simulation and RFID. Automation in Construction, 85, 369-383.
Baumung, W., Fomin, V., V. (2018). Optimization Model to Extend Existing Production Planning and Control Systems for the Use of Additive Manufacturing Technologies in the Industrial Production. Procedia Manufacturing, 24, 222-228.
Berger, C., Hoffmann, U., Braunreuther, S., & Reinhart, G. (2018). Modeling, simulation, and control of production resource with a control theoretic approach. Procedia CIRP, 67, 122-127.
Besikci, U., Bilge, U., & Ulusoy, G. (2015). Multi mode resource constrained multi-project scheduling and resource portfolio problem. European Journal of Operational Research240(1), 22-31.
Bhargav, A., Sridhar, C., N., V., & Deva Kumar, M., L., S. (2017). Study of Production Scheduling Problem for Reconfigurable Manufacturing System (RMS). International Conference on Advancements in Aeromechanical Materials for Manufacturing (ICAAMM), 4, 7406–7412.
Biondi, M., Sand, G., & Harjunkoski, I. (2017). Optimization of multipurpose process plant operations: A multi-time-scale maintenance and production scheduling approach. Computers and Chemical Engineering, 99, 325-339.
Birjandi, A., Mousavi, S., M., Hajirezaie M., & Vahdani, B. (2019). A new weighted mixed integer nonlinear model and FPND solution algorithm for RCPSP with multi-route work packages under fuzzy uncertainty. Journal of Intelligent & Fuzzy Systems, 37, 737–751.
Chakrabortty, R., K., Sarker, R., A., & Essam, D., L. (2016). Multi-Mode Resource Constrained Project Scheduling Under Resource Disruptions. Computers and Chemical Engineering, 88, 13-29.
Chand, S., Huynh, Q., Singh, H., Ray, T., & Wagner, M. (2018). On the use of genetic programming to evolve priority rules for resource constrained project scheduling problems. Information Sciences, 432, 146-163.
Chiang, P., H., & Torng, C., C. (2016). A production planning and optimization of multi-mode job shop scheduling problem for an avionics manufacturing plan. International Journal of Manufacturing Technology and Management, 30(3/4), 179-195.
Debels, D., & Vanhoucke, M. (2007). A decomposition-based genetic algorithm for the resource constrained project scheduling problem. Operations Research, 55(3), 457–469.
Deblaere, F., Demeulemeester, E., & Herroelen, W. (2011). Reactive scheduling in the multi-mode RCPSP. Computers and Operations Research, 38(1), 63-74.
Dorfeshan, Y., & Mousavi, S., M. (2019). A group TOPSIS-COPRAS methodology with Pythagorean fuzzy sets considering weights of experts for project critical path problem. Journal of Intelligent and Fuzzy Systems, 36(2), 1375-1387.
Duffy, G., Woldesenbet, A., Jeong, D., H., S., & Oberlender, G. D. (2012). Advanced linear scheduling program with varying production rates for pipeline. Automation in Construction, 27, 99–110.
Eberhart, R., C., Shi, Y., & Kennedy, J. (2001). Swarm Intelligence, Swarm Intelligence. A volume in The Morgan Kaufmann Series in Artificial Intelligence.
Fernandes M., A., E., Rodrigues, C., D., & Da Costa, F., A. (2018). A Path-Relinking algorithm for the multi-mode resource-constrained project scheduling problem. Computers and Operations Research92, 145-154.
Fuchigami, H., Y., & Rangel, S. (2018). A survey of case studies in production scheduling: Analysis and perspectives. Journal of Computational Science, 25, 425-436.
Golmakani, H., R., & Birjandi, A., R. (2013). A two-phase algorithm for multiple-route job shop scheduling problem subject to makespan. International Journal of Advanced Manufacturing Technology67(1-4), 203–216.
Golmakani, H., R., & Birjandi, A., R. (2014). Multiple route job shop scheduling using particle swarm optimisation approach. International Journal of Procurement Management, 7(2), 119-144.
Golmakani, H., R., Mills, J., K., & Benhabib, B. (2006). Deadlock-free scheduling and control of flexible manufacturing cells using Automata theory. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 36(2), 327-337.
Golmakani, H., R., Mills, J., K., & Benhabib, B. (2007). On-line scheduling and control of flexible manufacturing cells using Automata theory. International Journal of Computer Integrated Manufacturing, 19(2), 178–193.
Golmakani, H., R., & Namazi, A. (2012). An artificial immune algorithm for multiple-route job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 63(1-4), 77-86.
Hartmann, S., & Briskorn, D. (2010). A survey of variants and extensions of the resource constrained project-scheduling problem. European Journal of Operational Research, 207(1), 1-14.
Kellenbrink, C., & Helber, S. (2015). Scheduling resource-constrained projects with a flexible project structure. European Journal of Operational Research246(2), 379-391.
Kennedy, J., & Eberhart, R., C. (1997). A discrete binary version of the particle swarm algorithm. IEEE International Conference on Systems, Man, and Cybernetics, 5, 4104-4108.
Kopanos, G., M., Kyriakidis, T., S., & Georgiadis, M., C. (2014). New continuous-time and discrete-time mathematical formulations for resource-constrained project scheduling problems. Computers and Chemical Engineering, 68, 96-106.
Le Hesran, C., Ladier, A., L., Botta-Genoulaz, V., & Laforest, V. (2019). Operations scheduling for waste minimization: A review. Journal of Cleaner Production, 206, 211-226.
Liu, M., Chu, F., He, J., Yang, D., & Chu, C. (2019). Coke production scheduling problem: A parallel machine scheduling with batch preprocessing and location-dependent processing times. Computers and Operations Research, 104, 37–48.
Marichelvam, M. K., & Mariappan, G. (2018). A Hybrid Genetic Scatter Search Algorithm to Solve Flexible Job Shop Scheduling Problems: A Hybrid Algorithm for Scheduling Problems. In Soft Computing Techniques and Applications in Mechanical Engineering (pp. 181-194). IGI Global.
Merchan, A., F., Lee, H., & Maravelias, C., T. (2016). Discrete-Time MIP Methods for Production Scheduling in Multistage Facilities. Computer Aided Chemical Engineering, 38, 362-367.
Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6(4), 333–346.
Messelis, T., & Causmaecker, P. D. (2014). An automatic algorithm selection approach for the multi-mode resource-constrained project-scheduling problem. European Journal of Operational Research, 233(3), 511-528.
Mohagheghi, V., Mousavi, S., M., & Vahdani, B. (2016). A new multi-objective optimization approach for sustainable project portfolio selection: A real-world application under interval-valued fuzzy environment. Iranian Journal of Fuzzy Systems, 13(6), 41-68.
Mohagheghi, V., Mousavi, S., M., Vahdani, B., & Siadat, A. (2017). A mathematical modeling approach for high and new technology-project portfolio selection under uncertain environments. Journal of Intelligent and Fuzzy Systems, 32, 4069–4079.
Moradi, N., Mousavi, S., M., & Vahdani, B. (2018). An Interval Type-2 Fuzzy Model for Project-earned Value Analysis Under Uncertainty. Journal of Multiple-Valued Logic and Soft Computing, 30, 79–103.
Nikolakis, N., Kousi, N., Michalos, G., & Makris, S. (2018). Dynamic scheduling of shared human-robot manufacturing operations, Procedia CIRP, 72, 9-14.
Nonaka, Y., Erdos, G., Kis, T., Nakano, T., & Vancza, J. (2012). Scheduling with alternative routings in CNC workshops. CIRP Annals Manufacture Technology, 61(1), 449–454.
Ozguven, C., Ozbakır, L., & Yavuz, Y. (2010). Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 34(1), 1539–1548.
Paraskevopoulos, D., C., Tarantilis, C., D., & Ioannou, G. (2012). Solving Project Scheduling Problems with Resource Constraints via an Event List-based Evolutionary Algorithm. Expert Systems with Applications, 39(4), 3983–3994.
Paraskevopoulos, D., C., Tarantilis, C., D., & Ioannou, G. (2016). An adaptive memory programming framework for the resource-constrained project scheduling problem. International Journal of Production Research, 54(16), 4938-4956.
Peteghem, V., V., & Vanhoucke, M. (2014). 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), 62-72.
Qin, H., Fan, P., Tang, H., Huang, P., Fang, B., & Pan, S. (2019). An effective hybrid discrete grey wolf optimizer for the casting production scheduling problem with multi-objective and multi-constraint. Computers and Industrial Engineering, 128, 458–476.
Qinming, L., Ming, D., Chen, F., F. (2018). Single-machine-based joint optimization of predictive maintenance planning and production scheduling. Robotics and Computer Integrated Manufacturing, 51, 238-247.
Rajabinasab, A., & Mansour, S. (2011). Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach. International Journal of Advanced Manufacture Technology, 54(9-12), 1091-1107.
Sharma, D., Singh, V., & Sharma, C. (2011). GA Based Scheduling of FMS Using Roulette Wheel Selection Process. Proceedings of the International Conference on Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011), 131-940.
Szeredi, R., & Schutt, A. (2016). Modeling and solving multi-mode resource-constrained project scheduling. International Conference on Principles and Practice of Constraint Programming, 9892, 483-492.
Tao, S., & Dong, Z., S. (2018). Multi-mode resource constrained project scheduling problem with alternative project structure. Computers and Industrial Engineering, 125, 333-347.
Tasgetiren, M., F., & Liang, Y., C. (2004). A binary particle swarm optimization algorithm for lot sizing problem. Journal of Economic and Social Research, 5(2), 1–20.
Zareei, S. (2018). Project scheduling for constructing biogas plant using critical path method. Renewable and Sustainable Energy Reviews, 81, 756-759.
Zhang, H., Li, H., & Tam, C., M. (2006). Particle swarm optimization for resource-constrained project scheduling, International Journal of Project Management, 24(1), 83–92.
Zhang, S., & Wong, T., N. (2018). Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning. Journal of Intelligent Manufacturing, 29(3), 585-601.