# Dr Jonathan Thompson

Director of Learning and Teaching

- Email:
- thompsonjm1@cardiff.ac.uk
- Telephone:
- +44 (0)29 2087 5524
- Location:
- M/0.27, Ground Floor, Mathematics Institute, Senghennydd Road, Cardiff, CF24 4AG

My research interests include graphic theoretic modelling, meta-heuristics (particularly ant systems, genetic algorithms and simulated annealing) and scheduling problems (examination scheduling, sports fixture scheduling and manpower planning).

### Research group

### Administrative duties

- Admissions Tutor
- Year One Director of Studies
- Marketing of Degree schemes
- Prospectus (undergraduate)
- University Open Day co-ordinator
- Chair of Schools Admissions Committee
- Member of School Management Board
- Member of School Learning and Teaching Committee
- Member of School IT committee
- Member of School Staff/Student Panel
- Member of Statistics / OR Subject Panel

### Previous positions

- Lecturer in Statistics and Operational Research, Edinburgh University, 1996-7
- Research Assistant, Swansea University, 1994-6.

### Other projects

Dr Jonathan Thompson has also completed projects with several companies including WH Smiths, John Menzies and the International Rugby Board. He is an active researcher in the areas of heuristics, and particularly in timetabling, manpower planning and scheduling. He has recently extended his research to vehicle routing problems and in particular, real time routing. He is currently a member of the organising committee of the OR49 conference held in Edinburgh this September. He has organised several streams on scheduling at OR conferences. He is on the Editorial Board of the International Journal of Operational Research and on the Programme Committee for several conferences such as GECCO, PPSN and PATAT.

### 2018

- Hawa, A. L., Lewis, R. and Thompson, J. M. 2018. Heuristics for the score-constrained strip-packing problem. Presented at: COCOA 2018: International Conference on Combinatorial Optimization and Applications, Atlanta, GA, USA, 15-17 December 2018 Presented at Kim, D., Uma, R. N. and Zelikovsky, A. eds.Combinatorial Optimization and Applications: 12th International Conference, COCOA 2018, Atlanta, GA, USA, December 15-17, 2018, Proceedings, Vol. 11346. Lecture Notes in Computer Science Springer Verlag pp. 449., (10.1007/978-3-030-04651-4_30)
- Hardy, B., Lewis, R. and Thompson, J. M. 2018. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics 24(3), pp. 321-343. (10.1007/s10732-017-9327-z)

### 2017

- Alrajhi, K., Thompson, J. and Padungwech, W. 2017. A Heuristic approach for the Dynamic Frequency Assignment problem. In: Chao, F., Schockaert, S. and Zhang, Q. eds. Advances in Computational Intelligence Systems., Vol. 650. Advances in Intelligent Systems and Computing Springer, pp. 91-103., (10.1007/978-3-319-66939-7_8)

### 2016

- Padungwech, W., Thompson, J. and Lewis, R. 2016. Investigating edge-reordering procedures in a tabu search algorithm for the capacitated arc routing problem. Presented at: HM 2016: International Workshop on Hybrid Metaheuristics, Plymouth, UK, 8-10 June 2016 Presented at Blesa, M. J., Blum, C. and Cangelosi, A. eds.Hybrid Metaheuristics: 10th International Workshop, HM 2016, Plymouth, UK, June 8-10, 2016, Proceedings, Vol. 9668. Lecture Notes in Computer Science Cham: Springer pp. 62-74., (10.1007/978-3-319-39636-1_5)
- Hardy, B., Lewis, R. and Thompson, J. M. 2016. Modifying colourings between time-steps to tackle changes in dynamic random graphs. Presented at: EvoCOP 2016: European Conference on Evolutionary Computation in Combinatorial Optimization, Porto, Portugal, 30 March - 1 April 2016 Presented at Chicano, F., Hu, B. and Garcia-Sanchez, P. eds.Evolutionary Computation in Combinatorial Optimization: 16th European Conference, EvoCOP 2016, Porto, Portugal, March 30 – April 1, 2016, Proceedings, Vol. 9595. Springer pp. 186-201., (10.1007/978-3-319-30698-8_13)
- Kheiri, A.et al. 2016. A Sequence-based selection hyper-heuristic: a case study in nurse rostering. Presented at: PATAT 2016: 11th International Conference on the Practice and Theory of Automated Timetabling, Udine, Italy, 23-26 August 2016 Presented at Burke, E. K. et al. eds.PATAT 2016: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling. pp. 503-505.

### 2015

- Kamour, A.et al. 2015. Increasing frequency of severe clinical toxicity after use of 2,4-dinitrophenol in the UK: a report from the National Poisons Information Service. Emergency Medicine Journal 32(5), pp. 383-386. (10.1136/emermed-2013-203335)
- Lewis, R. and Thompson, J. 2015. Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem. European Journal of Operational Research 240(3), pp. 637-648. (10.1016/j.ejor.2014.07.041)
- Rowse, E. L.et al. 2015. Applying set partitioning methods in the construction of operating theatre schedules. Presented at: International Conference on Theory and Practice in Modern Computing 2015, Las Palmas de Gran Canaria, Spain, 22-24 July 2015.

