University of Nottingham Malaysia
School of Computer Science
     
  

Operational Research

Overview

We carry out research into models, heuristics and algorithms to automatically produce high-quality solutions to a variety of real-world applications and optimisation problems, including sports scheduling, examination timetabling, manufacturing, logistics, space allocation, stock cutting.

Specifically, we attempt to model the complexity and uncertainty in real-world problems, which are often the most difficult problems to model and solve) across a wide range of application areas.

We are also investigating how we can automate the heuristic design process, by the use of a methodology that has been termed hyper-heuristics.

Below are some of our main research areas, although we are interested in any operational research/optimisation problems. 

Research Areas

A. Hyper-heuristics

One of the key aims of hyper-heuristics is to develop more general algorithms that can be utilised across a range of problem domains, rather than typical meta-heuristic methodologies which tend to be customised to a particular problem or a narrow class of problems. That is, we wish to investigate whether we can develop algorithms that:

  1. Work well across different instances of the same problem.
  2. Are able to adapt to different problem domains, without the search algorithm having to change.
  3. Do not require parameters to be tuned. Rather the hyper-heuristic algorithm is able to adapt and tune the parameters at run time.

More information is available here.

Selected Publications

  1. Bai, R; Blazewicz, J; Burke, E. K; Kendall, G and McCollum, B A Simulated Annealing Hyper-heuristic Methodology for Flexible Decision Support. 4OR - A Quarterly Journal of Operations Research, In Press.
  2. Blazewicz, J; Burke, E. K; Kendall, G; Mruczkiewicz, W; Öguz, C and Swiercz, A A hyper-heuristic approach to sequencing by hybridization of DNA sequences. Annals of Operations Research, In Press.
  3. Burke, E.K; Hyde, M; Kendall, G and Woodward, J Automating the Packing Heuristic Design Process with Genetic Programming. Evolutionary Computation, In Press.
  4. Burke, E. K; Hyde, M. R and Kendall, G Grammatical Evolution of Local Search Heuristics. IEEE Transactions on Evolutionary Computation, In Press.
  5. Burke, E. K; Kendall, G; Misir, M and Özcan, E Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Research, In Press.
  6. Sabar, N. R; Ayob, M; Qu, R and Kendall, G A Graph Coloring Constructive Hyper-Heuristic for Examination Timetabling Problems. Applied Intelligence, In Press.
  7. Bai, R; Burke, E. K; Kendall, G; Li, J and McCollum, B A Hybrid Evolutionary Approach to the Nurse Rostering Problem. IEEE Transactions on Evolutionary Computation, 14 (4): 580-590, 2010.
  8. Burke, E. K; Hyde, M; Kendall, G and Woodward, J A Genetic Programming Hyper-Heuristic Approach for Evolving 2-D Strip Packing Heuristics. IEEE Transactions on Evolutionary Computation, 14 (6): 942-958, 2010.
  9. Bai, R; Burke, E. K and Kendall, G Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation. Journal of the Operational Research Society, 59 (10): 1387-1397, 2008.
  10. Burke, E. K; Kendall, G and Soubeiga, E A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics, 9 (6): 451-470, 2003.
  11. Kendall, G and Burke, E.K Hyper-heuristics. In Wiley Encyclopedia of Operations Research and Management Science, Wiley, 2011.
  12. Burke, E.K; Hyde, M; Kendall, G; Ochoa, G; Ozcan, E and Woodward, J. R A Classification of Hyper-heuristic Approaches. In Handbook of Meta-Heuristics, pages 449-468, Kluwer, 2010.
  13. Bai, R and Kendall, G Chapter 4: An Investigation of Automated Planograms Using a Simulated Annealing Based Hyper-Heuristic. In Metaheuristics: Progress as Real Problem Solvers (Operations Research/Computer Science Interfaces Series, Volume 32, Part III), pages 87-108, Springer, 2005.
  14. Kendall, G and Hussin, N. An Investigation of a Tabu Search Based Hyper-Heuristic for Examination Timetabling. In Selected papers the 1st International Conference on Multidisciplinary Scheduling: Theory and Applications, pages 309-328, Springer, 2005.
  15. Burke, E.K; Hart, E; Kendall, G; Newall, J; Ross, P and Schulenburg, S Hyper-Heuristics: An Emerging Direction in Modern Search Technology. In Handbook of Meta-Heuristics, pages 457-474, Kluwer, 2003. 

