Jurnal Teknik Informatika dan Sistem Informasi ISSN  2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E- ISSN  2503-2933 547

## Optimasi Penjadwalan Olahraga ITC 2021 Menggunakan Swap
Alda Muhammad Sulaiman* 1 , Ahmad Muklason 2
1,2 Departemen Sistem Informasi Institut Teknologi Sepuluh Nopember e-mail: * 1 aldamuhammadsulaiman@gmail.com

## Abstrak
Riset operasi memiliki salah satu bidang yakni penjadwalan olahraga. Topik ini menjadwalkan  sebuah  pertandingan  olahraga  dengan  tidak  melanggar  batasan  yang ada.  Permasalahan  penjadwalan  olahraga  saat  ini  menjadi  semakin  kompleks  dengan banyaknya  batasan  yang  ada.  Kompetisi  International  Timetabling  Competition  on Sports Timetabling 2021 (ITC 2021) merupakan salah satu yang mengeluarkan dataset realworld  terbaru.Optimasi  kualitas  penjadwalan  olahraga  untuk  menurunkan  nilai penalty  pada  solusi  akhir  dari  penjadwalan  merupakan  focus  dari  penelitian  ini. Penerapan  algoritma  ini  mampu  menghasilkan  optimasi  dengan  rata-rata  10  dari solusi awal. Algoritma ini juga menghasilkan solusi yang konsistern selama 10.000.000 kali percobaan setiap dataset.
Kata kunci —Penjadwalan Olahraga, Algoritma Tabu Search, Hiper Heuristik

## Abstract
Operations  research  has  one  area,  namely  sports  scheduling.  This  topic  is scheduling a sporting event without violating any existing restrictions. The problem of sports  scheduling  today  is  becoming  increasingly  complex  with  the  many  limitations that exist. The International Timetabling Competition on Sports Timetabling 2021 (ITC 2021) is one of those that releases the latest realworld dataset.Optimizing the quality of sports  scheduling  to  reduce  the  penalty  value  in  the  final  solution  of  scheduling  is  the focus of this research.The application of this algorithm is able to produce optimization with  an  average  of  10  from  the  initial  solution.  This  algorithm  also  produces  a consistent solution during 10.000.000 trials for each dataset.
Keywords — Sports Scheduling, Taboo Search Algorithm, Hyper Heuristics

