# American Institute of Mathematical Sciences

December  2017, 7(4): 465-480. doi: 10.3934/naco.2017029

## A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem

 1 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran 2 Department of Industrial and Systems Engineering, Isfahan University of Technology, 84156-83111, Isfahan, Iran

* Corresponding author

Received  December 2016 Revised  September 2017 Published  October 2017

Fund Project: The reviewing process of this paper was handled by Associate Editors A. (Nima) Mirzazadeh, Kharazmi University, Tehran, Iran, and Gerhard-Wilhelm Weber, Middle East Technical University, Ankara, Turkey, at the occasion of 12th International Conference on Industrial Engineering (ICIE 2016), which was held in Tehran, Iran during 25-26 January, 2016

In this paper, first, the problem of dynamic two-machine flow shop scheduling with the objective of minimizing the number of tardy jobs is investigated. Second, a hybrid algorithm based on genetic algorithm and parallel simulated annealing algorithm is presented. In order to solve large scale instances of the problem and to generate the initial population for the hybrid approach, a heuristic algorithm is also presented. To evaluate the efficiency of the proposed algorithms, they are compared with an optimal branch-and-bound algorithm which has been already developed in the literature. Computational experiments demonstrate that the proposed hybrid algorithm can solve the entire small-sized problems and more than 95% of medium-sized problems optimally.

Citation: Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029
##### References:

show all references

##### References:
The flowchart of the proposed hybrid meta-heuristic algorithm
An example for R-K method
Crossover operator
The differences between two groups of generated problems
 Influential Parameter High setting Low setting $r_j$ Jobs are available in a longer time interval after the beginning of scheduling Jobs are available in a short time interval which is closer to the close to the beginning of scheduling $D_j$ Tight due date intervals Loose due date intervals $D_j$ Different due dates Similar due dates Number of tardy jobs More tardy jobs Less tardy jobs
 Influential Parameter High setting Low setting $r_j$ Jobs are available in a longer time interval after the beginning of scheduling Jobs are available in a short time interval which is closer to the close to the beginning of scheduling $D_j$ Tight due date intervals Loose due date intervals $D_j$ Different due dates Similar due dates Number of tardy jobs More tardy jobs Less tardy jobs
Performance of PSA-GA and HEU1 algorithms in set High (compared with B & B)
 CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1 n min avg max OPT# OPT(%) avg max avg max 5 0.00 0.09 0.17 20 100% 1.00 1.00 1.06 1.50 6 0.05 0.16 0.28 20 100% 1.00 1.00 1.11 1.33 7 0.02 0.20 0.37 20 100% 1.00 1.00 1.09 1.40 8 0.02 0.18 0.37 20 100% 1.00 1.00 1.10 1.20 9 0.02 0.21 0.45 20 100% 1.00 1.00 1.06 1.17 10 0.08 0.16 0.41 20 100% 1.00 1.00 1.12 1.29 12 0.02 0.06 0.50 20 $100\%$ 1.00 1.00 1.01 1.10 14 0.23 0.41 0.86 20 $100\%$ 1.00 1.00 1.12 1.25 16 0.33 0.70 1.15 19 $95\%$ 1.00 1.07 1.11 1.25 18 0.62 1.34 2.11 19 $95\%$ 1.01 1.07 1.04 1.13 20 0.44 0.90 1.67 19 $95\%$ 1.01 1.08 1.05 1.12
 CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1 n min avg max OPT# OPT(%) avg max avg max 5 0.00 0.09 0.17 20 100% 1.00 1.00 1.06 1.50 6 0.05 0.16 0.28 20 100% 1.00 1.00 1.11 1.33 7 0.02 0.20 0.37 20 100% 1.00 1.00 1.09 1.40 8 0.02 0.18 0.37 20 100% 1.00 1.00 1.10 1.20 9 0.02 0.21 0.45 20 100% 1.00 1.00 1.06 1.17 10 0.08 0.16 0.41 20 100% 1.00 1.00 1.12 1.29 12 0.02 0.06 0.50 20 $100\%$ 1.00 1.00 1.01 1.10 14 0.23 0.41 0.86 20 $100\%$ 1.00 1.00 1.12 1.25 16 0.33 0.70 1.15 19 $95\%$ 1.00 1.07 1.11 1.25 18 0.62 1.34 2.11 19 $95\%$ 1.01 1.07 1.04 1.13 20 0.44 0.90 1.67 19 $95\%$ 1.01 1.08 1.05 1.12
