Dergiler / El-Cezeri / 2024 / Cilt: 11 Sayı: 2

Iterated modified tabu search based equitable coloring for scheduling cricket world cup tournament

Praveena K(Dr. G. R. Damodaran College of Science)0000-0002-5527-7600
Dafik Dafik(University of Jember)0000-0003-0575-3039
Sayfa
131–141
Yayın Tarihi
2024-07-07
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

Both the results illustrate that the IMTS provided comparatively better solution with high quality and computational efficiency.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:In this article, an Iterated Modified Tabu Search (IMTS) approach is presented by improving certain aspects of general Tabu Search to enhance the approximation of the Equitable coloring problem (ECP) problem for a real-world problem of scheduling the ICC Cricket World Cup tournament.
📊
Temel Bulgular & Veri:The proposed IMTS introduces new point generation mechanisms and parameter updating rules to achieve this objective of tournament scheduling.
💡
Sonuç & Katkı:Both the results illustrate that the IMTS provided comparatively better solution with high quality and computational efficiency.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Equitable coloring problem · Iterated Modified Tabu Search · Scheduling Problem

Abstract

In this article, an Iterated Modified Tabu Search (IMTS) approach is presented by improving certain aspects of general Tabu Search to enhance the approximation of the Equitable coloring problem (ECP) problem for a real-world problem of scheduling the ICC Cricket World Cup tournament. The proposed IMTS introduces new point generation mechanisms and parameter updating rules to achieve this objective of tournament scheduling. The IMTS algorithm defines different k-ECP instances and utilizes the search process to determine the optimal solution for instance of k-ECP by estimating the minimum k-coloring value. An illustration of resolving the Cricket World Cup tournament scheduling problem using the proposed IMTS algorithm is provided. Also, an assessment of the IMTS is also performed on a commonly used benchmark instances. Both the results illustrate that the IMTS provided comparatively better solution with high quality and computational efficiency.

🔖

Bu Makaleye Atıf Yap

M, V., K, P., Dafik, D., Cangül, İ. N. (2024). Iterated modified tabu search based equitable coloring for scheduling cricket world cup tournament. El-Cezeri, Cilt: 11 Sayı: 2, 131–141. https://doi.org/10.31202/ecjse.1252238

📄 Tam Metin PDF Okuyucu

📄

PDF görüntüleyici hazırlanıyor...

Kaynakça (25)

  1. Jonathan L Gross and Jay Yellen. Graph theory and its applications. CRC Press, 2005.
  2. LR Foulds. Graph theory applications. Springer Science & Business Media, 2012.
  3. Narsingh Deo. Graph theory with applications to engineering and computer science. Courier Dover Publications, 2017.
  4. P. M. Pardalos, T. Mavridou, and J. Xue. The graph coloring problem: A bibliographic survey. In Handbook of combinatorial optimization, pages 1077–1141. Springer, 1998.
  5. T. Vredeveld and J. K. Lenstra. On local search for the generalized graph coloring problem. Operations Research Letters, 31(1):28–34, 2003.
  6. H. Furmanczyk and M. Kubale. Equitable coloring of graphs. Contemporary mathematics, 352:35–54, 2006.
  7. H. Furmańczyk. Equitable coloring of graph products. Opuscula Mathematica, 26(1):31–44, 2006.
  8. H. Furmańczyk and M. Kubale. Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling. Archives of Control Sciences, 25(1):109–116, 2015.
  9. A. Drexl and S. Knust. Sports league scheduling: graph-and resource-based models. Omega, 35(5):465–471, 2007.
  10. R. Lewis and J. Thompson. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research, 38(1):190–204, 2011.
  11. Z. Yan, W. Wang, and X. Zhang. Equitable colorings of cartesian products with balanced complete multipartite graphs. Discrete Applied Mathematics, 180:200–203, 2015.
  12. L. Bahiense, Y. Frota, T. F. Noronha, and C. C. Ribeiro. A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives. Discrete Applied Mathematics, 164:34–46, 2014.
  13. P. San Segundo. A new dsatur-based algorithm for exact vertex coloring. Computers & Operations Research, 39(7): 1724–1733, 2012.
  14. I. Mendez-Diaz, G. Nasini, and D. Severin. A polyhedral approach for the equitable coloring problem. Discrete Applied Mathematics, 164:413–426, 2014.
  15. I. Mendez-Diaz, G. Nasini, and D. Severin. An exact dsatur based algorithm for the equitable coloring problem. Electronic Notes in Discrete Mathematics, 44:281–286, 2013.
  16. I. Mendez-Diaz, G. Nasini, and D. Severin. A dsatur based algorithm for the equitable coloring problem. Computers & Operations Research, 57:41–50, 2015.
  17. I. Mendez-Diaz, G. Nasini, and D. Severin. A tabu search heuristic for the equitable coloring problem. In International Symposium on Combinatorial Optimization. Springer, 2014.
  18. W. Wang, J. K. Hao, and Q. Wu. Tabu search with feasible and infeasible searches for equitable coloring. Engineering Applications of Artificial Intelligence, 71:1–14, 2018.
  19. X. Lai, J. K. Hao, and F. Glover. Backtracking based iterated tabu search for equitable coloring. Engineering Applications of Artificial Intelligence, 46:269–278, 2015.
  20. W. Sun, J. K. Hao, W. Wang, and Q. Wu. Memetic search for the equitable coloring problem. Knowledge-Based Systems, page 105000, 2019.
  21. P. Galinier and A. Hertz. A survey of local search methods for graph coloring. Computers & Operations Research, 33(9): 2547–2562, 2006.
  22. P. Galinier, Z. Boujbel, and MC. Fernandes. An efficient memetic algorithm for the graph partitioning problem. Annals of Operations Research, 191(1):1–22, 2011.
  23. P. Galinier, J. P. Hamiez, J. K. Hao, and D. Porumbel. Recent advances in graph vertex coloring. In Handbook of optimization, pages 505–528. Springer, 2013.
  24. S. An, S. Yang, S. L. Ho, T. Li, and W. Fu. A modified tabu search method applied to inverse problems. A modified tabu search method applied to inverse problems, 47(5):1234–1237, 2010.
  25. R. Lewis and J. Thompson. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research, 38(1):190–204, 2011.