The way their league functions is as follows. Once a month, couples get together at various houses, with four couples at each house (that being the most people couples are willing to host). Their league has 12 couples, so there are three venues operating simultaneously. At each house, each of the four couples plays against each of the other couples (so three games per venue per date). The objectives in forming the schedule are to minimize the variation in how often any pair of couples faces each other, and simultaneously to minimize the variation in how often a couple is called upon to host a game. The planning horizon is eight dates.
Dawn (the brighter of the two) was apparently able to construct a balanced schedule for 16 couples, four venues per date and an unspecified horizon (which I'm sure was divisible by five), despite being hampered by a degree in abstract algebra. Neither of them could find a schedule for 12 couples/eight dates, in part because it cannot be balanced: each couple plays three games per date, so 24 games total, which means they cannot play the other 11 couples an equal number of times. Bluto asked me if this was an operations research problem, which it most definitely is.
It can be attacked in a variety of ways (mixed integer program, constraint program, metaheuristic); I chose to try a MIP model first, since that's the type of software with which I'm most familiar. As with many MIP problems, the model was easy but the solution was a bit time-consuming, even after tweaking the model to eliminate some of the symmetry that plagues the problem.
I won't bore anyone with the model details, but I thought I'd post the best schedule I found, in case anyone else happens to be trying to schedule 12 team round-robins (although I suspect the parameters of this particular problem are rather unusual). In the tables below, couples are identified with the letters 'a' through 'l'; hosts are capitalized.
| Date | Game 1 | Game 2 | Game 3 |
|---|---|---|---|
| 1 | abcD | efgH | iJkl |
| 2 | aeFj | Bdhl | cgIk |
| 3 | agHj | Bfkl | cdeI |
| 4 | Abek | Cghl | dFij |
| 5 | ahiK | bcfG | dejL |
| 6 | acEl | bGij | dfhK |
| 7 | adgL | bEhi | Cfjk |
| 8 | Afil | bchJ | Degk |
Charitably assuming I transcribed that correctly, each team plays every other team either two or three times. (With 12 teams playing three games on each of eight dates, for 24 games total per team, you would expect to play nine of the other 11 teams twice and the other two three times each, so this tracks.) Everyone hosts exactly twice. In terms of meeting Bluto's stated criteria, it does pretty well; but looking at it, I wonder if I should have added a penalty for couples hosting on consecutive dates, or tried to maximize the minimum elapsed time between hosting assignments for any couple?
I am looking for a schedule for round robin bridge for 16 couples who play for seven months with four couples playing in different homes. Can you help me?
ReplyDeleteProbably. Please send the specifics (couples play once a month? every couple "volunteers" to host? at any one home, does every couple play every other couple, for a total of three rounds of two simultaneous games each?) to me at rubin AT msu DOT edu.
DeleteHi Paul, How quickly can a schedule be made for 22 tennis players of various levels. There are 11 married couples. I'd prefer for each couple to play round 1 with their spouse and then split up thereafter. I have the 11 males ranked and the 11 females ranked and ultimately have the couples ranked as well. I expect to play 6 rounds. How can I do this ?
ReplyDeleteGuess I should have included this is a round robin. My first attempt at having one of these. Thanks in advance.
ReplyDeleteThere are more details necessary, but once the details are pinned down it should be fairly easy to concoct a reasonable schedule (meaning less than an afternoon's work). If you wish, you can write to me at rubin AT msu DOT edu. It might take a round or two of emails to pin down the necessary specs.
Delete