Kicking Timetabling Problems into Touch

- scheduling the 1999 Rugby World Cup

by Jonathan Thompson

The schedule for the 1999 Rugby Union World Cup had to satisfy the Organising Committee, various Rugby Unions and several television companies as well as being fair to all the competing teams. Consequently producing the schedule was a complex multi-objective problem and a meta-heuristic based approach was envisaged; however an intensive analysis of the problem lead to a satisfactory schedule being produced using manual methods. This schedule was compared with solutions generated using tabu search, with the World Cup organisers preferring the manual solution. Thus some apparently complicated problems may not be as difficult as they first seem.

-oo0oo-

Every four years, rugby fever grips the globe as the Rugby Union World Cup kicks into action. The 1999 World Cup was hosted by the sleeping giants of world rugby, Wales, and required massive organisation. One vital job fell into the hands of Operational Researchers, that of producing the tournament schedule. This paper begins by explaining the format of the World Cup before giving a formal definition of the scheduling problem. The results of a manual investigation are given and are compared with a more sophisticated meta-heuristic approach.

The 1999 Rugby World Cup divides into two parts, a group stage and a knockout stage. In the former, teams are divided into groups within which each team plays every other. In previous World Cups, there have been four groups and the two teams who finished top of each went forward to the Quarter-Finals. In 1999, each of the four home nations (Wales, England, Ireland and Scotland) and France wished to host a group, so a more complicated procedure is required to select the eight Quarter-Finalists. It was decided that the five group winners should proceed directly to the Quarter-Finals, with the five runners up and the best third place team playing off for the remaining three places. The Quarter-Finals are followed by the Semi-Finals and the Final, with the two losing Semi-Finalists playing an extra match to decide third place. The format may seem a little ‘awkward’ but has the major advantage that every game is important as there is a significant difference between finishing first and second in a group. Even the play off between the two losing Semi-Finalists is important because the winner automatically qualifies for the following World Cup; the loser does not.

Sixty-six nations competed in the Qualifying rounds, which began in Latvia in October 1996. The twenty teams who would compete in the tournament were made up of the top three from the previous World Cup (South Africa, New Zealand and France), the hosts (Wales) and sixteen qualifiers, coming from Europe (6), the Pacific region (3), America (3), Africa (1), Asia (1) and 2 others. Even before these teams were known, they had been allocated to groups. For fairness, it was desirable to make each group of equal quality. The 20 teams were ordered in terms of their perceived quality, and given seedings from 1 (best) to 20 (worst). They were then allocated to the groups as follows:

 

Group A	Group B	Group C	Group D	Group E
1	2	3	4	5
10	9	8	7	6
11	12	13	14	15
20	19	18	17	16

 

Thus the sum of the seedings of the teams in each group is equal. If all went according to these seedings, the six teams in the Quarter-Final Play-Offs would be teams 6, 7, 8, 9, 10 and 11. In order to ensure that these Play-Off matches were also of equal difficulty, they were scheduled to be between teams 6 and 11, 7 and 10 and 8 and 9 (each pair giving a total of 17). Thus they were scheduled as being:

Runner Up Group E v best 3rd Place team.
Runner Up Group D v Runner Up Group A.
Runner Up Group C v Runner Up Group B.

According to the seedings, the Quarter-Finals will be between teams 1 to 8, so for fairness, team 1 plays team 8, 2 plays 7, 3 plays 6 and 4 plays 5. Thus the Quarter-Finals are:

Winner Group A v Runner Up Group C or Runner Up Group B.
Winner Group B v Runner Up Group D or Runner Up Group A.
Winner Group C v Runner Up Group E or best 3rd Place team.
Winner Group D v Winner Group E.

The Semi-Finals would be between the winners of the first and fourth Quarter-Finals, and the second and third. It was thought that this structure produced the fairest draw while ensuring that no matches can possibly be repeated. A possible exception is the 3rd place team who can come from any group and thus, may play a repeat match.

At the time of writing, the qualification stage had been completed and the pools were as follows:

 

Group A	Group B	Group C	Group D	Group E
A1. South Africa	B1. New Zealand	C1. France	D1. Wales	E1. Australia
A2. Scotland	B2. England	C2. Fiji	D2. Argentina	E2. Ireland
A3. Spain	B3. Italy	C3. Canada	D3. Samoa	E3. USA
A4. Uruguay	B4. Tonga	C4. Namibia	D4. Japan	E4. Romania

 

Our objective is to produce a schedule for the World Cup tournament. When Wales submitted its bid to host the 1999 Rugby World Cup, a draft schedule was included, some of which is reproduced below:

 

Date	Match
Wednesday 22nd September Thursday 23rd September Friday 24th September Saturday 25th September   Sunday 26th September	D1 v D2 B3 v B4 C3 v C4 D3 v D4 E1 v E2 A3 v A4 E3 v E4 A1 v A2 B1 v B2 C1 v C2
etc

 

Many problems with this schedule were identified, the most important of which were:

1. Games were scheduled for every day of the week. Also there were discrepancies in the numbers of games scheduled for each day.
2. All the major games ie between the top two teams in each group were scheduled for the start of the tournament.
3. The schedule was not fair because teams had different intervals between matches. Some had an excessively long 12 day gap, while others had only two days between matches.
4. The total length of the World Cup was over 6 weeks, which was considered overlong.

Our task is to produce a tournament schedule which satisfies all interested parties - in particular, the Organising Committee, the relevant Rugby Unions and the television companies.

The definition of the problem

Working with Paul Thorburn, the Tournament Director of the Rugby World Cup, the following set of rules for the tournament schedule were identified:

• Each team should have an equal gap between matches. In all cases, each team should have at least three clear days between matches, but not more than seven.
• The most attractive matches ie between the top two teams in each group should be spread throughout the group phase.
• No two games should be played at the same time. However, up to four matches may be held on any one day.
• As many games as possible should be played at weekends; in particular, the matches involving the eight Foundation Unions (the 4 Home Unions, France, Australia, New Zealand and South Africa).
• The entire tournament should last about five weeks, with the Final on Saturday the 6th of November and the Semi-Finals and the Quarter-Finals on the previous weekends.
• Games from the same group should not be played on the same day.
• The opening game should be Wales (D1) against the second seeded team in their group (D2).
• Matches should be played on a maximum of four days per week.
• England and Wales should not play on the same day as some supporters may wish to watch both teams.

Which solution approach?

The problem appears to be complex, with many different objectives and constraints. Exact solution methods are not a realistic proposition due to the complexity of the problem and because the Organising Committee could not categorically prioritise the various factors. Our inclination was to use a meta-heuristic based approach due to past experience and an impressive track record on multi-objective scheduling problems. In particular, a similar problem, that of scheduling the English cricket fixtures, was solved by Wright (1994) using one example of a meta-heuristic, tabu search.

Implementing tabu search requires the definition of a cost function and a neighbourhood structure. The cost function measures the quality of each solution with regard to the objectives of the problem. The neighbourhood defines a set of solutions which can be obtained by a slight modification to the existing solution. Tabu search commences from some (normally random) starting solution. The entire neighbourhood is evaluated and the one with the best cost function is selected. This becomes the new solution and the process is repeated. The search firstly converges to a locally optimal solution, ie no neighbour has a better cost function. At this point, the search will accept the best neighbour, even if it causes an increase in the cost function. However, at the next iteration, the search will normally return to the previous solution. To avoid this cycling, a tabu list is maintained which prevents the search from visiting the last T solutions, where T >is a parameter. The tabu list forms the short term memory function and enables the search to explore a wide range of solutions.

When solving a multi-objective problem, some objectives are included in the cost function and optimised; others are incorporated into the solution space definition. The decision as to how each objective should be treated typically depends on two main factors; importance and difficulty. Objectives included in the solution space definition will always be satisfied and should be, where possible, the more important. However, those which are hard to satisfy can distort the solution space, making it difficult to generate neighbours. Thus a complete understanding of the problem is required before employing a meta-heuristic and to help us achieve this, a full manual investigation was undertaken prior to employing a more sophisticated approach.

Manual investigation

As the latter matches of the World Cup were already scheduled, we began by working backwards. As stated previously, the Final was scheduled for Saturday the 6th of November with the third place Play-Off taking place two days earlier. The Semi-Finals would be the previous weekend and the Quarter-Finals on Saturday the 23rd and Sunday the 24th of October.

In the original tournament schedule, the Quarter-Final Play-Offs were scheduled for the previous weekend, thereby ensuring maximum exposure for these matches. However, this would cause group winners to have an excessive gap (at least eleven days) between their final group match and their Quarter-Final. Therefore the Quarter-Final Play-Offs were scheduled for Wednesday the 20th of October, with the group matches being finished by the previous Saturday.

Within each group, six games will be played with each team involved in three of them. In order to obtain an equal spacing of games for all teams, these games need to be paired, such that when two teams from one group meet, the other two teams from that group play one another also. However, these two matches cannot occur on the same day and for this reason, it is impossible to give teams from the same group exactly the same gaps between matches. This is illustrated in the following example:

Day 1       Team 1 plays Team 2
Day 2       Team 3 plays Team 4

The next game must be on day 6 in order to give all teams sufficient rest.

Day 6       Team 1 plays Team 3
Day 7       Team 2 plays Team 4

Similarly the next game must be four days later.

Day 11       Team 1 plays Team 4
Day 12       Team 2 plays Team 3

Thus the matches played by Team 2 are spread over eleven days whereas those of Team 4 are spread over nine and this discrepancy cannot be avoided.

It is clear that the group matches fall neatly into three sets with each team playing one game in each set. In each set, there are ten matches (two matches in five pools) and because up to four games may be played on any one day, an entire set may be scheduled for a three day period. This can be accomplished while still ensuring that two games from the same group are not played on the same day. At this stage, the orderings of matches within a group are not important and can be determined later. Thus in order to fulfill the objective of keeping matches to just four days a week, the sets can be scheduled as follows (again working backwards):

Set 3:
Thursday 14th October to Saturday 16th October
Allowing three days rest

Set 2:
Friday 8th October to Sunday 10th October
Allowing three days rest

Set 1:
Saturday 2nd October to Monday 4th October.

The tournament organisers preferred to hold the opening match on Friday the 1st October, so Set 1 was moved accordingly. This still means that 5 of the 9 days on which group matches will be played are weekends.

The final stage is to allocate the group matches to these dates, while ensuring that England and Wales are not scheduled for the same day. Additionally, the more glamorous matches can be spread throughout the period and where possible, on weekends. This was straightforward and the following tournament schedule resulted. The matches stated for the knockout stage are those which will occur if the seedings are accurate.

Draft 1999 Rugby World Cup Tournament Schedule

Date	Proposed Match	Teams
Friday 1st October Saturday 2nd October Sunday 3rd October Friday 8th October Saturday 9th October Sunday 10th October Thursday 14th October Friday 15th October Saturday 16th October	D1 v D2 (with opening ceremony) C2 v C4 A3 v A4 B2 v B3 C1 v C3 E2 v E3 A1 v A2 B1 v B4 D3 v D4 E1 v E4 A2 v A4 C2 v C3 B1 v B2 C1 v C4 D1 v D4 E3 v E4 A1 v A3 B3 v B4 D2 v D3 E1 v E2 B1 v B3 C3 v C4 D2 v D4 A1 v A4 B2 v B4 E2 v E4 A2 v A3 C1 v C2 D1 v D3 E2 v E3	Wales v Argentina Fiji v Namibia Spain v Uruguay England v Italy France v Canada Ireland v USA South Africa v Scotland New Zealand v Tonga Samoa v Japan Australia v Romania Scotland v Uruguay Fiji v Canada New Zealand v England France v Namibia Wales v Japan USA v Romania South Africa v Spain Italy v Tonga Argentina v Samoa Ireland v Australia New Zealand v Italy Canada v Namibia Argentina v Japan South Africa v Uruguay England v Tonga Ireland v Romania Scotland v Spain France v Fiji Wales v Samoa Australia v USA
Quarter-Final Play-Offs Wednesday 20th October	2nd in E v best 3rd place team (F) 2nd in A v 2nd in D (G) 2nd in B v 2nd in C (H)	Possible Match Ireland v Spain Scotland v Argentina England v Fiji
Quarter-Finals Saturday 23rd October Sunday 24th October	1st in C v Winner F (I) 1st in D v 1st in E (J) 1st in B v Winner G (K) 1st in A v Winner H (L)	France v England Wales v Australia New Zealand v Scotland South Africa v Ireland
Semi-Finals	Winner I v Winner K (M) Winner J v Winner L (N)	France v New Zealand Wales v South Africa
Third Place Play Off	Loser M v Loser N	France v Wales
Final	Winner M v Winner N	New Zealand v South Africa

This schedule has met the criteria laid down by the World Cup Organising Committee and was accepted, with minor modifications (see conclusions).

What about meta-heuristics?

It was still of interest to ascertain whether a meta-heuristic solution method could produce equally good, or better solutions and we decided to evaluate tabu search. For a successful implementation, care must be taken when defining the solution space, neighbourhood structure and cost function and these are considered in turn.

Solution space

As the scheduling of the matches from the Quarter-Final Play-Offs and onwards is perfectly acceptable, only the scheduling of the group matches is considered here. There are 30 matches to schedule between Friday the 1st of October and Saturday the 16th of October. As the actual time of the matches does not matter at this stage, the solution space was defined as any allocation of matches to days subject to there being a maximum of 4 matches per day.

Neighbourhood

The traditional neighbourhood structure is defined by altering the value of a single variable - in our case, this would equate to altering the date of any one match. Another possibility is to exchange the dates of two matches - this can help in a situation where two matches are scheduled at a reasonably low cost, and it is expensive to move either individually, but exchanging their dates produces a decrease in cost. This is likely where two matches have a team in common. These two neighbourhoods were evaluated and are named M (move) and M/S (move and swap).

Cost function

When constructing a cost function, the various objectives and constraints have to be considered. They were listed previously and are re-stated here. Some will be dealt with in our solution space definition, others will be dealt with explicitly in the cost function:

• Each team should have an equal gap between matches. In all cases, each team should have at least three clear days between matches, but not more than seven.

It has already been shown that this objective can not be satisfied exactly. Our manual examination of the problem indicated that gaps of either 4 or 5 days between matches are likely. Thus any team with either larger or smaller gaps between matches are penalised according to:

(4 - x) * wt₁ if x < 4.

(x - 5) * wt₁ if x > 5.

where x is the gap between successive matches and wt₁ is a parameter.

• As many games as possible should be played at weekends; in particular the matches involving the Foundation Unions.
• The most attractive matches ie between teams 1 and 2 in each group should be spread throughout the group phase.

Each match y is given a score S_y equal to the number of Foundation Unions involved. The following cost function is then applied:

S_y * wt₂ if match y is not on a weekend.

This function ensures that the most attractive games are both at weekends and spread throughout the group phase, as weekends are naturally spread throughout the period.

• No two games should be played at the same time. However up to four matches may be held on any one day.

This is dealt with in the solution space definition.

• The entire tournament should last about five weeks.

This is dealt with in the solution space definition.

• Games from the same group should not be played on the same day.

A penalty of wt₃ was imposed for each instance of this constraint being broken.

• The opening game should be Wales (D1) against the second seeded team in their group (D2).

This is incorporated into the solution space definition. This will not cause any problems as it is still simple to generate the neighbourhood.

• Matches should be played on a maximum of four days per week.

Our manual investigation had indicated that to play games on 9 days of the 16 day period was ideal. The World Cup organisers indicated that this was acceptable; thus the cost function was equal to max (number of days - 9, 0) * wt₄ >where wt₄ is a parameter.

• England and Wales should not play on the same day.

Solutions that did not satisfy these objectives were eliminated from the solution space.

Thus the cost function is equal to the sum of four parts, which were each weighted according to their importance and difficulty. It was decided that wt₃ > wt₄ > wt₂ > wt₁ and after some experimentation, the following weights were used: wt₃ = 1000, wt₄ = 500, wt₂ = 10, wt₁ = 1.

Under this cost function, the schedule produced manually had a cost of 60wt₁ + 5wt₂+ 0wt₃ + 0wt₄= 110.

Experiments

The purpose of the first set of experiments was to compare the two neighbourhoods (M and M/S) and also to identify the optimal tabu list length T. Many applications have relatively small tabu lists but for reasons of completeness, the two neighbourhoods were tested with tabu list sizes ranging from 5 to 50. Each run lasted 1000 iterations and in each case, the mean cost function was taken from runs emanating from five randomly generated starting solutions. Performing further iterations produced little reward.

Figure 1 shows the results and indicates little difference between the two neighbourhoods. Each method found several schedules which could be considered as feasible, that is they had zero cost for weights 3 and 4. However, there was a large degree of variability in the results - often when one random number stream produced a high quality feasible solution, another random number stream would produce an extremely poor solution. This was due to the large weights on the different parts of the cost function which make the solution space very spiky and difficult to search. The M neighbourhood found better solutions for tabu lists of between 20 and 30 whereas the larger M/S neighbourhood required larger tabu lists. The best solution found had a cost of 134, under the M/S neighbourhood with a tabu list of size 31. For larger tabu list sizes, solution quality began to gradually decrease.

The problem with this tabu search implementation was that if the search found a schedule using just 9 days, it tended not to consider moving matches to other days as this resulted in a large increase in cost. Two methods for overcoming this problem were proposed. First the cost function was altered. The current cost function gives the same value irrespective of how many matches are on each day. Thus a solution with 3 matches on one day and 1 on another gives the same cost function value as one with 2 matches on one day and 2 on another. However the former solution can be considered to be closer to having matches on one less day, and hence to be a better solution. In order for the cost function to reflect this, it was altered to

S -wt₄ * (x_i²) where x_i = the number of matches on day i.

The two solutions described earlier would have cost functions of –10 and -8 respectively, so this cost function should guide the search towards schedules using fewer days more effectively. The previous experiments were repeated using the new cost function and a variety of values for wt₄. However, this new cost function failed to find high quality solutions, lacking the ability to converge to 9 day schedules.

A form of strategic oscillation was also evaluated. Strategic oscillation has two distinct phases; the first is standard tabu search while in the second, the search is allowed to become infeasible but in a controlled manner. In our case, we performed 20 iterations without attempting to reduce the days used to 9 ie, by setting wt₄ to 0. Figure 2 shows what happens to the full cost function when 500 iterations are conducted between oscillations.

An inspection of the results showed that strategic oscillation did guide the search to solutions using different days. Figure 3 shows the results using 5 strategic oscillations. Both neighbourhoods were used with tabu list sizes of 15 to 35 for the M neighbourhood and 30 to 50 for the M/S neighbourhood. Solution quality was much improved, with the majority of runs producing feasible solutions and the M/S neighbourhood performing particularly well. The best solution had a cost function of just 58 and, in a similar way to the manual solution, divided the matches into three distinct groups.

Conclusions

Scheduling the Rugby World Cup appeared to be complex. However, a manual investigation into the problem demonstrated that it was relatively simple to produce a high quality schedule. A tabu search implementation failed to match this quality until strategic oscillation was used to guide the search towards solutions using different days. This produced better results although not all starting solutions resulted in a feasible schedule being produced. However, this is not a major difficulty in situations where a one-off solution is required - as is the case here.

The World Cup organisers preferred the manual solution as it was more structured. Additionally they instigated several changes which reduced the quality of the solution in terms of the original objectives, for example some matches involving Foundation Unions were moved from weekends. This is clear evidence that there is little purpose in striving to obtain an optimal solution if the importance of the objectives is not clear.

Acknowledgments

The author wishes to thank Paul Thorburn for his help and advice.

For the interested reader

• Glover F (1990) ‘Tabu search: a tutorial’, Interfaces 20 (4), 74-94.
• Wright M (1994) ‘Timetabling country cricket fixtures using a form of tabu search’, JORS Vol. 45, No. 7 758-770.

JONATHAN THOMPSON lectures in Operational Research at the Department of Mathematics, Cardiff University. He holds a Bsc and PhD from Swansea University and has previously lectured at Edinburgh University. His current research interests are meta-heuristics, manpower scheduling and other multi-objective scheduling problems.

First published to members of the Operational Research Society in OR Insight July- September 1999