Dr Rhyd Lewis

Overview

Position: Lecturer Email: LewisR9@cardiff.ac.uk
Telephone: +44(0)29 208 74856
Fax: +44(0)29 208 74199
Extension: 74856
Location: M/0.32

Research Interests

- The application and analysis of metaheuristic algorithms;
- Automated timetabling (course and exam) and related problems;
- Grouping/Partitioning problems;
- Graph colouring;
- Sports timetabling, particularly round-robin ccheduling;
- Solving sudoku problems with metaheuristics;
- Bin-packing, trapezoid (trapezium) packing, and the equal-piles problem;
- Vehicle routing;
- Problem difficulty and problem generation;
- Scheduling, routing, and constraint satisfaction.

Research Group

Operational Research

Recent Significant Publications

Lewis, R., J. Thompson, C. Mumford, and J. Gillard (2011) 'A Wide-Ranging Computational Comparison of High-Performance Graph Colouring Algorithms'. Computers and Operations Research, DOI: 10.1016/j.cor.2011.08.010.

Lewis, R., X. Song, K. Dowsland and J. Thompson (2011) 'An Investigation into two Bin Packing Problems with Ordering and Orientation Implications'. European Journal of Operational Research, vol. 213, pp. 52-65.

Lewis, R. and J. Thompson (2011) 'On the Application of Graph Colouring Techniques in Round-Robin Sports Scheduling'. Computers and Operations Research, vol. 38(1), pp 190-204.

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.

Teaching

MA0105 Introduction to Probability

MA0276 Visual Basic Programming for OR

MAT004 Computational Methods

Administrative Duties

School
Member of Operational Research Group
Member of the Planning and Optimisation Group
Member of School Research Committee
Year-Two tutor

National/International
Associate editor for the International Journal of Metaheuristics
Program-committee member for Evolutionary Computation in Combinatorial Optimisation, EvoEnvironment, GECCO, the Congress of Evolutionary Computing and the Practice and Theory of Automated Timetabling conferences.

Personal Website

Dr Rhyd Lewis' personal webpage

Publications

2011

Lewis, R. and E. Pullin (2011) 'Revisiting the Restricted Growth Function Genetic Algorithm for Grouping Problems'. Evolutionary Computation, DOI: 10.1162/EVCO_a_00040.

Lewis, R. and J. Thompson (2011) 'On the Application of Graph Colouring Techniques in Round-Robin Sports Scheduling'. Computers and Operations Research, vol. 38(1), pp 190-204.

2010

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.

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.

2009

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.

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.

2008

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

2007

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.

2006

Lewis, R. (2006) 'Metaheuristics for University Course Timetabling'. Doctoral Thesis, Napier University, Edinburgh, Scotland.

2005

Lewis, R. and B. Paechter (2005). 'Application of the Grouping Genetic Algorithm to University Course Timetabling'. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 3448) J. Gottlieb and G. Raidl (Eds.) Berlin: Springer-Verlag, pp 144-153.

Research

I am a lecturer in Operational Research at the School of Mathematics, Cardiff University.

I am an associate editor for the International Journal of Metaheuristics

I was one of the co-organisers of the Second International Timetabling Competition, run during 2007 and 2008.

Currently, I teach the following modules in the School of Mathematics: MA0105: Introduction to Probability; MA0276: Visual Basic for Operational Research; and MAT004: Computational Methods. The online teaching resources for MA0105 can be found here (created by Dr Rob Wilson). Previously I have taught the following modules at Cardiff University: BSP658 Business Statistics (MBA); BS0511 Quantitative Methods for Business; and BS1501 Applied Statistics and Mathematics for Economics and Business (all at Cardiff Business School)."

I am a member of the program committee for Evolutionary Computation in Combinatorial Optimisation, EvoEnvironment, GECCO, and the Practice and Theory of Automated Timetabling (PATAT).

Some Useful Resources

Timetabling: Some of the research that I have done has focused on a timetabling problem formulation that was used for the International Timetabling Competition run in 2003. The twenty problem instances used in this competition can be found here. Some hard timetabling instances can also be found here. This latter set contains sixty problem instances that are intended to be more difficult than the competition instances with regards to both finding feasibility and satisfying the soft constraints. If anyone has been using these instances in their work then I'd be delighted to hear from them. Also have a look at the Second International Timetabling Competition (ITC2007), which began on the 1st of August 2007.

Sudoku: As you will see from my publications list, some of my work has concerned the use of metaheuristics (particularly simulated annealing) to help solve sudoku puzzles. If you want do download the c++ code [10KB] used for the experiments described in Lewis, R. (2007). Metaheuristics can Solve Sudoku Puzzles' Journal of Heuristics, vol. 13 (4), pp 387-401, it can be downloaded here [10KB] as a .zip file. The c++ code for the random sudoku problem instance generator [5KB] used in this research can be downloaded here [5KB] (also as a zip file).

Regarding Sudoku, here [54KB] is a very useful Sudoku to Graph Coloring Converter [54KB]. This program reads in a single sudoku problem (from a text file) and converts it into the equivalent graph coloring problem. The output file appears in the DIMACS format which can then be used as the input file for your favourite graph coloring algorithm. If a solution using the correct number of colours is found, this can then be easily converted back into the Sudoku representation, giving a valid solution to the original problem.

Postgraduate Students

Current

Miss Penny Holborn: Thesis Title: "Dynamic vehicle routing problems with pickups, deliveries and time windows"

Miss Lisa Taylor: Thesis Title: "Post-enrolment Based Course Timetabling"

Biography

Dr Rhyd Lewis is a lecturer in operational research at Cardiff School of Mathematics, Cardiff University. Previously he was a lecturer in quantitative methods at Cardiff Business School. Dr Lewis holds a PhD in Computer Science and Operational Research (Edinburgh Napier University, 2006) and a BSc in Computing (University of Wales, Swansea, 2002).

Dr Lewis is a programme committee member for a number of scientific conferences such as, EvoCop, Evo‐Environment, and PATAT. He has published articles in various scientific journals, conferences and books and is also the co‐founder and associate editor of the recently established International Journal of Metaheuristics (www.inderscience.com/ijmheur). Dr Lewis was also one of the co‐organisers of the ITC2007: the Second International Timetabling Competition. Currently he is part of the LANCS initiative (www.lancs‐initiative.ac.uk/) and is a contributing member of the WIMCS Statistics and OR cluster (www.wimcs.ac.uk).