|
Thanks for the insight. I hit upon the algorithmic description of that this morning. Here's a slightly deeper discussion of the issue, and an explanation of the solution from the direction I came across it.
Automatic scheduling is a difficult problem. My goal is, wherever possible, to simplify it into smaller problems, so that I can compose a solution to a given set of scheduling constraints out of information gained from solving smaller problems about that schedule. One of those smaller problems I ran into with the first iteration was scheduling interleague games. You can't simply schedule willy-nilly, because it's very easy for random chance to require a team be playing two other teams at once. That led me to do some work on figuring out opponent pools ahead of time: this seems like the way a human scheduler would figure things out, for one, and for another, it lets me go into matchup planning with the knowledge that this team must play these opponents, and need not be reserved for any other opponents.
The idea behind planning pools and matchups first is that by doing so, I can divide the season into three parts: divisional, subleague, and interleague parts. Each part should contain the same number of games. This means that I can plan matchups inside the pools and end up with the right number of overall games in the end. This also means that unbalanced subleague and interleague pools will end up with some divisional and subleague play scheduled, respectively, which is acceptable.
The question, then, is what constitutes a balanced pool? It's a pool where every sub-structure contributes the same number of parts, or, equivalently, where every substructure has the same number of opponents. In that case, each team requires one matchup per opposing team in the pool.
Unbalanced pools may require a different number of matchups, depending on the structure. Where n is the overall number of teams in the pool, and s is the number of teams contributed by the substructure with the fewest teams in the pool, the number of matchups required appears to be (n - s) * s. For instance, in a 3-2 pool as given above, six matchups are required. The three-team substructure plays each team from the two-team substructure twice, which leaves the three-team substructure with four matchups each and the two-team substructure with six each. The two-team substructure is finished. Each team from the three-team substructure plays each other team from within the substructure once, filling their six-matchup requirement.
With that information in hand, I can examine the number of games allocated to the type of play. If every pool is balanced, it doesn't matter—each team can schedule a slightly longer series against one opponent without wrecking the schedule. If any pool isn't balanced, we have to pick a number of games for the pool: the number closest to the desired number for the pool's type that is divisible by the number of matchups in every pool, and is a multiple of the preferred series length. At that point, we can assign series to each matchup based on the preferred series length number.
That just about wraps up the brain-work I need to do on matchup planning. Next step is to get that coded and tested, then I have to dive in on the actual scheduling. Which, I should remind you, is one of the parts I thought would be hard, in contrast to this part, which I rather incorrectly thought would be easy. :P
|