9

I am trying to create a sports league scheduler. I am having trouble identifying an algorithm to help me efficiently fill in each slot.

Sample data to build the schedule would be:

  1. 10 teams
  2. Each team plays each other 1 time (45 total games required)
  3. Each team plays no more than 1 time per day
  4. In my testing I am using 9 days with 5 slots per day.

Combo Table (contains 45 combos)

ID
Team1ID
Team2ID
bitAssigned

Schedule Table (contains 45 time slots)

scheduleID
homeTeamID
awayTeamID
GameDate
GameTime

Right now my existing procedures fill about 90% of the slots leaving 10% of my slots empty to a scheduling conflict based off the rules above.

I loop over my schedule table in ascending date/time order.
My first slot could be Saturday at 8am.
I query a list of teams that haven't been scheduled yet. I then make an array of possible combinations of those teams. I then use that array to pull 1 random record from my combinations table from of combinations that haven't been scheduled yet and I place those teams on the schedule. I then set that combination as used.

I repeat the loop over and over again and each time my list of available teams gets smaller and my array as a result is smaller too.

I'm finding that some days go fine, and on other days my final last 2 remaining teams have already played in a previous week so they are not added to the schedule again.

The only thing I havent tried yet is to "reset" the conflict days and try them over again to see if I get better placements.

Does anyone have any suggestions?

  • 5
    round-robin tournament scheduling – kevin cline Sep 11 '14 at 17:29
  • kevin thanks. your right. I it seems that right now my array starts off at the same spot everytime and there is no rotation so no orderly flow to pairing the teams up. – steve Sep 11 '14 at 17:47
  • 1
    I use a completely random approach. Randomly pick a slot and two teams. If the rules are satisfied then schedule the game. If not discard and try again. I set a limit on total attempts and if the limit is reached then discard the entire schedule and start over. It actually works quite well in practice. – Cerad Sep 11 '14 at 20:57
  • I ended up going and following the round robin approach. I'm 95% done writing the script to connect to the DB, but in testing it seems to be running smooth and balanced. I'm treating my days like "rounds" and they are staying nice and balanced. I can play my rounds in any order and put the games for each round in any order but moving a game from one round to another would ultimately break the rules. – steve Sep 12 '14 at 0:17
5

Here's an algorithm I invented myself. I don't know if it already exists or is actually the round robin implementation:

1 4    1 5   1 6   1 3   1 2
2 5    4 6   5 3   6 2   3 4
3 6    2 3   4 2   5 4   6 5

basically you start with

rotation pic

and always keep the 1 in the same position and rotate the rest.

That way you will always get a schedule of unique matches. This is extremely easy to implement and scales with any number of opponents, even or uneven. If you have an uneven number of opponents, just don't place a team in the 1 position and they have a free round.

  • 2
    how do you manage home vs away balances? – Eric Cope Oct 27 '15 at 4:20
  • This doesn't actually work - in this simple rotation algorithm, the rotating teams which are 2 slots apart (2/4, 3/5) will never play. – mdryden Jun 6 '18 at 20:50
  • @mdryden it does work. Check it better and please remove your comment. – Pieter B Jun 7 '18 at 6:31
  • @PieterB I was thinking that it would work, but it actually doesn't work if there are an odd number of teams, as the ones that are right next to each other (like 4 and 5) will never play each other. You can see it pretty easily at the end with the 1, and also at the other end because you have the dangling team (with the bye) Here's a good response that also deals with the odd number: stackoverflow.com/a/6649732/6489306 – ragingasiancoder Jul 4 '18 at 22:08
  • @ragingasiancoder if there's an odd number of teams, add a dummy team. The answer you linked describes the exact same solution as I presented. – Pieter B Jul 5 '18 at 6:37
1

I think you are doing it backwards. Don't start with the schedule table, start with a table/array/whatever of all the game combinations (the 45 games). From there, it's a simple process to assign the games to a day, based on a team only playing once a day. And since matchups only happen once (Team A only plays Team B once) the scheduling is easy because you just need to make sure that the matchup hasn't already happened (the entries are "unique" that way).

1

I generated the 10 team single round robin schedule below. It took me about 3 minutes.

