A Comprehensive Analysis on the Iterated Greedy Algorithm

Abstract

Generally, optimization is the achievement of the best result under certain constraints. Basically, the approaches developed for the solution of optimization problems are examined under two groups as exact solution methods and approximate solution methods. Exact solution methods guarantee the optimum, but they cannot produce solutions in an acceptable time for large-scale real-life problems of NP-Hard. Therefore, the researchers draw great attention to the meta-heuristic methods, which are one of the approximate solution methods, because they can provide quality solutions at an acceptable time. In this study, a detailed analysis of the iterative greedy algorithm, which is an easy-to-apply and effective meta-heuristic, was conducted. In the relevant meta-heuristic, each operator is discussed under subheadings. Iterative greedy algorithm approaches developed for various problems are presented to the reader with their advantages and disadvantages. In summary, in this study, it is aimed to contribute to the Turkish literature about the iterative greedy algorithm, which has many aspects in common with various meta-heuristics such as taboo, annealing simulation, and iterative local search.

Keywords

• Combinatorial optimization
• iterated greedy algorithm
• meta-heuristics

Tekrarlı Açgözlü Algoritma Üzerine Kapsamlı Bir Analiz

Abstract

Genel olarak optimizasyon, belirli kısıtlar altında en iyi sonucun elde edilmesi için yapılan çalışmaların bütünüdür. Temel olarak optimizasyon problemlerinin çözümü için geliştirilen yaklaşımlar kesin çözüm yöntemleri ve yaklaşık çözüm yöntemleri olmak üzere iki grup altında incelenir. Kesin çözüm yöntemleri optimumu garanti ederler ancak NP-Zor yapıdaki büyük boyutlu gerçek hayat problemleri için kabul edilebilir bir zamanda çözüm üretemezler. Bu yüzden araştırmacılar, kabul edilebilir zamanda, kaliteli çözümler verebilmeleri nedeni ile yaklaşık çözüm yöntemlerinden metasezgisel yöntemlere büyük ilgi göstermektedir. Bu çalışmada uygulaması kolay ve etkili bir metasezgisel olan tekrarlı açgözlü algoritmaya yönelik detaylı bir analiz çalışması yapılmıştır. İlgili metasezgisele ait her bir operatör alt başlıklar halinde ele alınmıştır. Çeşitli problemler için geliştirilen tekrarlı açgözlü algoritma yaklaşımları avantaj ve dezavantajlarıyla okuyucuya sunulmuştur. Özetle bu çalışmada tabu, tavlama benzetimi, tekrarlı yerel arama gibi çeşitli meta-sezgiseller ile ortak birçok yönü bulunan tekrarlı açgözlü algoritma hakkında Türkçe literatüre katkıda bulunmak amaçlanmıştır.

Keywords

• Kombinatoriyal en iyileme
• meta-sezgisel teknikler
• tekrarlı açgözlü algoritma

References

1. Al Aqel, G., Li, X., Gao, L., Gong, W., Wang, R., Ren, T., Wu, G. 2018. Using Iterated Greedy with a New Population Approach for the Flexible Jobshop Scheduling Problem. In 2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM) (pp. 1235-1239). IEEE.
2. Al Aqel, G., Li, X., Gao, L. 2019. A modified iterated greedy algorithm for flexible job shop scheduling problem. Chinese Journal of Mechanical Engineering, 32(1), 21.
3. Al-Behadili, M., Ouelhadj, D., Jones, D. 2020. Multi-objective biased randomised iterated greedy for robust permutation flow shop scheduling problem under disturbances. Journal of the Operational Research Society, 71(11), 1847-1859.
4. Bouamama, S., Blum, C., Boukerram, A. 2012. A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Applied Soft Computing, 12(6), 1632-1639.
5. Campbell HG, Dudek RA, Smith ML. Heuristic algorithm for N-job, Mmachine sequencing problem. Management Science Series B—Application 1970;16(10):B630–7.
6. Cesta, A., Oddi, A., Smith, S.F.: Iterative flattening: a scalable method for solving multi-capacity scheduling problems. In: Proceedings of the National Conference on Artificial Intelligence, pp. 742–747 (2000)
7. Ciavotta, M., G. Minella, and R. Ruiz. 2013. “Multi-objective Sequence Dependent Setup times Permutation Flowshop: A New Algorithm and a Comprehensive Study.” European Journal of Operational Research 227 (2): 301–313.
8. Choi, I. C., and O. Korkmaz. 1997. “Job Shop Scheduling with Separable Sequence-Dependent Setups.” Annals of Operations Research 70 (1): 155–170.