B. Sports Scheduling

Sport has worldwide appeal, with supporters (obviously) having a significant interest, whether they attend the event live, watch it on television, listen to it on the radio or simply follow it on the internet or through the newspapers.

Sport also has an effect on the lives of those who may not follow events on the field. People who live near the stadiums will be affected, television schedules are planned around (and can disrupt) sporting events (the Football World Cup and the Olympic Games being prime examples), entire towns can feel the effect (both good and bad) of supporters when they visit for a particular event and, of course, marketing and brand promotion can have an impact on family budgets.

Events such as the Olympics Games, the Football World Cup, as well as the major golf and tennis tournaments generate huge worldwide television audiences and many sports are multi-million dollar industries, which rely on ever increasing support and marketing to increase (or even maintain) their financial stability.

A key requirement of sporting events is the ability to generate high quality schedules that optimise many different factors, including being seen to be fair to all participants (both the sports clubs and the fans).

Generating a fair set of fixtures is an important aspect, which is the area of sports scheduling I am most interested in. Producing the fixture list is just one element and there are many other (equally important) scheduling problems, such as assigning officials (referees, umpires etc.), which also must be addressed.

Selected Publications

  1. Kendall, G; Knust, S; Ribeiro, C. C and Urrutia, S Scheduling in sports: An annotated bibliography. Computers & Operations Research, 37 (1): 1-19, 2010.
  2. Kendall, G Scheduling English football fixtures over holiday periods. Journal of the Operational Research Society, 59 (6): 743-755, 2008.

More information is available here.

C. Cutting and Packing

Cutting material from stock sheets is a key process in a number of important manufacturing industries such as the sheet metal industry, the paper industry, the garment industry and the glass industry.

Cutting out the material in the most effective way usually has a financial incentive. If a company is able to minimise the amount of waste it produces then there is a quantifiable saving in the cost of raw material. This saving can either be passed on to the customer which, in turn, makes the company more competitive in the market place or the saving can be realised in increased profits for the company. In addition, the company may be able to reduce its stock holding which can make additional savings through improved cash flow. The company may also be able to reduce its warehousing capacity, resulting in further savings.

Although the normal motivation for effective stock cutting is financial, companies may have other objectives in implementing efficient stock cutting procedures. For example, there may be a requirement to meet certain orders within a given time. Under these circumstances the order in which shapes are cut may be more important than the packing so as to meet the deadline.

Consideration may also be given to the quality of the material being used. This is particularly apparent in the leather industry where a given piece of leather is not only an irregular shape but also consists of a number of different areas which vary in quality. Different parts of the final garments may require leather of different qualities. For example, the back of a leather jacket will require the leather of the best quality, whereas leather used in the lining of the jacket can use material of an inferior quality.

Underpinning the methodologies for cutting and packing are some classic combinatorial optimisation problems such as bin packing and the knapsack problem which can often provide motivation for the methodology to address the problem at hand.

