Schedule Strengths (3 of 3): Generating Balanced Schedules

Introduction

Hello all, this will be the last in my three-part series of articles on schedule strengths. Here are parts one and two in case you missed them.

Now that we have a schedule strength metric per team and a way to score the “balance” of an entire event’s schedule by taking the standard deviation of all team’s schedule strengths, it’s time to use this criteria to create really good schedules. That will be the focus of this article.

Approach

Rather than build up my own match scheduler from scratch, it’s way easier for me just to grab the pre-generated schedules from Cheesy Arena and use them as a starting point, so that’s what we’ll do. Huge thanks to Pat Fairbank and the developers of Cheesy Arena for making these available. I previously showed that these schedules are comparable to actual schedules used in FRC, with perhaps a slight bias towards red/blue balance and avoiding duplicate partners over having larger match gaps and avoiding duplicate opponents. If we take these schedules and just swap team indices, we can improve schedule “balances” without sacrificing other important qualities of a good schedule, and can thus avoid another algorithm of death fiasco. For each of the Cheesy Arena schedules, I iterated through the team indices and kept swapping teams until I couldn’t improve the schedule anymore. I would only swap team indices if swapping them decreased the standard deviation of schedule strengths of all teams. This method guarantees local optimality in the sense that, there exists no pair of teams which can be swapped to make the schedule more balanced. I did not try to achieve global optimality as that is a vastly more difficult problem which I believe will provide negligible gain. I’m not even sure that there exists a way to check if a schedule is globally optimal short of generating all possible schedules, of which there are (# of teams) factorial, or about 1047 for a 40 team event. Regardless, I believe the locally optimal schedules are quite good, more on that below.

Generated Schedules

I’ve created a pull request to Cheesy Arena to incorporate these schedules, so if the developers choose to merge them in that might be the easiest spot to access them. However, I have also uploaded a zipped folder of all of the schedules here. Feel free to review them to look for errors. In addition to making sure the general schedule is acceptable (all teams have the same number of matches, no back-to-back matches, reasonable red-blue balance, minimal duplicate partners/opponents, etc…), you can also check that each team’s schedule is reasonably balanced by using the metric found in my first article. I’ll walk through one example now. If you look at the 40 team, 12 matches per team schedule (40_12_balanced.csv) and look at the team with index 19, you get the following list of partners and opponents:

To get the schedule strength, we sum all partners and the average team’s rank (20.5 in this case), and then subtract out all opponent team ranks. Summing the partners gives 495, and the opponents gives 738, so the schedule strength is 495+(20.5*12)-738=3. Similarly, the schedule strengths for team indices 7 and 38 are -6 and 8 respectively. Compare these to the schedule strengths for the same indices in the unbalanced 40_12.csv schedule in cheesy arena, and you get -56, -19, and -17, which are clearly much further from 0 than the scores we get from the balanced schedules.

Results

I took the 40-team, 12 matches per team “balanced” schedule I created, and fed it into my event simulator for the 3 Michigan Champs Divisions that had 40 competing teams (Consumers, Ford, and Dow). You can sort teams by whatever metric you want with these schedules, my personal opinion is that Elo > OPR >> non-award District Points > District Points >>> Team Number > Random if you’re looking for each team to actually get as fair of a schedule as possible. That said, I can’t properly evaluate how good Elo would be as a sorting method due to feedback with my event simulator, so I only compared OPR, district points, and the actual schedules (essentially random). The standard deviation of each team’s expected rank change for each method was:

So we can see that either district points or OPR provide really solid improvements over the randomized schedule, with OPR being even comfortably better than District Points. If you’re more visual, here’s a scatter plot showing how each team’s expected rank changed due to the actual schedule, and how much it would have changed using the balanced schedule with OPR as a sort:

You can see that the balancing really does avoid the really awful or really good schedules, as the 7 best and 7 worst schedules out of the 120 teams all come from the actual schedules.

Final Thoughts

These schedules were a lot of work to develop, and I’m glad I’m finally done. If anyone is crazy enough to actually want to implement these at an event, there’s still some work to be done in Cheesy Arena to allow importing of a team list sorted by some “strength” metric. Send me a message if you are going to do this and I’ll try to provide support/guidance, but otherwise I don’t think I’m going to work on this anymore unless I know the schedules are going to be used somewhere.

Good luck this build season!

Caleb

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s