### 2012

- Goodman, M., Dowsland, K. A. and Thompson, J. M. 2012. Hybridising GRASP and network flows in the solution of a medical school scheduling problem. Journal of Scheduling 15(6), pp. 717-731. (10.1007/s10951-012-0289-6)
- Lewis, R.et al. 2012. A wide-ranging computational comparison of high-performance graph colouring algorithms. Computers & Operations Research 39(9), pp. 1933-1950. (10.1016/j.cor.2011.08.010)
- Song, X.et al. 2012. An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem. Computers & Operations Research 39(9), pp. 1988-2000. (10.1016/j.cor.2011.09.012)
- Dowsland, K. A. and Thompson, J. 2012. Simulated annealing. In: Rozenberg, G., Back, T. and Kok, J. N. eds. Handbook of Natural Computing.. Springer Reference Springer-Verlag, pp. 1623-1655., (10.1007/978-3-540-92910-9_49)
- Holborn, P. L., Thompson, J. M. and Lewis, R. 2012. Combining heuristic and exact methods to solve the vehicle routing problem with pickups, deliveries and time windows. Presented at: EvoCOP 2012: 12th European Conference on Evolutionary Computation in Combinatorial Optimization, Malaga, Spain, 11-13 April 2012 Presented at Hao, J. K. and Middendorf, M. eds.Evolutionary Computation in Combinatorial Optimization: 12th European Conference, EvoCOP 2012, Málaga, Spain, April 11-13, 2012. Proceedings, Vol. 7245. Lecture Notes in Computer Science Springer Verlag pp. 63-74., (10.1007/978-3-642-29124-1_6)

### 2011

- Lewis, R.et al. 2011. An investigation into two bin packing problems with ordering and orientation implications. European Journal of Operational Research 213(1), pp. 52-65. (10.1016/j.ejor.2011.03.016)
- Lewis, R. and Thompson, J. M. 2011. On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research 38(1), pp. 190-204. (10.1016/j.cor.2010.04.012)

### 2010

- Song, X.et al. 2010. A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting. European Journal of Operational Research 202(2), pp. 368-378. (10.1016/j.ejor.2009.05.047)

### 2009

- Goodman, M. D., Dowsland, K. A. and Thompson, J. M. 2009. A GRASP-knapsack hybrid for a nurse-scheduling problem. Journal of Heuristics 15(4), pp. 351-379. (10.1007/s10732-007-9066-7)

### 2007

- Parr, D. and Thompson, J. M. 2007. Solving the multi-objective nurse scheduling problem with a weighted cost function. Annals of Operations Research 155(1), pp. 279-288. (10.1007/s10479-007-0202-4)
- Dowsland, K. A. and Thompson, J. M. 2007. An improved ant colony optimisation heuristic for graph colouring. Discrete applied mathematics 156(3), pp. 313-324. (10.1016/j.dam.2007.03.025)
- Staggemeier, A.et al. 2007. Improving our knowledge of metaheuristic approaches for cell suppression problems. Presented at: UNECE/Eurostat Work Session on Statistical Data Confidentiality, Manchester, UK, 17-19 December 2007Proceedings of the Eurostat Conference on Statistical Data Confidentiality. Titchford: Eurostat, (10.2901/Eurostat.C2007.004)

### 2005

- Dowsland, K. A. and Thompson, J. M. 2005. Ant colony optimization for the examination scheduling problem. Journal of the Operational Research Society 56(4), pp. 426-438. (10.1057/palgrave.jors.2601830)

### 2000

- Dowsland, K. A. and Thompson, J. M. 2000. Solving a Nurse Scheduling Problem with Knapsacks, Networks and Tabu Search. Journal of the Operational Research Society 51(7), pp. 825-833. (10.1057/palgrave.jors.2600970)

### Undergraduate - Autumn semester

- MA0358 Mathematical Programming

### Postgraduate - Autumn semester

- MAT001 OR Methods

### Postgraduate students

#### Graduated (since 2000)

- Nick Pugh - Ants for Examination Timetabling (2004)
- David Parr - A comparison of solution methods for the nurse scheduling problem (2004)
- Steven Casey - A comparison of methods for the examination timetabling problem (2005)
- Max Wallace - The Dynamic Vehicle Routing Problem (2007)
- Melissa Goodman - Construction-Based Metaheuristics for Personnel Scheduling problems (2008)
- Vicky Reynish - An Investigation into the University Timetabling Problem (2008)
- Penny Holborn - Optimisation Method for Dynamic Operational Research Problems (2013)
- Lisa Taylor

#### Current

- Mr Bradley Hardy
- Mr Wasin Padungwech

### External funding since 2000

- Two projects with The Office of National Statistics to investigate the Cell Suppression Problem (2005 and 2006).

### Major conference talks since 2004

- 2007 – The Operational Research Society Conference, Edinburgh, UK – The Dynamic Vehicle Routing Problem
- 2006 – The Operational Research Society Conference, Bath, UK – GRASP for the nurse scheduling problem
- 2004 - Combinatorial Optimisation, Lancaster, UK - Ants for graph colouring