Selected Publications

  1. Bai, R; Blazewicz, J; Burke, E. K; Kendall, G and McCollum, B A Simulated Annealing Hyper-heuristic Methodology for Flexible Decision Support. 4OR - A Quarterly Journal of Operations Research, In Press.
  2. Burke, E.K; Hyde, M; Kendall, G and Woodward, J Automating the Packing Heuristic Design Process with Genetic Programming. Evolutionary Computation, In Press.
  3. Burke, E. K; Hyde, M. R and Kendall, G Grammatical Evolution of Local Search Heuristics. IEEE Transactions on Evolutionary Computation, In Press.
  4. Allen, S. D; Burke, E.K and Kendall, G A hybrid placement strategy for the three-dimensional strip packing problem. European Journal of Operational Research, 209 (3): 219-227, 2011.
  5. Bak, S; Blazewicz, J; Pawlak, G; Plaza, M; Burke, E.K and Kendall, G A Parallel Branch-and-Bound Approach to the Rectangular Guillotine Strip Cutting Problem. INFORMS Journal on Computing, 23 (1): 15-25, 2011.
  6. Burke, E.K; Hyde, M.R and Kendall, G A Squeaky Wheel Optimisation Methodology for Two Dimensional Strip Packing. Computers & Operations Research, 38 (7): 1035-1044, 2011.
  7. Burke, E.K; Hellier, R; Kendall, G and Whitwell, a. G Irregular Packing using the Line and Arc No-Fit Polygon,. Operations Research, 58 (4): 948-970, 2010.
  8. Burke, E. K; Hyde, M; Kendall, G and Woodward, J A Genetic Programming Hyper-Heuristic Approach for Evolving 2-D Strip Packing Heuristics. IEEE Transactions on Evolutionary Computation, 14 (6): 942-958, 2010.
  9. Bai, R and Kendall, G A Model for Fresh Produce Shelf-Space Allocation and Inventory Management with Freshness-Condition-Dependent Demand. INFORMS Journal on Computing, 20 (1): 78-85, 2008.
  10. Burke, E.K; Hellier, R; Kendall, G and Whitwell, G Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 179 (1): 27-49, 2007.
  11. Dowsland, K.A; Gilbert, M and Kendall, G A local search approach to a circle cutting problem arising in the motor cycle industry. Journal of the Operational Research Society, 58 (4): 429-438, 2007.
  12. Burke, E. K; Hellier, R; Kendall, G and Whitwell, G A New Bottom-left-Fill Heuristic Algorithm for the 2D Irregular Packing Problem. Operations Research, 54 (3): 587-601, 2006.
  13. Dowsland, K. A; Herbert, E.A; G. Kendall, G. and Burke, E Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems. European Journal of Operational Research, 168 (2): 390-402, 2006.
  14. Burke, E.K; Kendall, G and Whitwell, G A New Placement Heuristic for the Orthogonal Stock-Cutting Problem. Operations Research, 52 (4): 655-671, 2004.
  15. Burke, E and Kendall, G Comparison of meta-heuristic algorithms for clustering rectangles. Computers and Industrial Engineering, 37 (1-2): 383-386, 1999.
  16. Bai, R and Kendall, G Chapter 4: An Investigation of Automated Planograms Using a Simulated Annealing Based Hyper-Heuristic. In Metaheuristics: Progress as Real Problem Solvers (Operations Research/Computer Science Interfaces Series, Volume 32, Part III), pages 87-108, Springer, 2005.
  17. Burke, E.K and Kendall, G Chapter 1: Introduction. In Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, pages 5-18, Springer, 2005.

More information is available here.

D. Timetabling

Our work has largely been concerned with attempting to model the real world problem of scheduling examinations that is faced every school, college and university around the world. One of the main challenges is to capture and model all the hard and soft constraints, and then investigate suitable solution methodologies to solve those problems.

Selected Publications

  1. Bai, R; Blazewicz, J; Burke, E. K; Kendall, G and McCollum, B A Simulated Annealing Hyper-heuristic Methodology for Flexible Decision Support. 4OR - A Quarterly Journal of Operations Research, In Press.
  2. Burke, E. K; Kendall, G; Misir, M and Özcan, E Monte Carlo hyper-heuristics for examination timetabling. Annals of Operations Research, In Press.
  3. Sabar, N. R; Ayob, M; Kendall, G and Qu, R A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research, In Press.
  4. Sabar, N. R; Ayob, M; Qu, R and Kendall, G A Graph Coloring Constructive Hyper-Heuristic for Examination Timetabling Problems. Applied Intelligence, 2099 - In Press.
  5. Kahar, M .N. M and Kendall, G The examination timetabling problem at Universiti Malaysia Pahang: Comparison of a constructive heuristic with an existing software solution. European Journal of Operational Research, 207 (2): 557-565, 2010.
  6. Burke, E. K; Kendall, G and Soubeiga, E A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics, 9 (6): 451-470, 2003.
  7. Kendall, G and Hussin, N. An Investigation of a Tabu Search Based Hyper-Heuristic for Examination Timetabling. In Selected papers the 1st International Conference on Multidisciplinary Scheduling: Theory and Applications, pages 309-328, Springer, 2005.