Performance of PSA-GA and HEU1 algorithms in set Low (compared with B & B)
 CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1 n min avg max OPT# OPT(%) avg max avg max 5 0.02 0.09 0.16 20 100% 1.00 1.00 1.10 1.33 6 0.06 0.15 0.31 20 100% 1.00 1.00 1.10 1.25 7 0.14 0.27 0.38 20 100% 1.00 1.00 1.05 1.20 8 0.11 0.20 0.34 20 100% 1.00 1.00 1.07 1.40 9 0.23 0.41 0.55 20 100% 1.00 1.00 1.06 1.33 10 0.11 0.29 0.55 20 100% 1.00 1.00 1.09 1.60 12 0.22 0.33 0.61 20 $100\%$ 1.00 1.00 1.07 1.43 14 0.22 0.48 0.67 20 $100\%$ 1.00 1.00 1.08 1.20 16 0.37 0.70 1.08 20 $100\%$ 1.00 1.00 1.09 1.17 18 0.70 1.14 1.62 19 $95\%$ 1.01 1.03 1.06 1.15 20 0.78 1.12 2.29 19 $95\%$ 1.01 1.03 1.07 1.12
 CPU time (Sec.) for PSA-GA Number of problems optimally solved* $Z^{opt}/ Z^{heu}$ PSA-GA $Z^{opt}/ Z^{heu}$ HEU1 n min avg max OPT# OPT(%) avg max avg max 5 0.02 0.09 0.16 20 100% 1.00 1.00 1.10 1.33 6 0.06 0.15 0.31 20 100% 1.00 1.00 1.10 1.25 7 0.14 0.27 0.38 20 100% 1.00 1.00 1.05 1.20 8 0.11 0.20 0.34 20 100% 1.00 1.00 1.07 1.40 9 0.23 0.41 0.55 20 100% 1.00 1.00 1.06 1.33 10 0.11 0.29 0.55 20 100% 1.00 1.00 1.09 1.60 12 0.22 0.33 0.61 20 $100\%$ 1.00 1.00 1.07 1.43 14 0.22 0.48 0.67 20 $100\%$ 1.00 1.00 1.08 1.20 16 0.37 0.70 1.08 20 $100\%$ 1.00 1.00 1.09 1.17 18 0.70 1.14 1.62 19 $95\%$ 1.01 1.03 1.06 1.15 20 0.78 1.12 2.29 19 $95\%$ 1.01 1.03 1.07 1.12
Performance of algorithms HEU1 and PSA-GA in large problems; set High
 CPU time (Sec.) for PSA-GA CPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$ n min avg max min avg max avg max 30 1.06 2.16 3.45 0.00 0.00 0.01 1.16 1.26 40 1.44 2.01 2.87 0.01 0.01 0.01 1.13 1.31 50 2.79 4.90 6.72 0.01 0.02 0.03 1.11 1.20 60 5.01 7.96 11.06 0.00 0.01 0.04 1.11 1.21 70 6.44 10.63 14.45 0.01 0.02 0.04 1.11 1.25 80 11.29 18.65 26.46 0.03 0.04 0.06 1.08 1.22 90 10.42 23.23 36.60 0.02 0.04 0.07 1.07 1.14 100 13.29 19.39 24.73 0.03 0.05 0.09 1.06 1.10
 CPU time (Sec.) for PSA-GA CPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$ n min avg max min avg max avg max 30 1.06 2.16 3.45 0.00 0.00 0.01 1.16 1.26 40 1.44 2.01 2.87 0.01 0.01 0.01 1.13 1.31 50 2.79 4.90 6.72 0.01 0.02 0.03 1.11 1.20 60 5.01 7.96 11.06 0.00 0.01 0.04 1.11 1.21 70 6.44 10.63 14.45 0.01 0.02 0.04 1.11 1.25 80 11.29 18.65 26.46 0.03 0.04 0.06 1.08 1.22 90 10.42 23.23 36.60 0.02 0.04 0.07 1.07 1.14 100 13.29 19.39 24.73 0.03 0.05 0.09 1.06 1.10
