Using a SAT‐solver to schedule sports leagues

Using a SAT‐solver to schedule sports leagues

0.00 Avg rating0 Votes
Article ID: iaor2012926
Volume: 15
Issue: 1
Start Page Number: 117
End Page Number: 125
Publication Date: Feb 2012
Journal: Journal of Scheduling
Authors: , ,
Keywords: scheduling, combinatorial optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.