English Íslenska

24,261
1,341
4,077

Thesis (Master's)

Please use this identifier to cite or link to this item: http://hdl.handle.net/1946/33993

Title:
• An integer programming formulation for scheduling of the Icelandic football league
• Heiltölubestunarlíkan sem býr til leikjaplan fyrir efstu deild karla í knattspyrnu á Íslandi
Degree:
• Master's
Authors:
Abstract:
• In this thesis, the process of generating a sport schedule for a round robin competition is automated. By automating the process, the scheduling time should decrease, and the schedule could potentially give a better solution by satisfying more requests from stakeholders.
The main goal for this project is to create a mathematical model by using integer programming and a two-phase approach. The presented model is used to make a schedule for the men’s highest division in the Icelandic football league in collaboration with the Icelandic Football Association (KSÍ). The current scheduling process is rather manual. KSÍ rely on a fixed table alignment from the regulations. The competition committee gathers team preferences and puts together a list of the main constraints. Next, they manually assign each team a number that best fulfills their wishes. The current process is time consuming and complex, this process can be greatly improved.
When generating the model, firstly a pattern set with equally distributed breaks is generated and used as an input for the two-phase mathematical model. A break is when a team plays two or more consecutive games either at their home venue or at an away venue. In Phase I of the mathematical model a round robin schedule is generated while taking several hard constraints into account. A second model is generated to try and minimize the breaks in the pattern set. It is done using a large set containing all possible patterns. In Phase II of the mathematical model the teams are assigned to patterns using both hard and soft constraints and depending on team preferences. The schedule for the 2019 season had already been generated when this project was started. Therefore, preliminary results are presented by using real preferences and constraints sent in by the competition manager at KSÍ. These results are compared to the schedule which KSÍ generated.
The integer programming model is able to return a good solution while taking both fairness and break minimization into account, as well as satisfying most of the requests by using a two-phase model approach. After comparing the schedule from KSÍ to the preliminary results in this project it is apparent that the model could be of great help to the competition manager at KSÍ as well as a time saver.

• Í þessu verkefni er ferlið við að útbúa leikjaplan fyrir hvert sumar gert sjálfvirkara. Með því að gera ferlið sjálfvirkara ætti tíminn sem það tekur mótastjóra KSÍ að útbúa leikjaplanið að styttast. Líkanið ætti að gefa betri niðurstöðu og gæti uppfyllt fleiri skorður og óskir liðanna.
Markmið þessa verkefnis er að setja fram stærðfræðilíkan með því að notast við heiltölubestun og tveggja fasa aðferð. Líkanið sem er sett fram býr til leikjaplan fyrir efstu deild karla í knattspyrnu. Þetta verkefni er unnið í samstarfi með Knattspyrnusambandi Íslands (KSÍ). Núverandi ferli við að útbúa leikjaplanið hjá KSÍ er að miklu leiti handvirkt. KSÍ notast við hefðbundna töfluröð sem er í reglugerðum sambandsins. Mótastjórn KSÍ kallar eftir óskum hvers félags fyrir sig og setur saman lista yfir helstu skorður. Hverju liði er næst úthlutað því númeri í töfluröðinni sem best uppfyllir óskir hvers félags fyrir sig, mótastjórn ákveður þetta númer. Núverandi aðferð er heldur tímafrek og flókin í framkvæmd, þetta ferli er hægt að bæta töluvert.
Þetta verkefni verður gert með tilliti til þess að reyna að lágmarka þann fjölda skipta sem lið spilar annaðhvort tvo heimaleiki eða útileiki í röð, slíkt kallast brot í mynstri. Í upphafi er útbúið mynstursett sem er með jafn dreifðum brotum. Það mynstursett er gert með tilliti til sanngirni þar sem hvert lið er með jafn mörg brot í mynstri. Mynstursettið er næst notað sem inntak í tveggja fasa stærðfræðilíkanið. Í Fasa I af stærðfræðilíkaninu er búin til áætlun þar sem öll lið spila hvort við annað, tvisvar sinnum á tímabilinu. Þetta er gert með því að notast við harðar skorður sem þarf að uppfylla. Annað líkan er útbúið til að reyna að lágmarka fjölda brota í mynstursettinu. Það er gert með því að útbúa stórt gagnasafn sem inniheldur öll möguleg mynstur. Í Fasa II af stærðfræðilíkaninu er hverju liði úthlutað númeri með því að notast við bæði harðar og mjúkar skorður auk þess að reyna að verða við séróskum liðanna. Leikjaplanið fyrir tímabilið 2019 hefur nú þegar verið birt, en engu að síður er útbúið líkan sem býr til leikjaplan fyrir það tímabil. Þetta er gert með því að reyna að uppfylla sömu óskir og skorður sem mótastjóri KSÍ notast við. Þær niðurstöður eru bornar saman við leikjaplanið sem KSÍ útbjó.
Heiltölubestunarlíkanið skilar góðri niðurstöðu bæði með því að taka tillit til sanngirni og lágmörkun brota í mynstri. Líkanið nær einnig að fullnægja flestum óskunum með því að nota tveggja fasa aðferðina. Samanburður á milli leikjaplansins sem KSÍ útbjó og þess sem var útbúið með hjálp líkansins í þessu verkefni sýnir að líkanið getur verið mótastjóra KSÍ mikil hjálp þegar leikjaplanið er útbúið ásamt því að spara mikinn tíma og fyrirhöfn.

Accepted:
• Jun 20, 2019
URI:
• http://hdl.handle.net/1946/33993

Files in This Item:
Filename Size VisibilityDescriptionFormat
MSC-EvaLindaGunnarsdóttir_Spring2019_Skemman.pdf2.55 MBOpenComplete TextPDF