Multi-league sports scheduling with different leagues sizes

This paper introduces a general multi-league sports scheduling problem where timetables for multiple leagues must be determined simultaneously, a practical and challenging problem in amateur and youth sports. We consider round robin leagues with different numbers of teams, and hence also requiring different numbers of rounds. As the number of simultaneous home games that clubs can organize for their teams is limited by the capacity of their venue, the objective is to minimize capacity violations. Along with a mixed integer programming model which is formulated to optimize the starting round of each league as well as to settle when teams have their home games, we develop various methods to construct an initial solution, and a heuristic with several local search and perturbation components to improve on this. Extensive computational experiments reveal that our heuristic can efficiently provide high-quality solutions for artificial and realistic instances. We also illustrate the impact of using different sets of home-away patterns on the total venue capacity violations. Results on a real-life application from the Belgian national football association indicate that schedules based on our heuristic allow teams to substantially decrease their venue capacity without causing meaningfully more violations.