I am working on a round-robin scheduling algorithm for sports.
The goal of the algorithm is to schedule all given games across different weeks, in the given fields and given game times. These are usually round-robin or double round-robin leagues, but the number of times each team plays the other may not be the same.
Leagues are made up of different groups or categories (i.e. Ladies, Gentlemen, Under-18) with different number of teams and different number of games. The slots where games are scheduled are shared by all of them. An example of a slot can be
Field 3 10am-11am.
Match-ups are calculated beforehand using a regular round-robin algorithm, and then the scheduling algorithm works in a very straight forward way. Games in each week are scheduled in the first eligible slot:
for week in weeks: for game in games[week]: for slot in slots: if eligible(game, slot): schedule(game, slot)
A match is made up of
Home Team vs Away Team. A team is the home or the away team simply by its position in the match.
The home field constraint creates an association between a team and a field, and states that this team must play their home games in that specific field. Details to take into account:
- A team may or may not have a home field. If they do not, they can play their home games anywhere.
- A team may have more than one home field.
- Home fields can be shared: a field may be the home field of more than one team.
This last point is the whole giving me trouble. We have a two-month league with only one game time per week,
6pm-7pm on Fridays, which mean all games are simultaneous. All teams in the league have one or two home fields, and they are often shared by a couple of teams. This leads to the following issue:
home_fields[team1] -> field2 home_fields[team3] -> field2
We are trying to schedule
Team 1 vs Team 2 which is in
Week 3. As we can see, we need to schedule it in a slot with
Field 2. However, it turns out that in
Week 3 we already have
Team 3 vs Team 5, which also needs to be scheduled in
We can't just try to schedule
Team 1 vs Team 2 in a different week because then the number of times
Team 1 (and
Team 2) plays each week would end up unbalanced. Teams need to play an evenly distributed number of games per week.
We have tried a number of approaches to resolve these home field conflicts. They do help, but only to some extent:
1. Switching home-away positions
This aims at tackling the shared field issue. If two teams share the same field and both of them are the home team in the same week, we try to switch the home and away positions in one of the games. Of course, this disrupts the home and away game count for both teams, so before making the switch effective, the count must be balanced out.
for unscheduled_game in unscheduled_games: for slot in all_slots: if not eligible(unscheduled_game, slot, reason=HOME_FIELD): switch_home_away(unscheduled_game) if balance_home_away(): if not slot.game or reschedule(slot.game, all_slots, home_away_switch=True): schedule(unscheduled_game, slot)
reschedule function, as you may assume, just takes the game off its current slot and attempts to reschedule a game in any of the given slots. Note how the home away switch flag is enabled, so that the rescheduling algorithm also attempts a home away switch, up to a certain depth limit.
This helps to a point, but sometimes it does not work because either the switched game cannot be scheduled anywhere, or because the attempt to reestablish the home-away balance failed.
2. Transferring games between weeks
This procedure only works if teams play each other more than once. Let's say we have
Team 1 vs Team 2 in
Week 1 that we could not schedule. Then there is a scheduled
Team 2 vs Team 1 game in
Week 5 that does fit in a slot in
Week 1. And also, the original unscheduled game fits in a slot in
Week 5. So we simply transfer the unscheduled game from
Week 1 to
Week 5 and schedule it successfully, and reschedule the scheduled game from
Week 5 to
for unscheduled_game in unscheduled_games: for game in [g for g in scheduled_games if g.home_team == unscheduled_game.away_team and g.away_team == unscheduled.game.home_team] for slot_week_M in [s for s in slots if s.week == game.week]: if eligible(unscheduled_game, slot_week_M): for slot_week_N in [s for s in slots if s.week == unscheduled_game.week]: if eligible(game, slot_week_N): schedule(unscheduled_game, slot_week_M) schedule(game, slot_week_N)
I have unformed ideas that I have not been able to work out and put to use, or even figure out if they could be useful at all:
Advanced cross-week transfer. Perhaps there is a more complex way of transferring multiple games between multiple weeks, with more than just two teams involved. But I do not have a definite idea of how to do this or how this would help.
Switching opponents. Maybe a way to resolve conflicts is straight out changing the composition of a match. Instead of having
Team 1 vs Team 2we would make it
Team 3 vs Team 2to get rid of a home field block
Team 1may have. I am not entirely sure whether this would help, and also if this is doable at all, since we would need to try to correct the change since this would leave the schedule unbalanced (
Team 1no longer plays in that week,
Team 3now has an extra game in that week, and the number of times these involved teams play each other might have deviated too much from the accepted number).
I just ran out of ideas. What other measures could I try to solve home field constraint issues and get to schedule all games?