Need help identifying a league scheduling algorithm

Question

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?

Answer 1

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

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.

Answer 2

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).

Answer 3

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.