# 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] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [2] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [3] Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107 [4] Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018 [5] Yolanda Guerrero–Sánchez, Muhammad Umar, Zulqurnain Sabir, Juan L. G. Guirao, Muhammad Asif Zahoor Raja. Solving a class of biological HIV infection model of latently infected cells using heuristic approach. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020431 [6] Hui Lv, Xing'an Wang. Dissipative control for uncertain singular markovian jump systems via hybrid impulsive control. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 127-142. doi: 10.3934/naco.2020020 [7] Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443 [8] Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276 [9] Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304 [10] Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020049 [11] Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166 [12] Chao Xing, Jiaojiao Pan, Hong Luo. Stability and dynamic transition of a toxin-producing phytoplankton-zooplankton model with additional food. Communications on Pure & Applied Analysis, 2021, 20 (1) : 427-448. doi: 10.3934/cpaa.2020275 [13] Hua Qiu, Zheng-An Yao. The regularized Boussinesq equations with partial dissipations in dimension two. Electronic Research Archive, 2020, 28 (4) : 1375-1393. doi: 10.3934/era.2020073 [14] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [15] Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081 [16] Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045 [17] João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138 [18] Zhouchao Wei, Wei Zhang, Irene Moroz, Nikolay V. Kuznetsov. Codimension one and two bifurcations in Cattaneo-Christov heat flux model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020344 [19] Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467 [20] Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243

Impact Factor: