Media Coverage
October 2011
Sport Scheduling Can Get Rucked
The Rugby World Cup 2011 has already seen its fair amount of controversy, but one incident grabbed my attention. It was the wrangling of the Samoan player, Eliota Fuimaono-Sapolu over the scheduling of the Samoans’ games, which saw the Samoans play Wales after only four days of rest compared to Wales’ seven.
Other teams highlighted as being hard-done by include the Georgians, the Americans and the Namibians. At the fore of the debate is that the Tier A teams are given preferential weekend slots due to sponsors and advertisers requests, leaving the week-day slots to be filled by the remaining teams.
Secondly, there is some imbalance in terms of where the teams are playing – for example, England plays three games in succession at Dunedin, reducing the amount of time spent on travel and administration.
Many vocal fans on the Net have jumped on the International Rugby Board’s supposed inability to create a reasonable and fair schedule. At a cursory glance, sports scheduling seems quite simple – but it is in fact one of most challenging areas of operations research.
Probably one of the clearest examples is Major League Baseball (MLB) in the USA. In a presentation by Professor Michael Trick of the Sports Scheduling Group, he presents the problem – scheduling the 30 baseball teams’ 162 games over a period of 182 days. He has made a business out of applying integer programming to sport schedules, and has been scheduling MLB for the past six years.
Prior to Trick, MLB was being scheduled manually (with a little computer assistance) by the husband-and-wife duo Holly and Henry Stephenson from their home in Long Island. Consider the implications of a multi-billion dollar business being scheduled by two people for more than 20 years.
More remarkable, however, is that Trick and his colleagues were only able to produce a computer-generated schedule that could trump the Stephenson’s in 2005, some nine years after accepting the challenge. That the Stephensons remained the incumbents for so long is in itself an amazing feat.
Why? Sport scheduling is an example of a NP-Hard problem. You can see an abstraction of the MLB example, which Trick has titled the Travelling Tournament Problem (TTP), here (http://mat.tepper.cmu.edu/TOURN/).
Basically, an NP-Hard problem is one that is difficult to solve at even low bounds. As you add more teams and more variables, the problem quickly becomes impossible to solve optimally by any known means.
The TTP proposes a double round-robin where all teams play each other once away and at home, cannot spend more than three consecutive days away or at home with the aim of minimising distance travelled. As of 2011, only the problem with 6 teams has been solved to optimality
While all this might provide Eliota scant comfort, fans hopefully will be less quick to judge those sport schedules. And if readers still think that scheduling major sports events is a cinch – well, give us a call; we’d be happy to hear about your multi-billion dollar talent.If you have any comments or questions, please e-mail me at rick.de.klerk@opsi.co.za.
