English Premier League scheduling using simulated annealing

Abstract

This is the first known attempt at scheduling the English Premier League (EPL), which is a NP-hard problem, in the literature. In this research an initial schedule is created using a ‘polygon’ construction method, a method which originates in graph theory. Two distinct simulated annealing metaheuristic solving methodologies are then created to improve this initial schedule. One method is based on a temperature schedule, finite epoch length and reheats while the other is based on a gradually reducing temperature schedule and non-finite epoch length. These two methods were evaluated with respect to solution quality (total penalty), reliability (variation of solution quality over numerous trials) and speed. The official schedule used by the EPL organisers was used for comparison. It was found that the first method produced comparable results, while the second produced improved results. The second method was validated over three seasons and consistently performed well. The findings in this research can be used as the maiden real-world framework and benchmark for the unsolved EPL scheduling problem in the sports scheduling literature.