9. Deng G, Gu X. A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion.Computers and Operations Research 2012; 39(9): 2152–2160.
10. Deng, G., Su, Q., Zhang, Z., Liu, H., Zhang, S., Jiang, T. 2020. A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterion. Engineering Applications of Artificial Intelligence, 88, 103369.
11. Fanjul-Peyro, L., Ruiz, R. 2010. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 207(1), 55-69.
12. Fernandez-Viagas, V., Framinan, J. M. 2015. A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 53(4), 1111-1123.
13. Framinan, J. M., Leisten, R. 2008. Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm. International Journal of Production Research, 46(22), 6479-6498.
14. García-Martínez, C., Rodriguez, F. J., Lozano, M. 2014. Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem. European Journal of Operational Research, 232(3), 454-463.
15. Graham, R. L., Lawler, E. L., Lenstra, J. K., Kan, A. R. 1979. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics (Vol. 5, pp. 287-326). Elsevier.
16. Hartigan, J. A., Wong, M. A. 1979. A K -means clustering algorithm. Journal of the Royal Statistical Society, Series C: Applied Statistics, 28 (1), 100–108.
17. Hiley, A., Julstrom, B. 2006. The quadratic multiple knapsack problem and three heuristic approaches to it. In Proc. of the genetic and evolutionary computation conference (GECCO) (pp. 547–552).
18. Hoos, H.H., Stutzle, T.: Stochastic Local Search—Foundations and Applications. Morgan Kaufmann Publishers/Elsevier, San Francisco (2004).
19. Huerta-Muñoz, D. L., Ríos-Mercado, R. Z., Ruiz, R. 2017. An iterated greedy heuristic for a market segmentation problem with multiple attributes. European Journal of Operational Research, 261(1), 75-87.
20. Jacobs, L. W., Brusco, M. J., 1995. A local search heuristic for large set-covering problems. Naval Research Logistics Quarterly, 42(7), 1129–1140
21. Johnson SM. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1954;1(1):61–8.
22. Juan, A. A., Lourenc¸o, H. R., Mateo, M., Luo, R., Castella, Q., 2014. Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues. International Transactions in Operational Research, 21(1), 103–126. doi:10.1111/itor.12028
23. Kang, Q., He, H., Wei, J. 2013. An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems. Journal of parallel and distributed computing, 73(8), 1106-1115.
24. Karabulut, K. 2016. A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops. Computers & Industrial Engineering, 98, 300-307.
25. Kim, J. S., Park, J. H., Lee, D. H. 2017. Iterated greedy algorithms to minimize the total family flow time for job-shop scheduling with job families and sequence-dependent set-ups. Engineering Optimization, 49(10), 1719-1732.
26. Lee, C. H., 2018. A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness. International Journal of Production Research, 56(6), 2292-2308.
27. Li, X., Wang, Q., Wu, C. 2009. Efficient composite heuristics for total flowtime minimization in permutation flow shops. OMEGA, The International Journal of Management Science, 37, 155–164
28. Li, W., Li, J., Gao, K., Han, Y., Niu, B., Liu, Z., Sun, Q. 2019. Solving robotic distributed flowshop problem using an improved iterated greedy algorithm. International Journal of Advanced Robotic Systems, 16(5), 1729881419879819.
29. Lin, S. W., Lu, C. C., Ying, K. C. 2011. Minimization of total tardiness on unrelated parallel machines with sequence-and machine-dependent setup times under due date constraints. The International Journal of Advanced Manufacturing Technology, 53(1-4), 353-361.
30. Lin, G. 2013. An iterative greedy algorithm for hardware/software partitioning. In 2013 ninth international conference on natural computation (ICNC) (pp. 777-781). IEEE.
31. Lin, S. W., Ying, K. C., Huang, C. Y. 2013. Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm. International Journal of Production Research, 51(16), 5029-5038.
32. Lin, S. W., Ying, K. C., Wu, W. J., Chiang, Y. I. 2016. Multi-objective unrelated parallel machine scheduling: a Tabu-enhanced iterated Pareto greedy algorithm. International Journal of Production Research, 54(4), 1110-1121.
33. Mascis, A., Pacciarelli, D.: Job-shop scheduling with blocking and no-wait constraints. Eur. J. Oper. Res. 143(3), 498–517 (2002)
34. Minella, G., R. Ruiz, andM. Ciavotta, “Restarted Iterated Pareto Greedy algorithm for multi-objective flowshop scheduling problems,” Computers and Operations Research, vol. 38, no. 11, pp. 1521–1533, 2011
35. Naderi, B., Ruiz, R., 2010. The distributed permutation flowshop scheduling problem. Comput. Oper. Res. 37, 754–768. https://doi.org/10.1016/j.cor.2009.06.019
36. Naderi, B., Rahmani, S., Rahmani, S. 2014. A multiobjective iterated greedy algorithm for truck scheduling in cross-dock problems. Journal of Industrial Engineering, 2014.
37. Nawaz M, Enscore Jr. EE, Ham I. A heuristic algorithm for the m machine, n job flowshop sequencing problem. Omega-International Journal of Management Science 1983;11(1):91–5.
38. Nouri, N., Ladhari, T. 2016. An Efficient Iterated Greedy Algorithm for the Makespan Blocking Flow Shop Scheduling Problem. Polibits, (53), 91-95.
39. Nowicki, E., Smutnicki, C. 1996. A fast taboo search algorithm for the job shop problem. Management science, 42(6), 797-813.
40. Pacciarelli, D. (2002) Alternative graph formulation for solving complex factoryscheduling problems, International Journal of Production Research, 40:15, 3641-3653, DOI:10.1080/00207540210136478
41. Palmer, D.S., 1965. Sequencing jobs through a multi-stage process in the minimum total time: a quick method of obtaining a near optimum. Operational Research Quarterly, 16 (1), 101–107.
42. Pan, Q. K., Tasgetiren, M. F., Liang, Y. C. 2008. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering, 55(4), 795-816.
43. Pan, Q.K., R Ruiz. Local search methods for the flowshop scheduling problem with flowtime minimization. European Journal of Operational Research, 2012, 222: 31-43.
44. Pan, Q. K., Ruiz, R. 2014. An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega, 44, 41-50.
45. Pinheiro, J. C., & Arroyo, J. E. C. 2020. Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints. Annals of Mathematics and Artificial Intelligence, 88(1-3), 169-185.
46. Pranzo, M., Pacciarelli, D. 2016. An iterated greedy metaheuristic for the blocking job shop scheduling problem. Journal of Heuristics, 22(4), 587-611.
47. Rad SF, Ruiz R, Boroojerdian N. New high performing heuristics for minimizing makespan inpermutation flowshops. OMEGA, The International Journal of Management Science 2009; 37(2): 331–345.
48. Rajendran, C., Ziegler, H. 2004. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155(2), 426-438.
49. Ribas, I., Companys, R., Tort-Martorell, X. 2019. An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem. Expert Systems with Applications, 121, 347-361.
50. Riahi, V., Chiong, R., Zhang, Y. 2020. A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion. Computers & Operations Research, 117, 104839.
51. Rodriguez, F. J., Lozano, M., Blum, C., & GarcíA-MartíNez, C. (2013). An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & Operations Research, 40(7), 1829-1841.
52. Ruiz, R., and Stutzle, T. (2007), ‘A Simple and Effective Iterated Greedy Algorithm for the Permutation Flowshop Scheduling Problem’, European Journal of Operational Research, 177, 2033–2049.
53. Shaw, P.: A new local search algorithm providing high quality solutions to vehicle routing problems. Departement of Computer Sciences, University of Strathclyde, Glasgow, Scotland, Technical Report, APES group (1997).
54. Taillard E. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 1990; 47(1): 65–74.
55. Tasgetiren, M.F., Pan, Q.K., Liang, Y.C. 2009, ‘A Discrete Differential Evolution Algorithm for the Single Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times’, Computers & Operations Research, 36, 1900–1915.
56. Tasgetiren, M. F., Pan, Q. K., Suganthan, P. N., Buyukdagli, O., 2013. A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Computers & Operations Research, 40(7), 1729-1743.
57. Urlings, T., Ruiz, R., Stützle, T. 2010. Shifting representation search for hybrid flexible flowline problems. European Journal of Operational Research, 207(2), 1086-1095.
58. Yuan, Z., Fügenschuh, A., Homfeld, H., Balaprakash, P., Stützle, T., Schoch, M., 2008. Iterated greedy algorithms for a real-world cyclic train scheduling problem. In International Workshop on Hybrid Metaheuristics (pp. 102-116). Springer, Berlin, Heidelberg.
59. Ying, K. C., S. W. Lin, and S. Y. Wan., 2014. “Bi-objective Reentrant Hybrid Flowshop Scheduling: An Iterated Pareto Greedy Algorithm.” International Journal of Production Research 52 (19): 5735–5747.