Optimization of parallel machine scheduling problem with human resiliency engineering: A new hybrid meta-heuristics approach

Document Type: Research note


School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


This paper proposes a mixed integer programming model to solve a non-identical parallel machine (NIPM) scheduling with sequence-dependent set-up times and human resiliency engineering. The presented mathematical model is formulated to consider human factors including Learning, Teamwork and Awareness. Moreover, processing time of jobs are assumed to be non-deterministic and dependent to their start time which leads to more precision and reality. The applicability of the proposed approach is demonstrated in a real world car accessories industrial unit. A hybrid metaheuristic method based on Genetic algorithm (GA) and simulated annealing (SA) is proposed to solve the problem. Parameter tuning is applied for adjustment of metaheuristic algorithm parameters.The superiority of the proposed hybrid metaheuristic method is evaluated by comparing the obtained results to GAMS, and two other hybrid metaheuristics. Moreover, it is shown that the hybrid approach provides better solutions than other hybrid approaches.


Main Subjects

Akhshabi, M, Tavakkoli-Moghaddam, R, & Rahnamay-Roodposhti, F. (2014). A hybrid particle swarm optimization algorithm for a no-wait flow shop scheduling problem with the total flow time. The International Journal of Advanced Manufacturing Technology, 70(5-8), 1181-1188.

Afzalirad, M., & Shafipour, M. (2018). Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions. Journal of Intelligent Manufacturing, 29(2), 423-437.

Alimoradi, S, Hematian, M, & Moslehi, G. (2016). Robust scheduling of parallel machines considering total flow time. Computers & Industrial Engineering, 93, 152-161.

Azadeh, A, Habibnejad-Ledari, H, Abdolhossein Zadeh, S, & Hosseinabadi Farahani, M. (2016). A single-machine scheduling problem with learning effect, deterioration and non-monotonic time-dependent processing times. International Journal of Computer Integrated Manufacturing, 1-13.

Azadeh, A, Salmanzadeh-Meydani, N, & Motevali-Haghighi, S. (2017a). Performance optimization of an aluminum factory in economic crisis by integrated resilience engineering and mathematical programming. Safety science, 91, 335-350.

Azadeh, Ali, Yazdanparast, Reza, Zadeh, Saeed Abdolhossein, & Zadeh, Afshin Esmail. (2017b). Performance optimization of integrated resilience engineering and lean production principles. Expert Systems with Applications, 84, 155-170.

Baez, Sarahi, Angel-Bello, Francisco, & Alvarez, Ada. (2016). Time-dependent formulations for minimizing total completion time in a parallel machine scheduling problem with dependent setup times. IFAC-PapersOnLine, 49(12), 857-862.

Biskup, Dirk. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1), 173-178.

Chang, P. C., Chen, S. H., & Lin, K. L. (2005). Two‐phase sub population genetic algorithm for parallel machine-scheduling problem. Expert Systems with Applications, 29(3), 705-712.

Farahani, Mehdi Hosseinabadi, & Hosseini, Leila. (2013). Minimizing cycle time in single machine scheduling with start time-dependent processing times. The International Journal of Advanced Manufacturing Technology, 64(9-12), 1479-1486.

Fanjul-Peyro, L., Perea, F., & Ruiz, R. (2017). Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. European Journal of Operational Research, 260(2), 482-493.

Ghodratnama, A, Rabbani, Masoud, Tavakkoli-Moghaddam, R, & Baboli, A. (2010). Solving a single-machine scheduling problem with maintenance, job deterioration and learning effect by simulated annealing. Journal of Manufacturing Systems, 29(1), 1-9.

Guo, Qingxin, & Tang, Lixin. (2015). An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Applied Soft Computing, 29, 184-195.

Hosseini, N, & Tavakkoli-Moghaddam, R. (2013). Two meta-heuristics for solving a new two-machine flowshop scheduling problem with the learning effect and dynamic arrivals. The International Journal of Advanced Manufacturing Technology, 65(5-8), 771-786.

Liao, T. W., Chang, P. C., Kuo, R. J., & Liao, C. J. (2014). A comparison of five hybrid metaheuristic algorithms for unrelated parallel-machine scheduling and inbound trucks sequencing in multi-door cross docking systems. Applied Soft Computing, 21, 180-193.

Lin, S. W., & Ying, K. C. (2015). A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems. International Journal of Production Research, 53(4), 1065-1076.

Low, Chinyao, & Lin, Wen-Yi. (2013). Some scheduling problems with time-dependent learning effect and deteriorating jobs. Applied Mathematical Modelling, 37(20), 8865-8875.

Majumder, A., Laha, D., & Suganthan, P. N. (2018). A hybrid cuckoo search algorithm in parallel batch processing machines with unequal job ready times. Computers & Industrial Engineering, 124, 65-76.

Martello, S., Soumis, F., & Toth, P. (1997). Exact and approximation algorithms for makespan minimization on unrelated parallel machines. Discrete applied mathematics, 75(2), 169-188.

Mehdizadeh, Esmaeil, Tavakkoli-Moghaddam, Reza, & Yazdani, Mehdi. (2015). A vibration damping optimization algorithm for a parallel machines scheduling problem with sequence-independent family setup times. Applied Mathematical Modelling, 39(22), 6845-6859.