## 1. PENDAHULUAN
ermasalan  penjadawalan  olahraga  adalah  permasalahan  kombinatorial  optimasi yang  terdiri  dari  membuat  jadwal  yang  menentukan  tim  siapa,  dimana,  dan  kapan diadakan  pertandingan  [1].  Format  data  yang  tidak  seragam  menyulitkan  untuk mendapatkan data perbandingan.
Dataset  terbaru,  ITC  2021,  memiliki  tingkat  kompleksitas  yang  sangat  tinggi. Dataset  ini  terdiri  dari  8  dataset.    Secara  garis  besar  dataset  ini  memiliki  5  batasan. P
548 Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E-ISSN 2503-2933
Tujuan  utama  dari  kompetisi  ini  adalah  menjadwalkan  tim  ke  dalam  jadwal pertandingan  yang  tersedia  tanpa  melanggar hard  constraint yang  ada.  Kualitas  dari solusi yang dihasilkan ditentukan oleh nilai penalty. Solusi yang paling baik merupakan solusi dengan penalti paling kecil. [2].
Pembuatan  jadwal  untuk  kompetisi  olahraga  telah  menjadi  topik  riset  sejak 1970.  Sejak  itu,  jurnal  akademik  tentang  penjadwalan  olahraga  meningkat  drastis. Penelitian  sebelumnya  membuktikan  bahwa  masalah relaxed dapat  diatasi  dengan algoritma local  search dimana  pendekatan mathematical  programming atau constraint programming cocok  untuk  masalah constrained [3]. Late  Acceptance  Hill-Climbing (LAHC) merupakan metodologi pencarian  yang  baru dan sangat sederhana. Algoritma ini  berdasar  algoritma local  search ,  dimana  menerima non-improving moves dimana nilai fungsi tujuan lebih baik daripada suatu angka pada iterasi sebelumnya. Angka ini berperan  sebagai  parameter  masukan  dimana  menentukan  jumlah  waktu  pemrosesan dari prosedur pencarian [4].
Keberhasilan  tabu  search  menjadi  terkenal  karena  menghasilkan  solusi  yang cukup baik pada masalah kombinatorial besar. Tabu Search adalah local search berbasis metode  optimasi.  Pencarian  bergerak  dari  satu  solusi  ke  solusi  lain,  memilih  elemen yang  terbaik  namun  tidak forbidden di neighborhood .  Metode  ini  menghindari  solusi dengan  beberapa  atribut  dengan  tujuan  menghindari  berputar  dan  mengarahkan pencarian  ke  arah  daerah  yang  belum  dieksplor  [5]. Simulated  annealing adalah metaheuristik local  search yang  dipelajari  dengan  baik  yang  digunakan  untuk menyelesaikan permasalahan optimasi yang bersifat diskrit, lebih rendah, dan kontinyu. Fitur utama dari simulated annealing adalah menyediakan mekanisme untuk keluar dari local  optima dengan  membolehkan  pergerakan hill-climbing (seperti  pergerakan  yang lebih buruk pada fungsi tujuan) dengan harapan untuk menemukan global optimum [6]. Terdapat beberapa jenis LLH yang akan digunakan, yaitu Team Swap , Home Swap dan Round  Swap [7].    Dalam  penjadwalan round-robin ,  setiap  tim  bermain  melawan  tim lain  pada  jumlah  yang  tetap  [8].  Liga  olahraga  profesional  adalah  aktivitas  ekonomi yang  cukup  penting  di  dunia.  Tim  dan  liga  tidak  ingin  rugi  karena  penjadwalan  yang buruk. Penjadwalan permainan cukup sulit untuk dilakukan [9].
Heuristik,  metaheuristik,  dan  hiper  heuristik  merupakan  beberapa  jenis  metode dalam  pengembangan  algoritma  dengan  pendekatan  heuristik.  Metode  heuristik  sering menghasilkan  hasil  yang  buruk  pada  beberapa  kasus  namun  mudah  untuk  digunakan. Metode metaheuristik tidak dapat digunakan pada dunia komersial dan industri karena metode ini membutuhkan biaya yang mahal dan susah untuk diterapkan walapun dapat menghasilkan solusi yang sangat baik. Sedangkan metode hiper heuristik lebih mampu menghasilkan solusi yang baik, cukup mudah, dan terjangkau [10]
Menurut  peneltian-penelitan  di  atas,    belum  ada  penelitian  metode  yang ditawarkan  pada  paper    ini.  Dataset  yang  digunakan  sangat  baru,  yakni  tahun  2021. Untuk  metode swapHome,  swapTeam, dan swapRound sudah  dilakukan,  namun  untuk studi kasus yang berbeda dengan penelitian ini.
Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E- ISSN 2503-2933 549

## 2. METODE PENELITIAN
Penelitian ini memiliki tahapan yakni praproses, desain algoritma, implementasi, dan analisis hasil.

## 2.1   Pra Proses Data
Pada  dataset  ITC  2021,  selama  terdapat  beberapa  kandidat  jadwal  yang  pasti akan  melanggar hard  constraint yang  ada,  maka  kandidat  tersebut  tidak  mugkin digunakan selama penjadwalan.

## 2. 1.1 Dataset
Dataset yang digunakan terbatas pada Test1-Test8 dari keseluruhan dataset ITC 2021. Detail jumlah tim dan slot setiap dataset dapat dilihat pada Tabel 2.1.
Tabel 1. Dataset Test Nama Dataset Tim Slot Test Instance 1 6 10 Test Instance 2 6 10 Test Instance 3 6 10 Test Instance 4 6 10 Test Instance 5 16 30 Test Instance 6 18 34 Test Instance 7 20 38 Test Instance 8 20 38

## 2. 2   Desain Algoritma
Desain algoritma terdiri atas 2 bagian,  yakni solusi dan melakukan swap untuk meminimalisir penalti hard constraint.
2. 2.1Rumus Matematika Capacity Constraint Capacity  constraint mengharuskan  sebuah  tim  bertanding  pada  mode home atau away dan mengatur jumlah permainan yang dimainkan oleh sebuah atau sekumpulan tim CA1 Setiap  tim  di  grup  tim T bermain  setidaknya k menit  dan  paling  banyak k max {pertandingan  kandang,  pertandingan  tandang,  pertandingan}  di  grup  waktu S . Setiap tim di T memicu deviasi  yang sama dengan jumlah pertandingan kandang di S kurang dari k min atau lebih dari k max .
(1)
550 Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E-ISSN 2503-2933

