|
Simple, set up a table...
01 02 03 04 05 .. 11
12 13 14 15 16 .. 22
This is the pairings for week one. Now rotate the table thus...
12 01 02 03 04 .. 10
13 14 15 16 17 .. 11
This is week two. On successive weeks 01 will play 12, 14, 16, .. 22, [12].
Rather than repeat, set up the table skewed and repeat...
01 02 03 04 05 .. 11
13 12 15 14 17 .. 21
/Bevin
|
| From: ROLL::USENET "USENET Newsgroup Distributor" 5-JUN-1984 22:03
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.wanted,net.math
Path: decwrl!dec-rhea!dec-turtle!bennison
Subject: Re: Algorithm for scheduling tennis matches
Posted: Mon Jun 4 08:49:04 1984
-----
One solution to the problem that I get by fooling around with
matrices for a few minutes is this:
let w(i,j) be the week that the ith and jth players play.
then w(i,j) = (i + j - 1) mod n-1 for i < j < n
and w(i,n) = (2i - 1) mod n-1 for i < n
Vick Bennison
...decvax!decwrl!rhea!turtle!bennison
(603) 881-2156
|
| From: ROLL::USENET "USENET Newsgroup Distributor" 6-JUN-1984 22:18
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.math
Path: decwrl!decvax!ucbvax!ucbcad!tektronix!tekchips!stevev
Subject: Re: Need help finding algorithm
Posted: Mon Jun 4 09:31:36 1984
> I was asked to create a schedule for opponent play in
>a league. There were 22 members in the league and they
>wanted each player to play every other player once, with
>no player playing more than once a week. That meant that
>it would be a 21 week schedule with 11 two person games a
>week. ...
A simple schedule for 2n players in 2n-1 weeks may be found by placing
the players names in two rows of n entries. The players in the same column
play each other the first week. For the next week, rotate all players
(say clockwise) except the player in the top/left position (who stays where
he is). For the week after that, perform the same rotation, etc. A
five-week six-player schedule, for example is as follows:
Week 1: Week 2: Week 3: Week 4: Week 5:
1 2 3 1 6 2 1 5 6 1 4 5 1 3 4
6 5 4 5 4 3 4 3 2 3 2 6 2 6 5
The rotation is such that 2 is always in the position that 3 was in the
previous week, 3 in 4's last position ... 6 in 2's last position, etc.
For the first week, 1 plays 6, 2 plays 5, 3 plays 4; the second week
1 plays 5, 6 plays 4 and 2 plays 3, etc.
Steve Vegdahl
Tektronix, Inc.
Beaverton, OR
|
| Newsgroups: net.math,net.wanted
Path: decwrl!decvax!mcnc!unc!ulysses!mhuxl!ihnp4!inuxc!pur-ee!CS-Mordred!Pucc-H:Pucc-I:ags
Subject: Re: Need help finding algorithm
Posted: Tue Jun 5 22:30:32 1984
The question was how to arrange a round robin schedule for N players,
specifically for N = 22. To understand the method, consider a simpler case
(N=6). Arrange the numbers 1-5 around a circle, with 6 in the center.
Connect 1-6, 2-5, and 3-4.
1
5---+---2
6
4-----3
Notice that the chords 2-5 and 3-4 have different lengths. This is essential.
We now have the pairings for the first round. To get the second-round pairings,
rotate the numbers on the circle to get
2
1---+---3
6
5-----4
and so on for succeeding rounds. The fact that the chords have different
lengths guarantees that there are no repeated matches and all possible matches
are represented after 5 rounds.
To handle N=22, the same method applies (1-21 on the circle, 22 in the center).
The only tricky part is setting up the chords for the first-round pairings.
I wrote a simple backtrack program which came up with
1-22, 2-3, 4-6, 5-8, 7-15, 9-16, 10-21, 11-20, 12-17, 13-19, 14-18.
If you know how to solve the eight queens program, you can do this. Note that
10-21 has to be considered to have length 10, not 11 (i.e. the shorter of the
two possible lengths, measuring along the circumference), and the set of
lengths (excluding the 1-22 pair) covers everything from 1 through 10. To
get the other rounds, just rotate cyclically as before, and remember that 22
stays constant. The second round therefore starts out
2-22, 3-4, 5-7, ...
What could be simpler? If you have an odd number of participants, add one
more to make it even and label the extra one a "BYE".
--
Dave Seaman
..!pur-ee!pucc-i:ags
"Against people who give vent to their loquacity
by extraneous bombastic circumlocution."
|
|
Now to make it hard:
I would like to do the same scheduling with the following provisions:
1. Each pairing will consume a certain resource (field, rink, ...)
while the match is being played. I.e. you can't play 2 tennis games
on the same court at the same time.
2. The resource is only available at certain time during the week.
For example, the rink is allocated to the league that skates on
Mon, Tu, & Th nights (1 game/team/week).
3. You want to prioritize certain team's requests for a particular
time to play. For example, the team that's been in the league the
longest gets highest priority, or however else you want to do it.
This seems algorithmically similar to the n-processor/m-job scheduling
problem where you would have n resources and m teams. I was thinking of a
possible heuristic similar to pipeline-resource collision diagrams. Anybody
out there have any ideas?
Mike
|