An effective hybrid ant lion algorithm to minimize mean tardiness on permutation flow shop scheduling problem

(1) * Dana Marsetiya Utama Mail (Departement of Industrial Engineering, University Of Muhammadiyah Malang (UMM), Indonesia)
(2) Dian Setiya Widodo Mail (University of 17 Agustus 1945 Surabaya, Indonesia)
(3) Muhammad Faisal Ibrahim Mail (Universitas Internasional Semen Indonesia, Indonesia)
(4) Shanty Kusuma Dewi Mail (Departement of Industrial Engineering, University Of Muhammadiyah Malang (UMM), Indonesia)
*corresponding author


This article aimed to develop an improved Ant Lion algorithm. The objective function was to minimize the mean tardiness on the flow shop scheduling problem with a focus on the permutation flow shop problem (PFSP). The Hybrid Ant Lion Optimization Algorithm (HALO) with local strategy was proposed, and from the total search of the agent, the NEH-EDD algorithm was applied. Moreover, the diversity of the nominee schedule was improved through the use of swap mutation, flip, and slide to determine the best solution in each iteration. Finally, the HALO was compared with some algorithms, while some numerical experiments were used to show the performances of the proposed algorithms. It is important to note that comparative analysis has been previously conducted using the nine variations of the PFSSP problem, and the HALO obtained was compared to other algorithms based on numerical experiments.


Optimization; Mean tardiness; Hybrid ant lion; Flow shop; Scheduling



Article metrics

Abstract views : 25884 | PDF views : 234




Full Text



[1] D. M. Utama, T. Baroto, D. Maharani, F. R. Jannah, and R. A. Octaria, "Algoritma Ant-Lion optimizer untuk meminimasi emisi karbon pada penjadwalan flow shop dependent sequence set-up," 2019, vol. 9, pp. 69-78, 2019-06-28 2019, doi: 10.24960/jli.v9i1.4775.69-78.

[2] M. S. Nagano, R. Ruiz, and L. A. N. Lorena, "A Constructive Genetic Algorithm for permutation flowshop scheduling," Computers & Industrial Engineering, vol. 55, pp. 195-207, 2008, doi: 10.1016/j.cie.2007.11.018.

[3] H. F. Rahman, R. Sarker, and D. Essam, "A genetic algorithm for permutation flow shop scheduling under make to stock production system," Computers & Industrial Engineering, vol. 90, pp. 12-24, 2015, doi: 10.1016/j.cie.2015.08.006.

[4] Q. C. Ta, J.-C. Billaut, and J.-L. Bouquard, "Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem," Journal of Intelligent Manufacturing, vol. 29, pp. 617-628, 2018, doi: 10.1007/s10845-015-1046-4.

[5] D. M. Utama, L. R. Ardiansyah, and A. K. Garside, "Penjadwalan Flow Shop untuk Meminimasi Total Tardiness Menggunakan Algoritma Cross Entropy–Algoritma Genetika," Jurnal Optimasi Sistem Industri, vol. 18, pp. 133-141, 2019, doi: 10.25077/josi.v18.n2.p133-141.2019.

[6] K. Karabulut, "A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops," Computers & Industrial Engineering, vol. 98, pp. 300-307, 2016, doi: 10.1016/j.cie.2016.06.012.

[7] D. M. Utama, D. S. Widodo, W. Wicaksono, and L. R. Ardiansyah, "A New Hybrid Metaheuristics Algorithm for Minimizing Energy Consumption in the Flow Shop Scheduling Problem," International Journal of Technology, vol. 10, pp. 320-331, 2019, doi: 10.14716/ijtech.v10i2.2194.

[8] Y.-D. Kim, "Heuristics for flowshop scheduling problems minimizing mean tardiness," Journal of the Operational Research Society, vol. 44, pp. 19-28, 1993, doi: 10.1057/jors.1993.3.

[9] V. Fernandez-Viagas and J. M. Framinan, "NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness," Computers & Operations Research, vol. 60, pp. 27-36, 2015, doi: 10.1016/j.cor.2015.02.002.

[10] M. Nawaz, E. E. Enscore, and I. Ham, "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, vol. 11, pp. 91-95, 1983, doi: 10.1016/0305-0483(83)90088-9.

[11] M. S. Nagano, F. L. Rossi, and C. P. Tomazella, "A new efficient heuristic method for minimizing the total tardiness in a no-idle permutation flow shop," Production Engineering, vol. 11, pp. 523-529, 2017, doi: 10.1007/s11740-017-0747-2.

[12] V. Fernandez-Viagas and J. M. Framinan, "Efficient non-population-based algorithms for the permutation flowshop scheduling problem with makespan minimisation subject to a maximum tardiness," Computers & Operations Research, vol. 64, pp. 86-96, 2015, doi: 10.1016/j.cor.2015.05.006.

[13] R. M’Hallah, "An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop," International Journal of Production Research, vol. 52, pp. 3802-3819, 2014/07/03 2014, doi: 10.1080/00207543.2014.899719.

[14] J.-M. Kim, Y.-D. Zhou, and D.-H. Lee, "Priority scheduling to minimize the total tardiness for remanufacturing systems with flow-shop-type reprocessing lines," The International Journal of Advanced Manufacturing Technology, vol. 91, pp. 3697-3708, 2017, doi: 10.1007/s00170-017-0057-z.