## CA2
Setiap  tim  di  grup  tim T 1 bermain  setidaknya k menit  dan  paling  banyak k max { home games , away games , games } melawan { teams , each team } di grup tim T 2 di grup waktu S .
(2)
CA3 Setiap  tim  di  grup  tim T 1 bermain  setidaknya k menit  dan  paling  banyak k max { home games, away games, games } melawan tim di grup tim T 2 di setiap urutan k { time slots, games }.  Setiap  tim  di T 1 memicu  penyimpangan  yang  sama  dengan  jumlah  jumlah pertandingan kandang melawan tim di T 2 kurang dari k menit atau lebih dari k max untuk setiap urutan k slot waktu
(3)
CA4 Tim  di  grup  tim T 1 bermain  setidaknya k menit  dan  paling  banyak k max { home games, away games, games } melawan tim di grup tim T 2 di { time group, each time slot of time group } S . Pemutusan ambiguitas dengan CA2: | T 1 | > 1. Grup waktu S memicu penyimpangan yang sama dengan jumlah pertandingan dengan tim tuan rumah di T 1 dan tim di T 2 kurang dari k min atau lebih dari k max .
(4)

## Game Constraint
Batasan permainan memaksakan atau melarang penugasan tertentu dari permainan ke slot waktu
GA1 Setidaknya k min dan paling banyak k max game dari G = { (i 1 , j 1 ) , (i 2 , j 2 ), . . . } berlangsung  dalam  kelompok  waktu S .  Grup  waktu S memicu  deviasi  yang  sama dengan jumlah game di G kurang dari k min atau lebih dari k max
(5)
Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E- ISSN 2503-2933 551

## Break Constraint
Batasan istirahat mengatur frekuensi dan waktu istirahat dalam suatu kompetisi. Sebuah tim memiliki istirahat kandang (tandang) ketika memainkan dua pertandingan kandang (tandang) berturut-turut, tidak peduli berapa banyak bye yang dimiliki tim ini di antara dua pertandingan
BR1 Setiap tim di grup tim T memiliki {tepat, tidak lebih dari} k { home break, away break, break }  di  grup  waktu S .  Setiap  tim  di T memicu  deviasi  yang  sama  dengan  selisih jumlah home break di S dan k .
(6)
BR2 Jumlah seluruh { home break, away break, break } tim di grup tim T adalah {tepatnya, tidak lebih dari} k di grup waktu S .
(7)
Fairness And Attractiveness Constraints Kendala berikut meningkatkan keadilan atau daya tarik kompetisi .

## FA2
Setiap  pasangan  tim  dalam  grup  tim T memiliki  selisih  {permainan  kandang, pertandingan  tandang,  pertandingan}  yang  dimainkan  tidak  lebih  besar  dari k setelah setiap  slot  waktu  di S .  Setiap  pasangan  tim  di T memicu  penyimpangan  yang  sama dengan  perbedaan  terbesar  dalam  pertandingan  kandang  yang  dimainkan  lebih  dari k selama semua slot waktu di S
(8)

## 2. 3   Implementasi Algoritma
Program  Intellij  dengan  bahasa  pemrograman Java diimplementasikan  pada bagian  ini.  Dataset  tersebut  diimplementasikan  dengan  cara  menjalankan  datasetnya dengan jumlah iterasi 10.000.000.
552 Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E-ISSN 2503-2933

## 2. 4   Analisis Hasil
Dari  hasil  eksekusi  tahap  sebelumnya,  dengan  membandingkan  nilai  penalti hard  constraint solusi sebelum dan sesudah optimasi, diperoleh hasil analisis optimasi yang berhasil..

## 3. HASIL DAN PEMBAHASAN
Metode swap dijalankan  untuk  mendapatkan hard  constraint terkecil.  Hasil menjankan metode swap dapat dilihat pada tabel 2.
Tabel 2. Hasil Penurunan Penalty
Gambar 1. Bagan Penurunan Penalty Test1-Test4
asli swap home swap round swap team ITC2021_Test1 42 5 2 1 ITC2021_Test2 7 1 0 0 ITC2021_Test3 51 20 10 9 ITC2021_Test4 61 24 16 16 ITC2021_Test5 57 22 16 12 ITC2021_Test6 581 117 104 88 ITC2021_Test7 1209 140 139 122 ITC2021_Test8 296 22 21 9
Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E- ISSN 2503-2933 553
Gambar 2. Bagan Penurunan Penalty Test5-Test8
Dari Gambar dan Tabel diatas, ditemukan bahwa tidak selalu data yang semakin kompleks  semakin  gagal.  Dapat  dikatakan  cukup  anomali.  Seperti  yang  ditunjukkan pada  instance  Test8  yang  menurun  lebih  kecil  daripada  Test7.  Untuk  dataset  Test3 berhasil feasible pada tahap swap .

