Planning and Optimisation

People involved

Penny Holborn
Dr Rhyd Lewis
Lisa Taylor
Dr Jonathan Thompson

Research activites

The Planning and Optimisation Group is involved in the design and application of mathematical optimisation techniques to real life problems, particularly in the areas of scheduling and packing. These techniques can be used to introduce efficiency and reduce waste in the logistical operations of companies and government agencies.

One vibrant area of research in this group concerns the problem of timetabling. Universities, for example, periodically face the burden of scheduling exams and lectures so that a variety of complex, and often conflicting constraints are met. Members of the group have previously designed methods for such problems and were also involved in the organisation of the Second International Timetabling Competition in 2006-7 which allowed researchers from across the globe to design and test their algorithms on real-life problems in a competitive environment. The resources generated from this competition continue to stimulate new work by providing a useful access point into the field.

Members of the group are also active in the area of sports timetabling, where the aim is to produce schedules that are fair to all teams and that also satisfy constraints regarding pitch availability, television requirements etc. The group has previously worked with the International Rugby Board and the Welsh Rugby Union and has used metaheuristic search techniques to produce schedules for the 1999 Rugby World Cup, Welsh domestic rugby leagues, and all international rugby fixtures over a 12-year period.

The Planning and Optimisation Group have also published widely in the field of partitioning problems. Such problems arise regularly in industry, transportation and logistics, and include multi-dimensional packing and balancing problems, stock cutting problems, rostering problems and graph-theory. Stock cutting problems, for example, arise in areas such as the clothing and building industries, where the aim is to cut a set of predefined and possibly multi-dimensioned items from a set of equi-dimensioned “stocks” such that the wastage is minimised (thus encouraging economic savings). Previous research by the group has resulted in methods achieving state of the art results on popular benchmark problems (some of which have originated from real-world industrial processes), as well as the analysis and solving of new cutting problems provided to us by industrial partners.

Finally, the group is also investigating dynamic routing problems – that is routing problems where requirements change over time. An example is where a company receives new orders during the day and has to re-route delivery vans to the new customers while still minimising the distance travelled. High-quality solutions have been achieved using ant colony optimisation and our methods have also been applied to large scale static problems in order to divide problems into more manageable parts.

References

Lewis, R. and J. Thompson, (2010) ‘On the application of graph colouring techniques in round-robin sports scheduling’, Computers & Operations Research, DOI: 10.1016/j.cor.2010.04.012

McCollum, B., A. Schaerf, B. Paechter, P. McMullan, R. Lewis, A. Parkes, L. Di Gaspero, R. Qu, and E. Burke (2010) 'Setting The Research Agenda in Automated Timetabling: The Second International Timetabling Competition'. INFORMS Journal on Computing, vol. 22(1), pp 120-130.

Lewis, R. (2010) 'A Time-Dependent Metaheuristic Algorithm for Post Enrolment-based Course Timetabling'. Annals of Operations Research, DOI: 10.1007/s10479-010-0696-z.

Bennell, J. and X. Song (2010). ‘A beam search implementation for nesting problems’, Journal of Heuristics, vol. 16, pp 167-188.

Lewis, R. (2009) 'A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing'. Computers and Operations Research, vol. 36(7), pp 2295-2310.

Song, X., C. Chu, R. Lewis, Y. Nie, and J. Thompson (2009) 'A Worst Case Analysis of a Dynamic Programming-based Heuristic Algorithm for 2D Unconstrained Guillotine Cutting'. European Journal of Operational Research, vol. 202(2), pp 368-378.

Goodman, M, Dowsland KA and Thompson JM (2009) Hybridising GRASP and network flows in the solution of a medical school scheduling problem. Submitted to The Journal of Scheduling.

Lewis, R. (2008) 'A Survey of Metaheuristic-based Techniques for University Timetabling Problems'. OR Spectrum, vol. 30(1), pp 167-190.

Goodman, M, Dowsland KA and Thompson JM (2008) – A GRASP Hybrid Approach for a Nurse Scheduling Problem. The Journal of Heuristics.

Bennell, J. and X.Song (2008), ‘A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums’, Computers & Operations Research, vol. 35(1), pp 267-281

Lewis, R. (2007) 'Metaheuristics can Solve Sudoku Puzzles'. Journal of Heuristics, vol. 13 (4), pp 387-401.

Lewis, R., and B. Paechter. (2007) 'Finding Feasible Timetables Using Group-Based Operators'. IEEE Transactions on Evolutionary Computation, vol. 11(3), pp 397-413.

Lewis, R., B. Paechter, and O. Rossi-Doria (2007) 'Metaheuristics for University Course Timetabling'. In Evolutionary Scheduling (Studies in Computational Intelligence, vol. 49), K. Dahal, Kay Chen Tan, P. Cowling (Eds.) Berlin: Springer-Verlag, pp 237-272.

Lewis, R. (2007) 'On the Combination of Constraint Programming and Stochastic Search: The Sudoku Case'. In Hybrid Metaheuristics (Lecture Notes in Computer Science vol. 4771) T. Bartz-Beielstein, M. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, and M. Sampels (Eds.) Berlin: Springer-Verlag, pp 96-107.

Parr D and Thompson JM (2007) Solving the multi-objective nurse scheduling problem with a weighted cost function. Annals of Operational Research, 155(1), 279-288.

Thompson JM, Staggemeier A, J Smith, A Clarke (2007), Improving our Knowledge of metaheuristic approaches for cell suppression problems, proceedings of the Eurostat Conference on Statistical Data Confidentiality, Titchford.

Song, X., C. B. Chu, Y. Y. Nie and J. Bennell (2006), ‘An iterated SHP algorithm to a real-life 1.5 Dimensional Cutting Stock Problem’, European Journal of Operational Research, vol. 175, pp 1870-1889.

Dowsland KA and Thompson JM (2005) Ant Colony Optimisation for the examination scheduling problem', Journal of the OR Society 56 ,4, 426-439.

Song, X., Y. Y. Nie, and C. B. Chu (2004), ‘Hill climbing algorithm for unconstrained knapsack problem", Mini-Micro Systems (Chinese), vol.25(7), pp 1352-1355.

Thompson JM and Casey S (2003) GRASPing the Examination Scheduling Problem, Practice and Theory of Automated Timetabling IV - Selected Papers from PATAT 2002, Lecture Notes in Computer Science Series LNCS2740, Springer-Verlag, 2003.

Song, X. and Y. Y. Nie (2003), ‘Improved dynamic programming algorithm for unconstrained two-dimentional cutting stock problem’, Information and Control (Chinese), Vol. 32(1), pp 14-19.

Thompson JM and Dowsland KA (2000). Solving a Nurse Scheduling Problem with Knapsacks, Networks and Tabu Search. Journal of the OR Society 51, pp825-833.

Thompson JM and Dowsland KA (1998). A robust simulated annealing based examination timetabling system. Computers and Operations Research 25: 637-648.

Thompson JM and Dowsland KA (1996). General cooling schedules for a simulated annealing based timetabling system. Springer-Verlag Lecture Notes in Computer Science Volume 1153. The Practice and Theory of Automated Timetabling E. Burke, D. Corne, B. Paechter and P. Ross (editors)

Thompson JM and Dowsland KA (1996). Variants of simulated annealing for the examination timetabling problem, Annals of Operations Research 63: 105-128.