1939 Jurnal Teknik Informatika dan Sistem Informasi                  ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1939-1944 E- ISSN 2503-2933

## Pembentukan Solusi Awal International Timetabling Competition 2021
Rizal Risnanda Hutama* 1 , Ahmad Muklason 2 1,2 Departemen Sistem Informasi, FTEIC ITS, Surabaya e-mail: * 1 r130498@gmail.com , 2 ahmad.muklason@gmail.com

## Abstrak
Penjadawalan  olahraga  merupakan  salah  satu  cabang  dari  optimasi  di  riset  operasi. Penjadwalan olahraga memiliki berbagai macam batasan yang menantang para peneliti untuk menyelesaikannya.  International  Timetabling  Competition  (ITC)  2021  merupakan  salah  satu kompetisi  optimasi  yang  menyediakan  permasalahan  penjadwalan  olahraga.  Permasalahan utama pada ITC 2021 yaitu menentukan jadwal waktu yang tepat untuk sebuah pertandingan. Sebuah  jadwal dikatakan dapat digunakan  (feasible) apabila tidak  melanggar  hard  constraint yang  ada.  Pembentukan  solusi  awal  yang  feasible  saat  ini  dapat  dilakukan  dengan  algoritma constraint  programming  atau  integer  programming.  Akan  tetapi,  kedua  algoritma  tersebut cukup  rumit  untuk  diimplementasikan.  Penelitian  ini  berfokus  pada  pembentukan  solusi  awal yang  feasible  dengan  cara  yang  mudah  untuk  diimplementasikan.  Cara  yang  digunakan  yaitu dengan  mengoptimasi  pelanggaran  hard  constraint  menggunakan  algoritma  Late  Acceptance Hill  Climbing  (LAHC)  dan  Tabu  Search  dengan  kerangka  kerja  Hyper-Heuristic  yang melibatkan low level heuristic (LLH). Algoritma dijalankan maksimal dengan batasan waktu 6 jam  untuk  setiap  data.  Hasil  dari  optimasi  pelanggaran  hard  constraint  menggunakan algoritma  LAHC  dan  tabu  search  dapat  menghasilkan  solusi  awal  yang  feasible  sebanyak 44.44% atau 24 dari 54 keseluruhan dataset.
Kata kunci —Penjadwalan Olahraga, Late Acceptance Hill Climbing, Tabu Search, Hyper- Heuristic