More information is available here.

Research Funding

Title : Towards More Effective Computational Search
Funding Body : EPSRC (Ref EP/H000968/1)
Amount Awarded : £1,001,333
Start Date : 22nd February 2010
End Date : 21st February 2015

Title : NETWORK: Interdisciplinary Cutting, Packing and Space Allocation
Funding Body : EPSRC (Ref EP/D031079/1)
Project Start Date : Mar 2006
Length of Project : 3 year (ended Feb 2009)
Grant Total : £63,212

Title : Symposium on Computational Intelligence & Games
Funding Body : EPSRC (Ref EP/C546024/1)
Project Start Date : Jul 2005
Length of Project : 1 year (ends Jun 2006)
Grant Total : £3,880 (to Nottingham), £3,880 (to Essex)

Title : An Investigation of Cutting/Packing and Planning using Automated Algorithm Selection
Funding Body : EPSRC (Ref GR/S52414/01)
Project Start Date : Feb 2004
Length of Project : 3 years (ends Feb 2007)
Grant Total : £153,670 (to Nottingham), £150,105 (to Southampton)

Title : Prisoners Dilemma Competition: Celebrating the 20th Anniversary
Funding Body : EPSRC (Ref GR/S63465/01)
Project Start Date : April 2004
Length of Project : 18 months (ends September 2005)
Grant Total : £11,848 (to Nottingham), £11,870 (to Birmingham)

Title : Scheduling Agents for distributed timetabling and rostering - A Visiting Fellowship
Funding Body : EPSRC (Ref GR/S53459)
Project Start Date : July 2003
Length of Project : 9 months (ends April 2004)
Grant Total : £10.350

Title : An Investigation Novel Methods for Optimising Shelf Space Allocation
Funding Body : EPSRC (Ref GR/R60577)
Project Start Date : July 2002
Length of Project : 3 years (ends July 2005)
Grant Total : £62,947

Title : Towards More Effective Computational Search
Funding Body : EPSRC (Ref EP/H000968/1)
Project Start Date : Sep 2009
Length of Project : 5 years (ends Aug 2014)
Grant Total : £1,011,159

Title : Next Generation Decision Support: Automating the Heuristic Design Process
Funding Body : EPSRC (EP/D061571/1)
Project Start Date : Mar 2006
Length of Project : 5 years (ends Feb 2011)
Grant Total : £2,663,528

Title : An investigation of the role of Genetic Programming in a Hyper-Heuristic Framework
Funding Body : EPSRC (EP/C523385/1)
Project Start Date : Oct 2005
Length of Project : 3 years (ends Sep 2008)
Grant Total : £227,675 (Nottingham), £246,984 (Essex: EP/C523377/1)

Title : Immersive Computing Games: A Visiting Fellowship
Funding Body : EPSRC (EP/C546962/1)
Project Start Date : Sep 2005
Length of Project : 3 years (ends Aug 2008)
Grant Total : £14,374

Title : Hyper-heuristics for Scheduling, Rostering and Routing: An International Collaboration: A Visiting fellowship (Prof. Michel Gendreau)
Funding Body : EPSRC (EP/D027039/1)
Project Start Date : May 2006
Length of Project : 5 years (ends May 2011)
Grant Total : £31,828

Title : Adaptive Multi-Objective Heuristic and Meta-heuristic Approaches to Space Allocation
Funding Body : EPSRC (GR/T26115/01)
Project Start Date : Apr 2005
Length of Project : 4 years (ends Apr 2009)
Grant Total : £205,378

Title :  DNA Mapping by Combinatorial Optimisation - A Visiting Fellowship  (Prof. Jacek Blazewicz)
Funding Body : EPSRC (GR/S64530/01)
Amount Awarded : £10,224
Project Start Date : Sep 2003
Length of Project : 3 years (ends May 2007)

Title : PLATFORM: Towards More General Optimisation/Search Systems
Funding Body : EPSRC (GR/S70197/01)
Project Start Date : Feb 2004
Length of Project : 5 years (ends Jan 2009)
Grant Total : £422,908

