Article ID: | iaor2012926 |
Volume: | 15 |
Issue: | 1 |
Start Page Number: | 117 |
End Page Number: | 125 |
Publication Date: | Feb 2012 |
Journal: | Journal of Scheduling |
Authors: | Bartsch Thomas, Horbach Andrei, Briskorn Dirk |
Keywords: | scheduling, combinatorial optimization |
Tournament schedules of sports leagues have to satisfy several types of constraints such as stadium unavailability, fixed matches, forbidden matches, minimum number of breaks. Usually, there is no schedule satisfying all given constraints and, hence, some of the constraints are considered as ‘soft’ ones. There are various models appropriately describing the environment of sport leagues. Only heuristic methods are known from the literature for solving instances of real life dimensions. We consider here a model which satisfies the demands of many sports leagues. We solve our model by reduction to series of instances of the propositional satisfiability problem and adaption of a satisfiability solver for these specific instances. We test our method on two real life examples and solve the problem optimally within our model in each case. Our solver shows good computational results also on generated test instances, which are motivated by real life requirements. It can be easily extended to meet the demands of other sports leagues.