## Abstract
Sports scheduling is a branch of optimization in operations research. sports scheduling has various constraints that are challenging for researchers to solve. International Timetabling Competition  (ITC)  2021  is  an  optimization  competition  that  provides  sports  scheduling problems.  The  main  problem  at  ITC  2021  is  determining  the  right  schedule  for  a  match.  A schedule  is  feasible  if  it  does  not  violate  the  existing  hard  constraints.  The  construction  of  a feasible  initial  solution  can  now  be  done  using  a  constraint  programming  algorithm  or  an integer programming algorithm. However, both algorithms are quite complicated to implement. This  research  focuses  on  establishing  a  feasible  initial  solution  in  a  way  that  is  easy  to implement.  The  method  used  is  by  optimizing  hard  constraint  violations  using  the  Late Acceptance  Hill  Climbing  (LAHC)  algorithm  and  Tabu  Search  with  a  Hyper-Heuristic framework that involves low level heuristics (LLH). The algorithm is run maximum with a time limit of 6 hours for each data. The results of the optimization of hard constraint violations using the LAHC algorithm and tabu search can produce a feasible initial solution of 44.44% or 24 of the 54 total datasets.
Keywords —Sport Scheduling, Late Acceptance Hill Climbing, Tabu Search, Hyper-Heuristic
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1939-1944 E- ISSN 2503-2933 1940
Hutama , et., al [ Pembentukan Solusi Awal International Timetabling Competition 2021] IJCCS Vol. x, No.–end_page
1. PENDAHULUAN
ada beberapa tahun terakhir, penjadwalan olahraga menjadi bagian yang seringkali dibahas pada  dunia  riset  operasi  khususnya  dibidang  optimasi  permasalahan  kombinatorial[1]. Penjadwalan  olahraga  menjadi  pembahasan  yang  menarik  dibidang  optimasi  karena  beberapa faktor[2]. Salah satunya yaitu menjadi tantangan tersendiri karena jumlah tim olahraga berkisar 8  hingga  30,  sedangkan  kebanyakan  algoritma  hanya  mampu  menyelesaikan  8  hingga  20  tim dengan berbagai kesulitan.
International Timetabling Competitio n (ITC) merupakan sebuah kompetisi yang terkait dengan optimasi penjadwalan. Pada tahun-tahun sebelumnya, ITC menyelenggarakan kompetisi untuk  optimasi  penjadwalan  ujian  universitas.  Sedangkan  pada  tahun  ini,  ITC menyelenggarakan  kompetisi  untuk  optimasi  penjadwalan  olahraga  untuk  pertama  kalinya[3]. Dalam  permasalahan  ITC  2021  ini,  dibebaskan  untuk  menggunakan  algoritma  apapun  untuk menyelesaikannya.  Akan  tetapi,  algoritma  tersebut  harus  sama  digunakan  pada instance- instance yang lain. Seperti pada permasalahan optimasi yang lainnya, ITC 2021 juga memiliki kompenen hard  constraint , soft  constraint dan objective  function .  Dalam  permasalahan  ini, sebuah solusi dapat digunakan ( feasible ) apabila tidak terdapat pelanggaran hard constraint . Hingga saat ini algoritma atau metode yang sering digunakan untuk membentuk solusi awal  yaitu constraint  programming .  Penelitian  yang  menggunakan constraint  programming untuk  menyelesaikan  permasalahan  penjadwalan  olahraga  dilakukan  dengan  cara  membagi menjadi  2  tahapan  yaitu  menetapkan  partisipan  serta  jadwal  pertandingan  dan  menetapkan lawan  di  setiap  pertandingan[4].  Penerapan constraint  programming juga  dilakukan  pada permasalahan penjadwalan olahraga round robin [5] dan untuk menentukan jumlah venue yang dibutuhkan[6].  Selain constraint  programming ,  para  peneliti  sebelumnya  juga  menggunakan metode integer  programming untuk  menyelesaikan  permasalahan  penjadwalan  olahraga[7]. Akan  tetapi  kedua  metode  tersebut  cukup  rumit  untuk  diaplikasikan.  Oleh  karena  itu,  dalam penelitian ini mengusulkan sebuah cara yang lebih mudah untuk membentuk solusi awal yang feasible dengan mengoptimasi pelanggaran hard constraint menggunakan algoritma tertentu. Dalam  penelitian  ini,  algoritma  yang  digunakan  untuk  membentuk  solusi  awal  yaitu Late  Acceptance  Hill  Climbing (LAHC)  dan Tabu  Searh .  Algoritma  LAHC  dinilai  cukup mudah  implementasinya[8]  dan  memiliki  performa  yang  cukup    bagus[9].  LAHC  digunakan sebagai strategi untuk mengurangi pelanggaran hard constraint yang terjadi. Pengurangan hard constraint dilakukan  hingga  bernilai  nol  (0)  atau  tidak  terdapat  pelanggaran hard  constraint . Jika  tidak  terjadi  pelanggaran hard  constraint ,  maka  solusi  tersebut  dikatakan  telah feasible sebagai  solusi  awal.  Algoritma  LAHC  diimplementasikan  berdasarkan  kerangka  kerja  Hyper- Heuristic  yang  berarti  tidak  bersinggungan  langsung  dengan  domain  permasalahan  melainkan bersinggunan  dengan low  level  heuristic (LLH)  seperti  pada  Gambar  1[10].  Sedangkan Tabu Search digunakan sebagai pemilihan LLH terbaik yang akan dijalankan pada setiap iterasinya.
P
1941 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1939-1944 E- ISSN 2503-2933
Gambar 1. Kerangka Kerja Hyper-Heuristic

## 2. METODE PENELITIAN
Alur metode yang digunakan pada penelitian ini ditampilkan pada Gambar 2.

## Gambar 2. Alur Metode Penelitian

## 2.1   Pembacaan Dataset
Dataset  yang  diperoleh  dari  situs  ITC  2021  berformat  .xml.  Oleh  karena  itu,  perlu dilakukan  pembacaan  dataset  dengan  tujuan  menyimpan  dataset  tersebut  kedalam  memori sementara  untuk  keperluan  penelitian  ini.  Pembacaan  dataset  dilakukan  dengan  bantuan  SAX Parser.  Seluruh  data  yang  dibaca  akan  disimpan  kedalam  berbagai  bentuk  misalnya array, objek, ataupun variabel sesuai dengan kebutuhan penelitian.

## 2. 2 Perhitungan Hard Constraint
Dalam  permasalahan  ITC  2021  memiliki  berbagai  macam hard  constraint yang seluruhnya  harus  dilakukan  perhitungan.  Perhitungan hard  constraint ini  bertujuan  untuk mengihitung  pelanggaran  yang  terjadi.  Perhitungan hard  constraint dilakukan  berdasarkan model  matematika  pada  penelitian  RobinX[11]  yang  telah  ada  dan  diperlukan  sedikit penyesuaian untuk permasalahan ITC 2021[3].
Pembacaan Dataset
Perhitungan Hard Constraint
Pembuatan Low Level Heuristic