Performance of algorithms HEU1 and PSA-GA in large problems; set Low
 CPU time (Sec.) for PSA-GA CPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$ n min avg max min avg max avg max 30 1.53 2.52 3.89 0.00 0.00 0.01 1.06 1.13 40 2.78 4.16 6.07 0.01 0.01 0.01 1.05 1.10 50 4.54 6.83 9.19 0.01 0.01 0.03 1.05 1.10 60 6.25 9.65 12.78 0.00 0.02 0.03 1.03 1.06 70 8.42 12.07 19.63 0.02 0.03 0.04 1.03 1.09 80 13.34 17.40 28.78 0.01 0.04 0.08 1.04 1.08 90 15.34 22.24 28.78 0.03 0.06 0.09 1.03 1.07 100 17.82 38.95 58.25 0.05 0.10 0.14 1.03 1.07
 CPU time (Sec.) for PSA-GA CPU times(Sec.) for HEU1 $Z^{PSA-GA}/ Z^{HEU1}$ n min avg max min avg max avg max 30 1.53 2.52 3.89 0.00 0.00 0.01 1.06 1.13 40 2.78 4.16 6.07 0.01 0.01 0.01 1.05 1.10 50 4.54 6.83 9.19 0.01 0.01 0.03 1.05 1.10 60 6.25 9.65 12.78 0.00 0.02 0.03 1.03 1.06 70 8.42 12.07 19.63 0.02 0.03 0.04 1.03 1.09 80 13.34 17.40 28.78 0.01 0.04 0.08 1.04 1.08 90 15.34 22.24 28.78 0.03 0.06 0.09 1.03 1.07 100 17.82 38.95 58.25 0.05 0.10 0.14 1.03 1.07
Results of the HEU1 algorithm; large-sized problem instances
 CPU time (Sec.) set High CPU times(Sec.) set Low n min avg max min avg max 200 0.08 0.13 0.17 0.22 0.25 0.30 400 0.70 1.05 1.33 1.64 1.85 2.06 600 2.31 3.03 3.64 5.60 6.13 6.55 60 6.25 9.65 12.78 0.00 0.02 0.03 800 5.53 7.10 8.64 12.97 14.46 19.42 1000 11.16 13.98 16.37 25.55 32.08 43.46
 CPU time (Sec.) set High CPU times(Sec.) set Low n min avg max min avg max 200 0.08 0.13 0.17 0.22 0.25 0.30 400 0.70 1.05 1.33 1.64 1.85 2.06 600 2.31 3.03 3.64 5.60 6.13 6.55 60 6.25 9.65 12.78 0.00 0.02 0.03 800 5.53 7.10 8.64 12.97 14.46 19.42 1000 11.16 13.98 16.37 25.55 32.08 43.46
 [1] T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53 [2] Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 [3] Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033 [4] Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019134 [5] Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219 [6] Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [7] Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391 [8] Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2019088 [9] Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017 [10] Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 [11] Muminu O. Adamu, Aderemi O. Adewumi. Minimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1465-1493. doi: 10.3934/jimo.2016.12.1465 [12] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019122 [13] Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041 [14] Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279 [15] Mao Chen, Xiangyang Tang, Zhizhong Zeng, Sanya Liu. An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle. Journal of Industrial & Management Optimization, 2020, 16 (1) : 495-510. doi: 10.3934/jimo.2018164 [16] Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial & Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457 [17] Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685 [18] Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1 [19] Yang Woo Shin, Dug Hee Moon. Throughput of flow lines with unreliable parallel-machine workstations and blocking. Journal of Industrial & Management Optimization, 2017, 13 (2) : 901-916. doi: 10.3934/jimo.2016052 [20] Muberra Allahverdi, Ali Allahverdi. Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019062

Impact Factor: