Introduction

Sports scheduling is a growing topic in OR research, with both theoretical models and practical applications to many sports being described in the literature. A useful survey is Kendall et al (2010), and Wright (2009) also gives many examples. However, there is still a considerable gap between the theory and the practice, although attempts are being made by some researchers to make the models more application-focused (see Trick, 2011).

Some real scheduling examples are so simple that well-established patterns can be used and models are not needed. For some round-robin leagues, for example, essentially the same schedule can be used every time, with just the names of the competing teams or players changed. Other examples are far too complex for the theoretical models to be usable. This is particularly true for professional sports where there are often large numbers of stakeholders to be satisfied—not only clubs, players and administrators but also sponsors and televisers, whose needs may be very different. Thus there may be a multiplicity of constraints and objectives, of varying levels of relative importance.

Practical scheduling work has been reported for a number of sports. These include football (della Croce and Oliveri, 2006; Kendall, 2008); cricket (Willis and Terrill, 1994; Wright, 2007); baseball (Russell and Leung, 1994); basketball (Nemhauser and Trick, 1998; Wright, 2006); tennis (della Croce et al, 1999); ice hockey (Fleurent and Ferland, 1993); American Football (Urban and Russell, 2003); and rugby union (Thompson, 1999). The methods used have included integer programming, goal programming, heuristics and metaheuristics.

However, in some cases scheduling expertise may be very useful at an earlier stage, before the format of a competition has been decided, for example as in Wright (2010), in order to gauge the impact of different ideas. Alternatives can be tested through experimentation, with such ‘what-if’ exercises helping to ensure that the expectations of what might be achievable are realistic, enabling tournament organisers to announce changes with the confidence that they will not have unfortunate consequences.

Such was the case with the scheduling of the 2011 ITM Cup in New Zealand. This is the premier domestic rugby union competition wholly within New Zealand, second in importance in the country only to Super Rugby (which includes five franchise teams from each of New Zealand, Australia and South Africa). The ITM Cup covers the whole of New Zealand from its northern tip to the far south. Although it is not a large league, with only 14 teams and 70 matches, there were a great multitude of considerations to take into account, such that no ‘standard’ off-the-peg approach could be of any value.

ITM Cup 2011

Up to and including 2009, the premier domestic competition was known as the Air New Zealand Cup, but in 2010 Independent Timber Merchants (ITM) took over the sponsorship. The format had changed slightly from year to year as the number of teams changed, and in 2010 there was just one division of 14 teams run as a single round-robin (every pair of teams meeting just once) plus semi-finals and a final. The matches took place over weekends (between Thursday and Sunday) during the season, which ran from 29 July to 5 November. During the round-robin stages every team played a match every weekend. Until 2011, the matches were scheduled by the NZRU without the aid of a computer.

However, it was clear that 2011 would have to be rather different. The Rugby World Cup (RWC) was due to take place in New Zealand in September and October 2011, meaning that there would be much less time for the ITM Cup. Because of other commitments, the earliest possible start date was 14 July, and the final would have to be played by 4 September. Thus the entire competition would have to be completed within eight weeks.

Before any scheduling took place, the New Zealand Rugby Union (NZRU), the organisers of the competition, together with the New Zealand Rugby Players' Association (NZRPA), made the following provisional decisions:

  • the same 14 teams were to take part, but split into two divisions;

  • the top seven teams from 2010 would form the ‘Premiership’ division;

  • the bottom seven teams would form the ‘Championship’ division;

  • every team was to play every other team in its own division (three at home and three away);

  • as far as possible, these matches would be at the reverse venue of the 2010 matches: that is, if team A and Team B were to be in the same division in 2011, and team A had been the home team in their 2010 match, then team B would be the home team in their 2011 match;

  • every team would play four ‘crossover’ matches, that is, against teams from the other division, two at home and two away, to be selected in a ‘selection event’ (see below);

  • there would be seven weekend rounds, in which all teams would play;

  • there would be six midweek rounds, with each team playing in three and having a bye in the other three;

  • all matches would carry full competition points, no matter whether the opponents were in the same division or not;

  • there would be no semi-finals;

  • each division would have a final;

  • the winner of the Championship final would be promoted for 2012; and

  • the seventh placed team in the Premiership would be relegated for 2012.

The selection event was to be held in November 2010, under the media spotlight. Its purpose was to determine crossover matches, that is, for each team, the identity of the teams from the other division against which they would be playing, and whether they would be at home or away.

The plan was first to organise the teams according to seedings determined by finishing position in 2010. Thus the team ending in first place was Seed 1, right down to the team finishing last being Seed 14.

The NZRU decided that they would like the event to proceed as follows.

First, each team would have one crossover opponent determined automatically according to the seedings. Seed 14 would play against Seed 1, Seed 13 would play against Seed 2, etc. The Championship teams (Seeds 14 to 8) would be the home teams.

Then there would be three ‘Picks’, for which teams would choose opponents in a prespecified order. At all stages, no team was allowed to choose an opponent against whom they were already due to play because of a previous Pick or the automatic matching. The Picks were to proceed as follows.

  • Pick 1: Championship teams at home—Premiership opponents picked by Championship teams in reverse seed order (14 to 8)

  • Pick 2: Premiership teams at home—Championship opponents picked by Premiership teams in seed order (1 to 7)

  • Pick 3: Premiership teams at home—Premiership opponents picked by Championship teams in seed order (8 to 14)

Ideally all matches from a Pick would be played during the same round of matches, if this could be achieved without undesirable repercussions (see later).

The NZRU saw the selection event as a valuable marketing opportunity to generate extra interest in the competition.

Experimental investigations

However, during the winter months of 2010, before committing themselves to these decisions or making any official announcements as to the format, the NZRU asked us to make some experimental runs to see what the effects of these and other decisions might be. They were worried that there could be unfortunate repercussions.

In order to do this, a set of fixtures had to be assumed. The first stage was to determine home and away opponents for the intra-divisional matches. For the Premiership it was very nearly possible to do this while ensuring that matches were the reverse of 2010, but not entirely, as in two cases this would have meant that a team would not have had three home and three away matches within their division. The repeated fixtures were Waikato versus Taranaki and Taranaki versus Bay of Plenty.

For the Championship this was achieved rather less well, in particular because Counties Manukau had played all of the 2010 matches against 2011 Championship teams at home. Overall there were six exceptions to the reverse rule: Tasman versus Otago, Manawatu versus Hawke's Bay, Otago versus Manawatu, and Counties Manukau against each of Manawatu, Northland and North Harbour.

This set of fixtures was later treated as fixed when the scheduling was done for real.

Since the experimentation was undertaken well before the selection event took place, assumptions also needed to be made as to the crossover matches—this was done in a fairly arbitrary manner. In addition, at this stage the provincial unions had not been asked for their preferences and requirements were unclear. Some preferences therefore had to be invented to enable the exercise to be undertaken.

Thus the experimental runs could only be a rough guide to what the final schedule might look like, but it was agreed that this would still give a reasonably clear idea of what features it might contain.

The problem was modelled as a complex combinatorial optimisation problem. This involved treating most constraints as objectives (or soft constraints leading to notional costs when not obeyed). These and other objectives were all allocated weights according to perceived importance (though these weights were varied during the course of the experimentation). Precise details and explanations of the formulations used and the solution technique applied are given later in this paper.

Consecutive matches

One very important issue concerned whether it would be possible to ensure that each team plays at most three matches in a row without a bye, and, if so, what might be the likely effect. This is an issue that is extremely important in terms of player welfare and the size of squad that must be employed. Indeed, if this could not be guaranteed then the viability of the competition might be thrown into question.

It was clear that this would be possible. With every team playing in every odd-numbered round from 1 to 13 (representing the seven weekends before the final weekend), each team would in addition need to play in three even-numbered rounds from 2 to 12, representing the midweek rounds. To ensure that a team did not play more than three matches in a row meant that it should not play in consecutive midweek slots. This could be achieved by any of the following combinations: {2, 6, 10}, {2, 6, 12}, {2, 8, 12} or {4, 8, 12}.

Given also that it was considered important (see below) that every midweek round should involve at least three matches in total, in particular that rounds 4 and 10 should involve at least three matches, this meant that six teams would have to play in rounds {2, 6, 10}, six teams would have to play in rounds {4, 8, 12}, with the remaining two playing in any one of the four possible combinations.

In the absence of other constraints, it is easy to construct possible schedules that meet these criteria. However, we were asked to go further: to examine not only the feasibility but also the likely implications of this constraint in terms of the other most important requirements as conceived at that stage, where a requirement is a criterion that must be obeyed if at all possible. The requirements were:

  • (R1) every team should have a home match in one of the first three rounds;

  • (R2) every team should have a home match in one of the last three rounds;

  • (R3) every midweek round should have either three or four matches;

  • (R4) every team should have either three or four weekend home matches; and

  • (R5) no team should at any stage have played two more matches than another team.

Several possible schedules were produced which also fully satisfied these requirements and so it was agreed that we could regard the preference not to have more than three matches in a row without a bye as a requirement (R6).

Crossover rounds

Another area of experimentation concerned the crossover matches. The NZRU were keen to have full rounds of crossover matches. Although each team was to be involved in four crossover matches, it was clear that there could not be as many as four such full rounds; because there was an odd number of teams in each division, and there was a requirement for every team to play in each of the seven weekend rounds, there would need to be at least one crossover match in every weekend round. However, it would be possible to have up to three full crossover weekend rounds, and the experimentation was designed to look at the implications, in terms of not only the requirements R1–R6 listed above, but also in terms of ‘general’ preferences (see below).

As well as requirements which have to be met, there are always a number of preferences to be considered when constructing a schedule. Here we divide them into ‘general’ and ‘specific’ preferences. General preferences refer to those applying across all teams, in contrast to specific preferences which apply only to particular teams.

At the investigatory stage, no specific preferences were assumed, though it was recognised that several would need to be recognised later when the actual scheduling was to take place. The following were the general preferences considered to judge the outcome of the experimental runs concerning crossover rounds, and also when the scheduling actually took place (though further general preferences were added later):

  • (G1) No team should have a run of three consecutive weekend homes;

  • (G2) No team should have a run of three home matches in consecutive rounds;

  • (G3) No team should have a run of four rounds without a home match—ideally no team should have run of three rounds without a home match;

  • (G4) No team should have a run of three weekend rounds without a home match;

  • (G5) No team should have a bye in each of two consecutive midweek rounds;

  • (G6) No team should have three consecutive crossover matches;

  • (G7) No team should have a pattern of home-away-home at any stage; and

  • (G8) No team should have a pattern of away-home-away at any stage.

G7 and G8 were an attempt to mitigate some of the worst features of travelling, although travel was also considered in a more precise way later.

Also for the purposes of the investigation it was necessary to generate some crossover matches from Picks 1, 2 and 3. This was done in an arbitrary but plausible manner.

The problem was modelled as a cost minimisation problem taking into account all of R1–R6 and G1–G8. The only hard constraints in the model were that no team could have more than one match in any round. Although R1–R6 were regarded informally as absolute constraints, for the purposes of the model they were regarded as soft constraints. The reason for this is that otherwise it would (a) make it much harder to find a feasible initial solution; (b) seriously inhibit the search process, since in many cases the neighbourhood sizes would be very small, making it very difficult if not impossible to travel between good feasible schedules.

The penalty costs for R1–R6 were set sufficiently high in relation to the weights applied for the general preferences (see below), so as to ensure that they were always satisfied completely. The preferences were in many cases conflicting, such that no schedule could possibly satisfy all of them. Thus weights were attached to the preferences when solving this problem (using the technique described later) in accordance with their approximate relative importance, but these weights were varied in order that several different schedules could be produced. These were discussed with the NZRU to assess their acceptability.

All the penalties and weights were reviewed when the scheduling was carried out in practice at a later stage. Appendix A shows the precise penalties used when producing the final set of solutions, and all of the notional costs of the schedule finally implemented.

The problem was then solved using a variant of simulated annealing—see the next section. This approach was used several times from different random starting solutions, ensuring that a wide variety of solutions were produced. The various solutions produced were then examined to note particular features of interest.

The experimental runs showed clearly that much better schedules could be produced if there were no requirement for crossover rounds, when almost all of the preferences could be satisfied. However, they also showed that acceptable schedules could probably be produced with one or two full crossover rounds, with a caveat that we were not using the actual crossover matches and that further preferences also had the potential to undermine this.

However, with three crossover rounds, the runs showed that it would be impossible to produce a satisfactory schedule even in the absence of any further criteria to consider. Typically a number of teams would have potentially unacceptable runs of home matches and/or runs without a home match. This situation could only get worse once further preferences, some of which were likely to be very important (eg not clashing with international matches), were incorporated.

Since the NZRU were keen to incorporate crossover rounds as part of their marketing strategy, it was therefore agreed that we would aim in practice to have two crossover rounds, with some flexibility as to which rounds they should be, though the NZRU decided that they should not be either round 1 or round 13 (the final round). The fixtures chosen in Pick 1 would form one crossover round and the fixtures chosen in Pick 2 would form the other crossover round.

Solution technique

A variant of simulated annealing was applied that uses subcost information to guide the search. This approach (Subcost-Guided Simulated Annealing, or SGSA) had been found to be beneficial for other problems of this type with many objectives (Wright, 2001). In this variant, perturbations are still always accepted if they reduce the overall cost, but the acceptance criterion for worsening solutions is different.

Standard simulated annealing accepts worse solutions with a probability e -(ΔC/T), where ΔC is the increase in overall cost and T is the temperature. In SGSA, however, ΔC is replaced in this expression by (ΔCe -(θB/ΔC)), where θ is a parameter and B is the best improvement (ie reduction) in a single subcost. Setting θ to zero reduces this to standard simulated annealing, but it had been found in Wright (2001) that values of θ from about 1.5 to 3 tended to give better results. A value of θ=2.5 was therefore used for this work.

For the initial solution, the matches in the two full crossover rounds were allocated in two blocks to two rounds at random. The remainder of the matches were all allocated separately and at random, except that it was ensured that no team was allocated to more than one match in any given round. Thus the initial solution was feasible.

The neighbourhood structure was chosen with care. If only simple swaps and insertions had been used, the neighbourhoods of feasible solutions would have been too small. For example, the only possible simple swaps involving a round with all teams playing would be to swap a match (AvB) for its reverse (BvA), and no matches could be inserted into these rounds.

The perturbations therefore were of two types. Those involving one or both crossover rounds were entire swaps of all matches in two rounds—thus all the matches in the crossover round would stay together. Otherwise Kempe Chains were used, as used by Lewis and Thompson (2011). These chains involved the swapping of some, but not necessarily all, matches between two rounds. At one extreme just one match could move; at the other extreme the entire contents of both rounds could be moved. The procedure ensured that the new solutions reached as a result of these perturbations were feasible.

The procedure for selecting a perturbation proceeded as follows.

  1. 1

    Select a match at random—call it i, currently in round R 1.

  2. 2

    Select another round R 2 at random, with R 2≠R 1.

  3. 3

    If either round R 1 or round R 2 contains a full round of crossover matches to be kept together, swap every match between round R 1 and round R 2 and end the procedure. Otherwise go to Step 4.

  4. 4

    Set up two initially empty lists of matches—call them list 1 and list 2. Mark all matches as ‘untreated’. Put fixture i on list 1.

  5. 5

    Repeat the following until every match on both lists has been ‘treated’:

    1. a)

      Find an untreated match k on list j, j=1 or 2 (this match will currently be in round R j ).

    2. b)

      Find all matches (if any) in round R 3−j which have a team in common with match k.

    3. c)

      Place these matches on list (3−j), unless they are already on this list.

    4. d)

      Mark match k as ‘treated’.

  6. 6

    Move every match in list j from round j to round (3−j), j=1 or 2.

A geometric cooling schedule was used. The starting and ending temperatures were chosen on an ad hoc basis, with the progress of the runs monitored to ensure that these were appropriate. Thus the starting temperature was adjusted until there was enough but not too much randomness at the start; and the ending temperature was adjusted until it was clear that there was enough intensification towards the end but not too much (ie not too much time being spent with no changes being accepted). Views as to what was meant by ‘enough but not too much’ were subjective, based on the prior experience of the authors.

Selection event

After the NZRU had officially announced the format for the competition, the selection event took place in November 2010 via a web conference, and the matches for Pick 1, Pick 2 and Pick 3 were determined. The tactics used by the teams to pick their opponents were very interesting and varied from Pick to Pick.

In Pick 1 it was clear that the Championship teams were choosing local opponents, presumably to maximise interest and the number of fans from both teams attending the match. In Pick 2, it appeared that the Premiership teams were using the exact opposite criterion, mainly choosing teams based a very long way away—for example, the first two picks were Canterbury choosing Northland and Waikato choosing Otago. Presumably the Premiership teams thought that these teams would be the easiest to beat because they would have to travel a long way. Finally, in Pick 3, it appeared that the Championship teams were choosing to travel to Premiership opponents partly on the basis of whom they thought they might be able to beat; the top three Premiership teams were the last three to be chosen in Pick 3.

The event generated a fair amount of media interest, both before and after the event, and in general the views were positive (Rugby Heaven, 2010a, 2010b; Manawatu Standard, 2010).

Full details of the crossover matches picked are given in Appendix B.

Further preferences

The final stage before the scheduling could begin to take place was to obtain all further preferences. Five further general preferences were added at this stage, as follows.

  • (G9) There should be no more than one crossover match in each of rounds 1, 11 and 13.

  • (G10) Each midweek round should involve at least two teams from each division.

  • (G11) Travel should be kept ‘reasonable’ as far as possible (see below).

  • (G12) Each weekend round apart from the first should contain at least one ‘backwards flexible’ match, preferably two (see below).

  • (G13) Each weekend round apart from the last should contain at least one ‘forwards flexible’ match, preferably two (see below).

The notional travel cost was determined not just by distance but, more importantly, by the proximity of major airports. Most travel between venues was to be conducted at least partly by air, with the distance travelled on an aeroplane being less important than distances travelled to get to and from the airports. The precise cost matrix used is given in Appendix C.

Flexibility was required because of the TV schedules. Since ‘weekend’ could mean any day from Thursday to Sunday and ‘midweek’ could mean either Tuesday or Wednesday, it was absolutely vital that a team playing on Thursday should not be playing in the previous midweek round (backwards flexibility) and also important (though not as vital, since there are two clear days between Sunday and Wednesday) that a team playing on Sunday should not be playing in the subsequent midweek round (forward flexibility).

At least one game needed to be offered to the TV company each weekend round that they could schedule on a Thursday, with preferably a choice of two such matches. Likewise at least one match, preferably two, needed to be offered to the TV company for televising on a Sunday.

In addition to these general preferences, 21 specific preferences were taken into account. Some were specified by the NZRU to avoid venue clashes with Test Matches (between New Zealand and other nations) or to keep certain grounds free in the run-up to the World Cup. Others were requests made by the clubs themselves. These preferences are listed in Appendix D, labelled S1 to S21.

Other preferences were initially introduced by the NZRU but later withdrawn. One such included a preference to spread out the ‘big’ matches, and others related to the Ranfurly Shield (a challenge shield held by one team at a time and surrendered to the opposition if the holders lose a match regarded as a Ranfurly Shield Challenge).

Creating the schedule

