2

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 Field 2.

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)

The 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 Week 1.

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 2 we would make it Team 3 vs Team 2 to get rid of a home field block Team 1 may 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 1 no longer plays in that week, Team 3 now 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?

3

You have broken down the problem into match-up selection and scheduling, and of course, this break down constrains the scheduling.

You're thinking of some way to revisiting some of the match-ups when the scheduling fails.  However, perhaps you should be broadly doing the match-ups and scheduling together to have access to the fuller and broader solution space.

Generally speaking, the brute force approach would be to generate all possible acceptable solutions and then score them to find the set of best solutions.

The downside of this approach is that for some problem domains, it can take too long to search the whole solution space.  However, the upside if it works, is that you don't have to figure out how to massage or tweak a failing solution (an only partially succeeding solution) into a succeeding one, you just skip over the failing ones no matter how close.

A very real issue can be that there are no solutions found.  In those cases, you will need to relax the bar for which solutions are acceptable, and make corresponding adjustments to the scoring so you can compare these worse solutions to each other.

It is clear that in the extreme, we can construct a league for which there are no solutions: for example, if there was only one field (since the fields can be shared), then only one game per week can be played.  If that were the case, you would need to either borrow fields, or not play some games (or something else like splitting the league) — those things (e.g. borrowing fields) can be modeled and scored, so you can then at least report some hypothetical solutions and their requirements.

  • I am not sure what you are suggesting. Just trying out all combinations of match-ups and all combinations of games in slots? That is not realistic, it would take ages. Literally. I can get behind trying different match-ups instead of locking in just one, but how could I be able to tell what's the best match-up combination before starting the scheduling? Wouldn't this be similar to the switching opponents idea I mentioned? – dabadaba May 10 '18 at 10:29
  • I'd appreciate if you could revisit the former comment. – dabadaba May 23 '18 at 12:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.