## Pembuatan Solusi Awal
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1939-1944 E- ISSN 2503-2933 1942

## 2.3 Pembuatan Low Level Heuristic
Low  level  heuristic (LLH)  digunakan  untuk  menghasilkan  solusi  lain  yang  bertujuan untuk menemukan solusi yang memiliki pelanggaran hard constraint lebih rendah. Pembuatan LLH  dilakukan  berdasarkan  penelitian  yang  sudah  ada[12]  dan  dilakukan  sedikit pengembangan.  LLH  yang  digunakan  pada  penelitian  ini  yaitu teamSwap , roundSwap , round3Swap dan swapHome .

## 2.4 Pembuatan Solusi Awal
Pembuatan  solusi  awal  dilakukan  dengan  cara  optimasi  pelanggaran hard  constraint menggunakan  algoritma late  acceptance  hill  climbing (LAHC).  Pembuatan  solusi  awal dilakukan  dengan  batasan  waktu  6  jam.  Jika  melebihi  6  jam  masih  terdapat  pelanggaran hard constraint maka  dapat  dikatakan  algoritma  yang  digunakan  gagal  dalam  membentuk  solusi awal.  Algoritma  LAHC  yang  diimplementasikan  menggunakan  panjang fitness  array 250. Algoritma  LAHC  dilakukan  sebagai  strategi move  acceptance dari  kandidat  solusi  yang diperoleh  dari  proses  LLH.  Setiap  iterasinya  LLH  yang  dipilih  ditentukan  oleh algoritma tabu search . Panjang tabu search yang digunakan yaitu 3.

## 3. HASIL DAN PEMBAHASAN
Algoritma  pembentukan  solusi  awal  dijalankan  Hasil  pembentukan  solusi  awal  yang dilakukan pada penelitian ini secara keseluruhan ditampilkan pada Tabel 1.
Tabel 1. Hasil Pembentukan Solusi Awal Instance Hasil Instance Hasil Test Instance Demo Feasible Middle4 Belum feasible Test1 Feasible Middle5 Feasible Test2 Feasible Middle6 Belum feasible Test3 Feasible Middle7 Belum feasible Test4 Belum feasible Middle8 Feasible Test5 Feasible Middle9 Feasible Test6 Belum feasible Middle10 Belum feasible Test7 Belum feasible Middle11 Belum feasible Test8 Belum feasible Middle12 Feasible Early1 Feasible Middle13 Belum feasible Early2 Feasible Middle14 Belum feasible Early3 Belum feasible Middle15 Feasible Early4 Belum feasible Late1 Belum feasible Early5 Belum feasible Late2 Belum feasible Early6 Belum feasible Late3 Feasible Early7 Belum feasible Late4 Feasible Early8 Feasible Late5 Feasible Early9 Feasible Late6 Belum feasible Early10 Belum feasible Late7 Belum feasible Early11 Belum feasible Late8 Feasible Early12 Belum feasible Late9 Feasible Early13 Feasible Late10 Belum feasible Early14 Feasible Late11 Feasible Early15 Belum feasible Late12 Belum feasible
1943 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1939-1944 E- ISSN 2503-2933
Middle1 Belum feasible Late13 Belum feasible Middle2 Belum feasible Late14 Feasible Middle3 Belum feasible Late15 Feasible
Dari hasil tersebut, terdapat 24 dari 54 data yang berhasil ditemukan solusi feasible , dan 30  dari  54  data  tidak  berhasil  ditemukan  solusi feasible .  Data  yang  tidak  berhasil  ditemukan solusi feasible disebabkan karena sangat terbatasnya solusi karena banyaknya batasan yang ada pada  data  tersebut.  Akan  tetapi  hasil  24  yang  berhasil  merupakan  hasil  yang  cukup  baik mengingat  mudahnya  mengimplementasikan  cara  yang  digunakan  dibandingkan  dengan penggunakaan constraint programming atau integer programming .
Jika  batasan  yang  ada  pada  sebuah  data  tidak  terlalu  banyak,  solusi  yang memungkinkan  akan  semakin  banyak  pula.  Dengan  kemungkinan  solusi  yang  lebih  banyak, penggunaan  cara  optimasi hard  constraint dapat  dilakukan.  Akan  tetapi  jika  batasan  pada sangatlah  kompleks  maka  diperlukan  cara  yang  lebih  canggih  yaitu constraint  programming atau integer programming untuk membuat solusi awal.