Mir, Mir Saber Salehi, & Rezaeian, Javad. (2016). A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines. Applied Soft Computing, 41, 488-504.

Mirabi, Mohammad, Ghomi, SMT Fatemi, & Jolai, Fariborz. (2013). A two-stage hybrid flowshop scheduling problem in machine breakdown condition. Journal of Intelligent Manufacturing, 24(1), 193-199.

Nasiri, Mohammad Mahdi, Yazdanparast, Reza, & Jolai, Fariborz. (2017). A simulation optimisation approach for real-time scheduling in an open shop environment using a composite dispatching rule. International Journal of Computer Integrated Manufacturing, 30(12), 1239-1252.

Rabbani, M., Heidari, R., Farrokhi-Asl, H., & Rahimi, N. (2018). Using metaheuristic algorithms to solve a multi-objective industrial hazardous waste location-routing problem considering incompatible waste types. Journal of Cleaner Production, 170, 227-241.

Ramezani, Pezhman, Rabiee, Meysam, & Jolai, Fariborz. (2015). No-wait flexible flowshop with uniform parallel machines and sequence-dependent setup time: a hybrid meta-heuristic approach. Journal of Intelligent Manufacturing, 26(4), 731-744.

Rostami, Mohammad, Pilerood, Amir Ebrahimzadeh, & Mazdeh, Mohammad Mahdavi. (2015). Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment. Computers & Industrial Engineering, 85, 206-215.

Ruiz-Torres, Alex J, Paletta, Giuseppe, & PéRez, Eduardo. (2013). Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects. Computers & Operations Research, 40(8), 2051-2061.

Santos, H. G., Toffolo, T. A., Silva, C. L., & Vanden Berghe, G. (2019). Analysis of stochastic local search methods for the unrelated parallel machine scheduling problem. International Transactions in Operational Research, 26(2), 707-724.

Shirali, Gh A, Motamedzade, M, Mohammadfam, I, Ebrahimipour, V, & Moghimbeigi, A. (2015). Assessment of resilience engineering factors based on system properties in a process industry. Cognition, Technology & Work, 1-13.

Shirvani, Nargess, Ruiz, Rubén, & Shadrokh, Shahram. (2014). Cyclic scheduling of perishable products in parallel machine with release dates, due dates and deadlines. International Journal of Production Economics, 156, 1-12.

Tanaka, Shunji, & Araki, Mituhiko. (2013). An exact algorithm for the single-machine total weighted tardiness problem with sequence-dependent setup times. Computers & Operations Research, 40(1), 344-352.

Tavakkoli-Moghaddam, R, & Mehdizadeh, E. (2007). A new ILP model for identical parallel-machine scheduling with family setup times minimizing the total weighted flow time by a genetic algorithm. International Journal of Engineering Transactions A Basics, 20(2), 183.

Tavakkoli-Moghaddam, Reza, Taheri, Farid, Bazzazi, Mohammad, Izadi, M, & Sassani, Farrokh. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Computers & Operations Research, 36(12), 3224-3230.

 Tian, H., Yu, S., & Luo, W. (2019). Parallel Machine Scheduling on Jobs and Partial Maintenance Activities due to job-Dependent Machine Deteriorations. American Journal of Mathematical and Management Sciences, 1-11.

Wang, H., & Alidaee, B. (2019). Effective heuristic for large-scale unrelated parallel machines scheduling problems. Omega, 83, 261-274.

Wreathall, John. (2006). Properties of resilient organizations: an initial view Resilience engineering: Concepts and precepts (pp. 275-286): Ashgate, Aldershot, UK.

Wu, Wen-Hsiang, Xu, Jianyou, Wu, Wen-Hung, Yin, Yunqiang, Cheng, I-Fan, & Wu, Chin-Chia. (2013). A tabu method for a two-agent single-machine scheduling with deterioration jobs. Computers & Operations Research, 40(8), 2116-2127.

Yang, Hong-an, Sun, Qi-feng, Saygin, Can, & Sun, Shu-dong. (2012). Job shop scheduling based on earliness and tardiness penalties with due dates and deadlines: an enhanced genetic algorithm. The International Journal of Advanced Manufacturing Technology, 61(5-8), 657-666.

Yilmaz Eroglu, D., Ozmutlu, H. C., & Ozmutlu, S. (2014). Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times. International Journal of Production Research, 52(19), 5841-5856.

Yin, Y., Wang, Y., Cheng, T. C. E., Liu, W., & Li, J. (2017). Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega, 69, 17-28.

Yin, Yunqiang, Wu, Wen-Hung, Cheng, TCE, & Wu, Chi-Chia. (2015). Single-machine scheduling with time-dependent and position-dependent deteriorating jobs. International Journal of Computer Integrated Manufacturing, 28(7), 781-790.

Zhang, Yebin, Wu, Xianyi, & Zhou, Xian. (2013). Stochastic scheduling problems with general position-based learning effects and stochastic breakdowns. Journal of Scheduling, 16(3), 331-336.

Zhou, Yiyuan, & Zhang, Qiang. (2015). Multiple-Machine Scheduling with Learning Effects and Cooperative Games. Mathematical Problems in Engineering, 2015.