Title  : Novel Metaheuristic Research Directions in Healthcare Personnel Rostering
Funding Body : EPSRC (Ref GR/S31150/01)
Project Start Date : Oct 2003
Length of Project : 3 years (ends Mar 2007)
Grant Total : £298,081 (£191,581 from EPSRC) (ORTEC Consultants B.V.  £81,000), Gower optimal Algorithms Ltd (£22,500) and KaHo St-Lieven (£3,000)

Title : Fuzzy Multicriteria Approaches to Scheduling and Rescheduling Problems in Uncertain Environments
Funding Body : EPSRC (Ref GR/R95319/01)
Project Start Date : Jan 2003
Length of Project : 3 years (ends Feb 2006)
Grant Total : £422,337 (£211,594 to Nottingham) (£210,743 to Coventry)

Title : INTERACT CHINA: A New Research Collaboration between The University of China and the Chinese Academy of Science
Funding Body : EPSRC (GR/S73150/01)
Project Start Date : 1st April 2004
Length of Project : 3 months
Grant Total : £5,924

Title : A Hybrid Meta-heuristic Approach to Simplified Sequence-Structure-Function Problems
Funding Body : BBSRC & EPSRC (Bio-informatics initiative) (Ref 42/BIO14458)
Project Start Date : Jan 2001
Length of Project : 3 years
Grant Total : £134,844

Title : An Investigation of Hyper-Heuristic Methods
Funding Body : EPSRC (Ref GR/N36837/01)
Project Start Date : Oct 2000
Length of Project : 3 years
Grant Total : £452,890 (£196,343 to Nottingham) (£256,547 to Napier)

Title : An Interdisciplinary Scheduling Network
Funding Body : EPSRC (Ref GR/N35205)
Project Start Date : May 2001
Length of Project : 3 years
Grant Total : £62,985
Notes : This project had 14 initial partner universities from across the UK. We intend to increase that number as the project progresses

Title : Scheduling Agents for Distributed Timetabling and Rostering - A Visiting Fellowship (Prof. Amnon Meisels)
Funding Body : EPSRC (Ref GR/S53459/01)
Project Start Date : Jul 2003
Length of Project : 3 months (extended to June 2004)
Grant Total : £10,350

Title : Tutorials in Optimisation and Search Methodology: A Workshop at the Interface of Artificial Intelligence and Operational Research
Funding Bodies : EPSRC and the London Mathematical Society (LMS) under the Mathematics for IT (MathFIT) initiative.
Project Start Date : March 2003
Length of Project : 8 months
Grant Total : £5000
Notes : This grant is supporting the (INTROS) workshop.

Title : A Dual Examination of Scheduling Problems - A Visiting Fellowship (Prof. M Dror)
Funding Body : EPSRC (Ref GR/S07124/01)
Project Start Date : Jul 2002
Length of Project : 3 months
Grant Total : £7,800

Title : Applying meta-heuristics and hyper-heuristics to stock cutting
Funding Body : EPSRC and Esprit Automation Limited
Type of Award : CASE (Co-operative Awards in Science and Engineering) for New Academics (CNA 00802329)
Project Start Date : Oct 2000
Length of Project : 3 years
Grant Total : £42,120 (£28,920 from EPSRC) (£13,200 from Esprit)  

Title : New Approaches to Produce Efficient Nesting Patterns
Funding Body : Teaching Company Directorate (Department of Trade and Industry (DTI))
Type of Award : TCS Programme No 3047 between the University of Nottingham and Esprit Automation Limited
Project Start Date : Oct 2000
Length of Project : 3 years
Grant Total : £126,268 (£86,268 from DTI) (£40,400 from Esprit)

Main contact

  • Graham Kendall (web page, e-mail: Graham.Kendall*).

Links

* e-mail suffix: @nottingham.edu.my

School of Computer Science

The University of Nottingham Malaysia Campus
Jalan Broga, 43500 Semenyih
Selangor Darul Ehsan
Malaysia

telephone: +6 (03) 8924 8767
fax: +6 (03) 8924 8018

Make an enquiry