Schedule info:

10 teams - 1 round robin (only the first 6 weeks are displayed)
Season start date 1/6/15 - end date 3/5/15
2 games each Tuesday, 3 games each Thursday, 5 games each week no skip dates

  • All teams are distributed to play in the 5 time slots equally.
  • All play 9 games.
  • All play each other once.
  • All are distributed evenly as home & visitor (either 5 / 4, or 4 / 5). Note: at the end of round robin 2 all teams play 18 games (9 as home & 9 as visitor) and all teams have 2 Byes.
  • All are distributed to play evenly in the 5 time slots each week.

We used an outdated Honeywell main frame computer and just under 3 years to put this whole thing together. Once our scheduling software was debugged, it took the main frame computer many hours searching millions of permutations & combinations to calculate and create the balanced patterns for 4 to 22 teams that we were looking for.

10 Team Division Schedule   DATE 12/20/14

DATE   DAY TIME    LOCATION  GM  HOME vs VISITOR

Jan  6 Tue 6:00pm  Field #1   1  # 1 vs #10 
Jan  6 Tue 6:00pm  Field #2   1  # 2 vs # 9 
Jan  8 Thu 6:30pm  Field #3   1  # 3 vs # 8 
Jan  8 Thu 6:30pm  Field #4   1  # 4 vs # 7 
Jan  8 Thu 6:30pm  Field #5   1  # 5 vs # 6

Jan 13 Tue 6:00pm  Field #1   2  # 6 vs # 3 
Jan 13 Tue 6:00pm  Field #2   2  #10 vs # 8 
Jan 15 Thu 6:30pm  Field #3   2  # 7 vs # 2 
Jan 15 Thu 6:30pm  Field #4   2  # 9 vs # 1 
Jan 15 Thu 6:30pm  Field #5   2  # 4 vs # 5

Jan 20 Tue 6:00pm  Field #1   3  # 7 vs # 9 
Jan 20 Tue 6:00pm  Field #2   3  # 5 vs # 2 
Jan 22 Thu 6:30pm  Field #3   3  # 6 vs #10 
Jan 22 Thu 6:30pm  Field #4   3  # 3 vs # 4 
Jan 22 Thu 6:30pm  Field #5   3  # 8 vs # 1

Jan 27 Tue 6:00pm  Field #1   4  # 9 vs # 5 
Jan 27 Tue 6:00pm  Field #2   4  # 1 vs # 7 
Jan 29 Thu 6:30pm  Field #3   4  # 2 vs # 3 
Jan 29 Thu 6:30pm  Field #4   4  # 8 vs # 6 
Jan 29 Thu 6:30pm  Field #5   4  #10 vs # 4

Feb  3 Tue 6:00pm  Field #1   5  # 4 vs # 8 
Feb  3 Tue 6:00pm  Field #2   5  # 7 vs # 5 
Feb  5 Thu 6:30pm  Field #3   5  # 1 vs # 6 
Feb  5 Thu 6:30pm  Field #4   5  #10 vs # 2 
Feb  5 Thu 6:30pm  Field #5   5  # 3 vs # 9

Feb 10 Tue 6:00pm  Field #1   6  # 3 vs # 7 
Feb 10 Tue 6:00pm  Field #2   6  # 6 vs # 4 
Feb 12 Thu 6:30pm  Field #3   6  # 5 vs # 1 
Feb 12 Thu 6:30pm  Field #4   6  # 9 vs #10 
Feb 12 Thu 6:30pm  Field #5   6  # 8 vs # 2 

There is no algorithm that solves the overall scheduling problems associated with the hundreds or thousands of different types of leagues, sports, and potential situations. What we did to solve this problem was to take a different approach to calculate schedules. It starts with the very complex math to determine proper round robin team pairings (match-ups), but that was just the beginning. Other pieces are needed to create a useful balanced schedule that can be published and distributed. Players, coaches, parents, etc., all need to know not only who they are playing; but where they are playing; what time they are playing; if they are home or visitor; and for many leagues, a game number.

I hope this helps you and others understand what took us 3 years to figure out.

protected by gnat Dec 23 '14 at 10:27

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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