## 4. KESIMPULAN
Pembentukan  solusi  awal  dengan  cara  mengoptimasi  pelanggaran hard  constraint menggunakan algoritma LAHC dan tabu search dapat menghasilkan 44.44% data yang feasible . Performa  tersebut  dirasa  cukup  baik  karena  mudahnya  implementasi  cara  yang  digunakan. Seluruh  data  dapat  ditemukan  solusi  yang feasible dengan  menerapkan  algoritma constraint programming atau integer programming sesuai dengan penelitian yang sudah ada sebelumnya.

## 5. SARAN
Penelitian  ini  hanya  menggunakan  sebuah  algoritma  untuk move  acceptance  strategy sehingga  masih  banyak  algoritma  lain  yang  tidak  dilakukan  percobaan.  Penelitian  selanjutnya dapat  mengembangkan  algoritma  dengan  kombinasi  ataupun  penggantian  algoritma  dengan algoritma  yang  lebih  canggih  misalnya population-based  algorithm. Selain  itu,  penelitian selanjutnya  juga  dapat  mencari  cara  yang  mudah  selain  optimasi hard  constraint untuk membentuk solusi awal yang feasible .

## UCAPAN TERIMA KASIH
Penulis  mengucapkan  terima  kasih  kepada  Bapak  Ahmad  Muklason  selaku  dosen  dari penulis yang selalu memberikan arahan dalam penelitian ini.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1939-1944 E- ISSN 2503-2933 1944

## DAFTAR PUSTAKA
[1] L.  Zeng  and  S.  Mizuno, 2013, “On  The  Generalized  Mirrored  Scheme  For  Double Round  Robin  Tournaments  In  Sports  Scheduling,” Asia-Pacific  J.  Oper.  Res. ,  Vol.  30, No. 3, pp. 1–16, doi: 10.1142/S0217595913400083.
[2] M.  A.  Trick, 2011, “Sports  Scheduling, ” Springer  Optim.  Its  Appl. ,  Vol.  45,  pp.  489– 508, doi: 10.1007/978-1-4419-1644-0_15.
[3] D. Van Bulck, D. Goossens, J. Beliën, and M. Davari, 2021. “International Timetabling Competition 2021: Sports Timetabling,” itc2021.ugent.be.
[4] R.  A.  Russell  and  T.  L.  Urban,  2006, “A  Constraint  Programming  Approach  To  The Multiple-Venue,  Sport-Scheduling  Problem,”  Comput.  Oper.  Res. ,  Vol.  33,  No.  7,  pp. 1895–1906, doi: 10.1016/j.cor.2004.09.029.
[5] M. Henz, “Scheduling A Major College Basketball Conference - Revisited,” Oper. Res. , Vol. 49, No. 1, pp. 163–168, 2001, doi: 10.1287/opre.49.1.163.11193.
[6] L. H. Su, Y. Chiu, and T. C. E. Cheng, “Sports Tournament Scheduling To Determine The  Required  Number  of  Venues  Subject  To  The  Minimum  Timeslots  Under  Given Formats,” Comput.  Ind.  Eng. ,  Vol.  65,  No.  2,  pp.  226–232,  2013,  doi: 10.1016/j.cie.2013.02.021.
[7] T.  Van  Voorhis, “College  Basketball  Scheduling  With  Travel  Swings, ” Comput.  Ind. Eng. , Vol. 48, No. 2, pp. 163–172, 2005, doi: 10.1016/j.cie.2005.01.003.
[8] 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.
[9] A.  L.  Aro  Bolaji,  A.  F.  Bamigbola,  and  P.  B.  Shola,  2018, “Late  Acceptance  Hill Climbing  Algorithm  For  Solving  Patient  Admission  Scheduling  Problem,” Knowledge- Based Syst. , vol. 145, no. February, pp. 197–206, doi: 10.1016/j.knosys.2018.01.017.
[10] A.  Muklason,  2017. “Solver  Penjadwal  Ujian  Otomatis  Dengan  Algoritma  Maximal Clique  dan  Hyper-heuristics,”  Semin.  Nas.  Teknol.  Informasi,  Komun.  dan  Ind.  9 ,  pp. 18–19,
[11] 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.
[12] T.  Januario,  S.  Urrutia,  C.  C.  Ribeiro,  and  D.  De  Werra,  2016, “Edge  coloring:  A Natural Model For Sports Scheduling ,” Eur. J. Oper. Res. , Vol. 254, No. 1, pp. 1–8, doi: 10.1016/j.ejor.2016.03.038.