## 4. KESIMPULAN
Pembentukan solusi awal dengan cara mengoptimasi pelanggaran menggunakan LLH swap hanya  berhasil feasible 1  dari  8 test  instance. Dapat  dikatakan  dataset  ini sangat baru, sehingga mencari perbandingannya sedikit sulit. Penalti dapat turun dengan baik  setelah  dilakukan swap  home,  swap  round, dan swap  team. .  Butuh  iterasi  cukup banyak untuk menurunkan penalti dataset yang semakin kompleks

## 5. SARAN
Dalam penelitian ini, tidak ada kombinasi LLH lain yang diuji. Pada penelitian selanjutnya, LLH yang telah digunakan dengan LLH lain, seperti team swap dan round swap ,  dapat  ditambahkan  atau  diganti.  Dengan  mencoba  berbagai  jenis  LLH,  saya berharap mereka dapat menghasilkan solusi yang lebih baik.
554 Jatisi ISSN 2407-4322 Vol. 9, No. 1, Maret 2022, Hal. 547-554 E-ISSN 2503-2933

## DAFTAR PUSTAKA
[1] D. Van Bulck, D. Goossens, J. Schönberger, and M. Guajardo, 2020, “RobinX: A Three-Field  Classification  and  Unified  Data  Format  For  Round-Robin  Sports Timetabling,” Eur.  J.  Oper.  Res. ,  Vol.  280,  No.  2,  pp.  568–580,  doi: 10.1016/j.ejor.2019.07.023.
[2] G. Kendall, S. Knust, C. C. Ribeiro, and S. Urrutia, 2010, “Scheduling in sports: An Annotated Bibliography,” Comput. Oper. Res. , Vol. 37, No. 1, pp. 1–19, doi: 10.1016/j.cor.2009.05.013.
[3] B.  C.  Ball  and  D.  B.  Webster,  1977,  “ Optimal  Scheduling  For  Even-Numbered Team  Athletic  Conferences,”  AIIE  Trans. ,  Vol.  9,  No.  2,  pp.  161–169,  doi: 10.1080/05695557708975138.
[4] E.  K.  Burke  and  Y.  Bykov,  2017, “The  Late  Acceptance  Hill-Climbing Heuristic,” Eur.  J.  Oper.  Res. ,  Vol.  258,  No.  1,  pp.  70–78,  doi: 10.1016/j.ejor.2016.07.012.
[5] M. Dell’Amico and M. Trubian, 1993, “Applying Tabu Search To The Job-Shop Scheduling  Problem,”  Ann.  Oper.  Res. ,  Vol.  41,  No.  3,  pp.  231–252,  doi: 10.1007/BF02023076.
[6] M. Gendreau and J.-Y. Potvin, 2010. Handbook of Metaheuristics: International Series in Operations research e Management Science .
[7] T. Januario, C. C. Ribeiro, and D. De Werra, “Keywords :”
[8] J.  Schönberger,  D.  C.  Mattfeld,  and  H.  Kopfer,  2004, “Memetic  Algorithm Timetabling For Non-Commercial Sport Leagues,” Eur. J. Oper. Res. , Vol. 153, No. 1, pp. 102–116, doi: 10.1016/S0377-2217(03)00102-4.
[9] C.  C.  Ribeiro  and  S.  Urrutia,  2007, “Heuristics  For  The  Mirrored  Traveling Tournament  Problem, ” Eur.  J.  Oper.  Res. ,  Vol.  179,  No.  3,  pp.  775–787,  doi: 10.1016/j.ejor.2005.03.061.
[10]  A.  E.  Burke,  E.  Hart,  G.  Kendall,  J.  Newall,  P.  Ross,  and  S.  Schulenburg, “Chapter  #  Hyper-Heuristics:  An  Emerging  Direction  In  Modern  Search Technology.”