Weights were applied to all requirements and preferences, both general and specific, in approximate relation to their perceived importance, and the solution procedure described earlier was applied and solutions were produced. These were carefully inspected by the authors, and weights were changed iteratively in order to try to come up with improved solutions which would probably prove acceptable to the NZRU. Where weights were changed significantly, further monitoring of the cooling schedule took place as described earlier, since the best starting and ending temperatures necessarily depend on the weights used.

Finally a selection of good schedules was presented to and discussed with the NZRU, who eventually selected one of them as the schedule they wished to implement. According to the final set of weights used, this was in fact the second-best solution produced, but only narrowly more expensive than the ‘best’ one.

The schedule selected is shown in Table 1. The 14 teams are presented in finishing order from the previous season. Each row represents one team's matches—each column represents a round. Where an entry is blank, that team has a bye during that round. Otherwise the opposing team is shown. A plus sign means that the team for that row is at home; a minus sign means that this team is away. Premiership teams are shown in capitals; Championship teams in lower case. The square brackets around rounds 7 and 9 show that these are the full crossover rounds.

Table 1 Schedule chosen by NZRU
Full size table

The schedule fully met all the requirements R1–R6, but there were many cases of preferences not being met. Full details are in Appendix A.

What happened next?

The format was well accepted, with the fans reportedly enjoying the constant stream of matches condensed into a short period. To allow for the inconvenience of midweek matches, the NZRU provided additional funding for hotels, and also allowed teams to field eight rather than seven reserves for each match, with two reserve prop forwards rather than just one, since there was less recovery time between matches.

The Premiership saw Waikato finish in first place, with Canterbury second despite having had to play many of their home matches away from their usual ground because of earthquake damage in Christchurch. Canterbury then defeated Waikato in the final to win the Cup. Southland finished bottom and were therefore relegated to the Championship for the 2012 season.

The Championship saw Manawatu finish top after their match against Otago in Dunedin had to be postponed because of snow to a midweek date just after round 13. This gave them less time to prepare for the final, which they then lost to second-placed Hawke's Bay who were duly promoted to the Premiership for the 2012 season.

Without the World Cup to consider, the 2012 competition could have returned to the previous format, but the success of the 2011 competition persuaded the NZRU to operate a slightly modified form of the 2011 format, this time with eight weekend rounds and every team playing just two midweek matches.

Conclusion and reflections

This paper has described the scheduling of the 2010 ITM Cup. It has concentrated mainly on issues of problem experimentation, formulation and implementation, rather than the specific solution technique, since these issues formed the most interesting parts of the overall task.

The problem was complex for various reasons, including World Cup and TV requirements, but a very satisfactory outcome was achieved, with the client very happy to accept one of the recommended schedules. A noteworthy feature of the work was the frequent interaction between the analysts and the client. An important conclusion to be drawn is that good professional sports competition design requires a detailed understanding of the likely scheduling consequences before finalising the design.

Without such prior analysis, it is possible that the NZRU would have found it difficult to convince themselves and others that it would be possible to ensure that no team would play in more than three consecutive rounds. This could have jeopardised the entire tournament, perhaps leading to a truncated tournament whereby only intra-divisional matches were played, and only at weekends, with consequent reductions in income from sponsors, televisers and spectators, as well as dissatisfaction on the part of teams' supporters and criticism from the media.

In addition, without an analysis of the crossover possibilities, it is quite possible that the NZRU would have announced in advance that there would be three crossover rounds, which would almost certainly have led to either highly undesirable consequences for teams in terms of their patterns of home matches or a humiliating climb-down and loss of credibility on the part of the NZRU. Alternatively they might have decided that they would not incorporate crossover rounds at all, thus missing out on what they regarded as a good marketing opportunity.

While the exercise was very successful in practice, it is not clear whether the experimental phase of the task could have been carried out in a rather more structured fashion. For example, should greater care have been taken to try to assess the circumstances under which the presence of two crossover rounds would or would not have caused serious problems? Could some kind of experimental design principle have been of value here?

With the ever-increasing importance of television and marketing considerations, it is likely that more professional sporting competitions will want to experiment with unorthodox competition formats. Thus there may be increasing demand for the sort of ‘what-if’ exercises undertaken here.