[15] M. Abdel-Basset, G. Manogaran, D. El-Shahat, and S. Mirjalili, "A hybrid whale optimization algorithm based on local search strategy for the permutation flow shop scheduling problem," Future Generation Computer Systems, vol. 85, pp. 129-145, 2018, doi: 10.1016/j.future.2018.03.020.

[16] E. Vallada and R. Ruiz, "Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem," Omega, vol. 38, pp. 57-67, 2010, doi: 10.1016/

[17] V. c. A. Armentano and D. P. Ronconi, "Tabu search for total tardiness minimization in flowshop scheduling problems," Computers & Operations Research, vol. 26, pp. 219-235, 1999, doi: 10.1016/S0305-0548(98)00060-4.

[18] H. Mokhtari and A. Noroozi, "An efficient chaotic based PSO for earliness/tardiness optimization in a batch processing flow shop scheduling problem," Journal of Intelligent Manufacturing, vol. 29, pp. 1063-1081, 2018, doi: 10.1007/s10845-015-1158-x.

[19] S. Hasija and C. Rajendran, "Scheduling in flowshops to minimize total tardiness of jobs," International Journal of Production Research, vol. 42, pp. 2289-2301, 2004, doi: 10.1080/00207540310001657595.

[20] W. Shao, D. Pi, and Z. Shao, "A hybrid discrete teaching-learning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion," Computers & Operations Research, vol. 94, pp. 89-105, 2018, doi: 10.1016/j.cor.2018.02.003.

[21] W. Liao and Y. Fu, "A New Robust Scheduling Model for Permutation Flow Shop Problem," Recent Advances in Intelligent Manufacturing, pp. 308-317, 2018, doi: 10.1007/978-981-13-2396-6_29.

[22] R. Nasution, A. K. Garside, and D. M. Utama, "Penjadwalan Job Shop Dengan Pendekatan Algoritma Artificial Immune System," 2017, vol. 18, p. 14, 2017, doi: 10.22219/JTIUMM.Vol18.No1.29-42.

[23] J.-n. Shen, L. Wang, and S.-y. Wang, "A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion," Knowledge-Based Systems, vol. 74, pp. 167-175, 2015, doi: 10.1016/j.knosys.2014.11.016.

[24] J. Haddock and J. Mittenthal, "Simulation Optimization Using Simulated Annealing," Computers & Industrial Engineering, vol. 22, pp. 387-395, 1992, doi: 10.1016/0360-8352(92)90014-B.

[25] D. M. Utama, "An Effective Hybrid Sine Cosine Algorithm to Minimize Carbon Emission on Flow-shop Scheduling Sequence Dependent Setup," 2019, vol. 20, pp. 62-72, 2019, doi: 10.22219/JTIUMM.Vol20.No1.62-72.

[26] S. Mirjalili, "The Ant Lion Optimizer," Advances in Engineering Software, vol. 83, pp. 80-98, 2015, doi: 10.1016/j.advengsoft.2015.01.010.

[27] N. Chopra and S. Mehta, "Multi-objective optimum generation scheduling using Ant Lion Optimization," in 2015 Annual IEEE India Conference (INDICON), 2015, pp. 1-6, doi: 10.1109/INDICON.2015.7443839.

[28] H. M. Dubey, M. Pandit, and B. K. Panigrahi, "Hydro-thermal-wind scheduling employing novel Ant Lion optimization technique with composite ranking index," Renewable Energy, vol. 99, pp. 18-34, 2016, doi: 10.1016/j.renene.2016.06.039.

[29] E. Umamaheswari, S. Ganesan, M. Abirami, and S. Subramanian, "Deterministic reliability model based preventive generator maintenance scheduling using Ant Lion Optimizer," in 2016 International Conference on Circuit, Power and Computing Technologies (ICCPCT), 2016, pp. 1-8, doi: 10.1109/ICCPCT.2016.7530272.

[30] M. Petrović, J. Petronijević, M. Mitić, N. Vuković, Z. Miljković, and B. Babić, "The Ant Lion optimization algorithm for integrated process planning and scheduling," in Applied Mechanics and Materials, 2016, pp. 187-192, doi: 10.4028/

[31] X. Li and M. Yin, "An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure," Advances in Engineering Software, vol. 55, pp. 10-31, 2013, doi: 10.1016/j.advengsoft.2012.09.003.

[32] P. Hansen and N. Mladenović, "Variable neighborhood search: Principles and applications," European Journal of Operational Research, vol. 130, pp. 449-467, 2001, doi: 10.1016/S0377-2217(00)00100-4.

[33] G. Laporte, M. Gendreau, J. Y. Potvin, and F. Semet, "Classical and modern heuristics for the vehicle routing problem," International transactions in operational research, vol. 7, pp. 285-300, 2000, doi: 10.1111/j.1475-3995.2000.tb00200.x.

[34] S. Parthasarathy and C. Rajendran, "A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs-a case study," Production Planning & Control, vol. 8, pp. 475-483, 1997, doi: 10.1080/095372897235055.

[35] M. R. Garey, D. S. Johnson, and R. Sethi, "The complexity of flowshop and jobshop scheduling," Mathematics of operations research, vol. 1, pp. 117-129, 1976, doi: 10.1287/moor.1.2.117.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

International Journal of Advances in Intelligent Informatics
ISSN 2442-6571  (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
E: (paper handling issues) (publication issues)

View IJAIN Stats

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0