Flow Shop Scheduling Using a Combination of Ant Colony Optimization Algorithm and Tabu Search Algorithm to Minimize Total Tardiness

Hana Merlina Hesti Bestari; Pratya Poeri Suryadhini; Nopendri Nopendri

doi:10.24014/jti.v10i2.32320

Flow Shop Scheduling Using a Combination of Ant Colony Optimization Algorithm and Tabu Search Algorithm to Minimize Total Tardiness

Hana Merlina Hesti Bestari, Pratya Poeri Suryadhini, Nopendri Nopendri

Abstract

This paper addresses the problem of production tardiness on five parallel production floors at PT Garmen X, each with an identical machine arrangement. The proposed method combines Ant Colony Optimization (ACO) and Tabu Search (TS) algorithms for flow shop scheduling problems. ACO acts as the primary method for finding the optimal solution. At the same time, the Tabu Search algorithm is applied as a local search to improve the quality of the solution found by ACO. The results show significant performance improvement, with a decrease in total tardiness by 88.09% and a reduction in total makespan by 5.08% compared to the existing method.

Keywords: Garment, Flow shop, Ant Colony Optimization, Tabu Search, Total Tardiness

Full Text:

PDF

References

S. N. Chapman, The fundamentals of production planning and control. Pearson/Prentice Hall, 2006.

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, no. 2, pp. 133–141, Oct. 2019, doi: 10.25077/josi.v18.n2.p133-141.2019.

J. N. D. Gupta and E. F. Stafford, “Flowshop scheduling research after five decades,” Eur J Oper Res, vol. 169, no. 3, pp. 699–711, Mar. 2006, doi: 10.1016/j.ejor.2005.02.001.

B. Yagmahan and M. M. Yenisey, “A multi-objective ant colony system algorithm for flow shop scheduling problem,” Expert Syst Appl, vol. 37, no. 2, pp. 1361–1368, Mar. 2010, doi: 10.1016/j.eswa.2009.06.105.

J. Schaller and J. Valente, “Branch-and-bound algorithms for minimizing total earliness and tardiness in a two-machine permutation flow shop with unforced idle allowed,” Comput Oper Res, vol. 109, pp. 1–11, Sep. 2019, doi: 10.1016/j.cor.2019.04.017.

J. Bautista-Valhondo and R. Alfaro-Pozo, “Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types,” Cent Eur J Oper Res, vol. 28, no. 1, pp. 5–23, Mar. 2020, doi: 10.1007/s10100-018-0553-8.

H. Allaoui and A. H. Artiba, “Johnson’s algorithm: A key to solve optimally or approximately flow shop scheduling problems with unavailability periods,” Int J Prod Econ, vol. 121, no. 1, pp. 81–87, Sep. 2009, doi: 10.1016/j.ijpe.2008.09.018.

M. K. Hajji, O. Hamlaoui, and H. Hadda, “A simulated annealing metaheuristic approach to hybrid flow shop scheduling problem,” Advances in Industrial and Manufacturing Engineering, vol. 9, Nov. 2024, doi: 10.1016/j.aime.2024.100144.

I. H. Kuo et al., “An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model,” Expert Syst Appl, vol. 36, no. 3 PART 2, pp. 7027–7032, 2009, doi: 10.1016/j.eswa.2008.08.054.

L. Wang, L. Zhang, and D. Z. Zheng, “An effective hybrid genetic algorithm for flow shop scheduling with limited buffers,” Comput Oper Res, vol. 33, no. 10, pp. 2960–2971, Oct. 2006, doi: 10.1016/j.cor.2005.02.028.

M. K. Marichelvam, T. Prabaharan, and M. Geetha, “Firefly algorithm for flow shop optimization,” Studies in Computational Intelligence, vol. 585, pp. 225–243, 2015, doi: 10.1007/978-3-319-13826-8_12.

P. N. Nhu and T. N. N. Thi, “Application of tabu search, TS, to solve a flow shop scheduling problem with changeover times in operations: A case study,” BOHR International Journal of Operations Management Research and Practices, vol. 3, no. 1, pp. 1–7, 2022, doi: 10.54646/bijomrp.2024.22.

T. Stützle, “An Ant Approach to the Flow Shop Problem,” Fifth European Congress on Intelligent Techniques & Soft Computing (EUFIT’98), vol. 3, pp. 1560–1564, 1998, [Online]. Available: http://iridia.ulb.ac.be/dorigo/ACO/ACO.html.

Karjono, Moedhiono, and D. Kurniawan, “Ant Colony Optimization,” Jurnal TICOM, vol. 4, no. 3, 2016.

A. Bauer, R. F. Hartl, C. Strauss, and B. Bullnheimer, “Minimizing Total Tardiness on a Single Machine Using Ant Colony Optimization,” 2014. [Online]. Available: https://www.researchgate.net/publication/260423657

M. den Besten, T. Stützle, and M. Dorigo, “Ant Colony Optimization for the Total Weighted Tardiness Problem.,” 2000, [Online]. Available: https://www.researchgate.net/publication/220702108

O. I. R. Farisi, B. Setiyono, and R. I. Danandjojo, “A Hybrid Firefly Algorithm-Ant Colony Optimization for Traveling Salesman Problem,” Jurnal Buana Informatika, vol. 7, no. 1, pp. 55–64, 2015.

K. L. Huang and C. J. Liao, “Ant colony optimization combined with taboo search for the job shop scheduling problem,” Comput Oper Res, vol. 35, no. 4, pp. 1030–1046, Apr. 2008, doi: 10.1016/j.cor.2006.07.003.

K. R. Baker and D. Trietsch, Principles of Sequencing and Scheduling, Second Edition. John Wiley & Sons, Inc., 2019.

M. Dorigo, V. Maniezzo, and A. Colorni, “Ant System: An Autocatalytic Optimizing Process,” 1991.

M. D. Toksari, “A hybrid algorithm of Ant Colony Optimization (ACO) and Iterated Local Search (ILS) for estimating electricity domestic consumption: Case of Turkey,” International Journal of Electrical Power and Energy Systems, vol. 78, pp. 776–782, Jun. 2016, doi: 10.1016/j.ijepes.2015.12.032.

Liliani and A. Alfian, “Usulan Penjadwalan Produksi Dengan Algoritma Ant Colony (Studi Kasus PT Shima Prima Utama Palembang),” Simposium Nasional RAPI XIII, 2014.

J. C. Nyirenda, “Relationship Between The Modified Due Date Rule and The Heuristic of Wilkerson and Irwin,” Journal of Computer Science and Engineering, vol. 17, no. 1, pp. 101–111, 2014, Accessed: Jul. 13, 2024. [Online]. Available: https://doi.org/10.5784/17-0-192

C. Venkateswarlu, “A Metaheuristic Tabu Search Optimization Algorithm: Applications to Chemical and Environmental Processes,” IntechOpen, 2022, Accessed: Mar. 22, 2024. [Online]. Available: http://dx.doi.org/10.5772/intechopen.98240

Z. Zhao, X. Chen, Y. An, Y. Li, and K. Gao, “A property-based hybrid genetic algorithm and tabu search for solving order acceptance and scheduling problem with trapezoidal penalty membership function,” Expert Syst Appl, vol. 218, May 2023, doi: 10.1016/j.eswa.2023.119598.

H. Pirim, B. Eksioglu, and E. Bayraktar, “Tabu Search: A Comparative Study,” 2008.

I. H. Sahputra, T. Octavia, and A. S. Chandra, “Tabu Search Sebagai Local Search pada Algoritma Ant Colony untuk Penjadwalan Flow Shop,” Jurnal Teknik Industri, vol. 11, no. 2, pp. 188–194, 2009.

S. Mardiani, “Penjadwalan Produksi Dengan Metode Tabu Search Menggunakan Software VBA Macro Excel di PT Citra Abadi Sejati,” Scientifict Journal of Industrial Engineering, vol. 2, no. 2, 2021, Accessed: Aug. 05, 2024. [Online]. Available: https://doi.org/10.30998/.v2i2.4179

DOI: http://dx.doi.org/10.24014/jti.v10i2.32320