Automated Scheduling Optimisation and Planning (ASAP) Research Group
  • Print
   
   

 Completed Projects


Project TitleInvestigatorFunding SourceAmount AwardedStart DateEnd Date

3D Printing Production Planning (3DPPP): reactive manufacturing execution driving re-distributed manufacturing

Martin Baumers, Dr Ender OzcanDr Jason Atkin Bit-by-Bit Network (EPSRC/ESRC) £ 42,000 01/04/2016 31/12/2016

This is a collaborative project between the Additive Manufacturing and 3D Printing Research Group (3DPRG) at the Faculty of Engineering and ASAP at the School of Computer Science. This project is an exploration of the feasibility of releasing significant additional value by adopting a reactive manufacturing execution methodology that complements the strengths of 3D printing. The approach is predicated on the replacement of the existing allocation process by a combined “all-rolled-into-one” optimisation-based production planning tool driven by a combined build volume packing and scheduling heuristic.

VEDAT (Value Enhancement for Data from Assets & Transactions)

Professor Robert John

Innovate UK

£ 149,401

01/09/2014

31/08/2016

This project (led by Microlise Ltd) focuses on transport & logistics will develop innovations to tackle the challenges of high volumes of complex Big Data generated hourly during "assets and transactions tracking and monitoring" in logistics companies and organisations. Much of this potential “high value” data finds itself locked in vaults/filed or even deleted. Data informatics companies successfully harvest and sell data, either directly back to the owner after a “value adding activity”, or onwards in a variety of niche markets. This project will result in Data Exploration innovative tools and methods of analysis that will bring benefits to data owners, users, operators, supply chain and consumers that will have applications across other sectors with big data challenges involving assets and transactions across finance, high value manufacturing, biotech/informatics, and healthcare.

Speed of Adaptation in Population Genetics and Evolutionary Computation (SAGE)

Dr Per Kristian Lehre

European Commission (FP7-ICT)

€ 1,578,080

01/01/2014

31/12/2016

Our project brings together an interdisciplinary consortium of ambitious researchers from the theory of evolutionary computation and theoretical population genetics to synergise these complementary approaches and to create the foundation of a unified quantitative theory describing the speed of adaptation in both biological and artificial evolution. Read more about this project.

To Improve Homecare Workforce Utilisation by Developing an Adaptable Software Optimisation Engine that Solves Any Workforce Management Scenario that Includes both Rostering and Routing

Dr Dario Landa-Silva EPSRC, TSB, Industry £ 122,159 17/02/2014 16/02/2016

This KTP project seeks to enable Webroster to enhance their software so that customers achieve more efficient workforce utilisation in the provision of high-quality homecare service, a crucial item in the country’s healthcare agenda. The KTP will transfer knowledge and expertise in the development of advanced and innovative computer algorithms for the problem of integrated rostering and routing optimisation. A fully optimised care and logistics software is not available from any of the company’s competitors, yet is consistently requested by major clients (Current systems can only ‘suggest’ solutions, which then require manual intervention).

Energy Efficient Freight Transport Scheduling in Supply Chain Logistics

Dr Rong Qu Royal Society,NSFC £ 11,830 01/04/2013 31/03/2015

In the project we focus on the real life freight transportation scheduling at Ningbo Port, China, the second largest port in the world, and address challenging research issues including real time freight scheduling with uncertain vehicle availability at Ningbo Port, aiming to maximise throughput and minimise cost; and energy efficient optimisation to reduce empty load rate. This project is in collaboration with the University of Nottingham Ningbo Campus (UNNC).

PLATFORM: Towards More Effective Computational Search

Professor Robert John EPSRC £ 1,001,333 22/02/2010 21/02/2015

The ASAP group has set the international research agenda in exploring the development of computational systems that can automatically build decision support systems. The group addresses a broad range of scientifically challenging problems, many of which are drawn from the real world where the complexities of the problem have not been abstracted away in order to make the problem easier to model/solve.The group's key research goals include:- Automating the Heuristic Design Process: We lead the international community in hyper-heuristics (heuristics to choose heuristics) research, with the aim being to investigate the extent to which we can replace human decision making by computer algorithms.- Closing the gap between industrial and real world issues and academic practice: We aim to explore dynamic and complex computational modeling and intelligent decision support within the context of real world problems such as aircraft scheduling, timetabling, manufacturing, bioinformatics, production scheduling and healthcare rostering. ASAP aims to establish new decision support methodologies that explore the use of automated search methodologies and the complexity that they are able to handle.- Closing the gap between theoretical understanding and the construction of search methodologies: We aim to theoretically analyse complex real world scenarios with a view to deepening our understanding of search methodology development. The state of the art in theoretical study in this field tends to deal with models that are too simple to be placed into real world practice. We aim to study the theory of real world applications.Our core research on modeling and search methodologies has redefined the inter-disciplinary interface between Computer Science and Operational Research, while our grounding in diverse applications involves dialogue with many other disciplines spanning biomedical science (new computational methodologies in bioinformatics, systems and synthetic biology as well as in nanoscience) through to the built environment (search methodologies for office space allocation). In this renewal proposal to our current Platform award, we are requesting support for 132 months of research assistant funding (at varying levels of seniority), over a five year period. This would enable us to conduct (and continue) a programme of transformative and innovative research that is not only high risk and high return, but which also has a clear multi-disciplinary and industrial focus.A Platform award would enable the ASAP group to retain key personnel at the interface of Computer Science and Operational Research. The potential benefits in providing the grounding for tomorrow's decision support systems could be far reaching in laying the foundations for more efficient, effective, cheaper, easier-to-implement and easier-to-use systems across many industries and sectors.

The LANCS Initiative in Foundational Operational Research: Building Theory for Practice

Professor Robert John EPSRC £ 1,988,920 03/11/2008 31/05/2014

The United Kingdom is the home of Operational Research (OR) and it maintains an application-oriented research tradition which is both true to its roots and which is also highly distinctive, if not unique. Many industries and public services are the beneficiaries of this effort, not least healthcare, finance, transport and defence. However, the EPSRC/ESRC 2004 International Review of the Research Status of OR in the UK warned that this leading position in applied work in OR could be jeopardised in the absence of a critical mass of researchers developing underpinning theory.

In the LANCS (Lancaster, Nottingham, Cardiff, Southampton) initiative, four universities, which have been at the forefront of UK research in OR, have committed to a major expansion of research capacity in its theoretical foundations, supported by the additional resources available as a result of the current Science and Innovation call. The universities concerned have already worked together in the creation of NATCOR, an EPSRC-supported initiative aimed at strengthening doctoral programmes in the mathematics of OR. They have also evidenced their commitment to the subject by recent decisions (in advance of this call) to invest substantially in it.

To Plan Develop and Implement a Telematics Based Predictive Maintenance System for Commercial Vehicles

Dr Dario Landa-Silva EPSRC, TSB, Industry £ 122,561 01/05/2012 30/04/2014

This KTP project seeks to develop predictive maintenance methodologies based on telematics, modelling and computer algorithms. Currently vehicle manufacturers set a standard service interval of e.g 40,000 miles. However this fails to take into account the ëactualí conditions that vehicles have operated under; some vehicles within the same fleet for example may operate under different conditions yet using the current system receive identical service time which leads to costly unexpected breakdowns. Reducing such incidents is seen as a major goal for both manufactures and hauliers, several of whom are keen to support this project. Knowledge from this project would then allow the company to target their other major telematics markets such as military and construction vehicles. The project tackles a complex, real-world logistics problem that involves data gathering, problem modelling and computer algorithms development. The academic team will work closely with the company to develop a set of tools and methodologies, enabling them to meet their medium term goals.

Target Start-Up Approval Time (TSAT) allocation for London Heathrow

Professor Edmund K. Burke, Dr Jason Atkin NATS £ 45,900 01/01/2007 21/03/2013

This research considers the problem of allocating pushback times to departing aircraft, specifying the time at which they will be given permission to push back from their allocated stand, start their engines, and commence their taxi to the runway. The aim of this research is to first predict the delay (defined as the waiting time at the stand or runway) for each departure, then to use this to calculate a pushback time such that an appropriate amount of the delay is absorbed at the stand, prior to starting the engines. A two-stage approach has been used, where the feasibility of the second stage (pushback time allocation) has to be considered within the first stage (takeoff sequencing). The characteristics of this real-world problem and the differences between it and similar problems have been thoroughly investigated, along with a consideration of the important effects of these differences. Differences include a non-linear objective function with a non-convex component; the integration of two sequence dependent separation problems; separations that can vary over time; and time-slot extensions. Each of these factors has contributed to the design of the solution algorithm. Significant fuel burn benefits were predicted from absorbing some of the delay as stand hold, as well as delay benefits from indirectly aiding the runway controllers by reducing runway queue sizes. The algorithms which resulted from this research were incorporated into a system for Heathrow which was developed by NATS (formerly National Air Traffic Services).

Next Generation Decision Support: Automating the Heuristic Design Process

Professor Sanja Petrovic EPSRC £ 2,666,765 01/10/2006 31/03/2012

Over the last twenty years or so, there has been significant scientific progress in building search methodologies and in tailoring those methodologies (usually through hybridisation with problem specific methods and information) for a very wide range of application areas. Such methodologies can be extremely effective in the hands of an expert but they require specialist human knowledge to be applied effectively in complex real world problem solving environments. The goal of developing automated systems to replace the human expert in this role is only just beginning to be seriously addressed by the scientific community, and the Automated Scheduling, Optimisation and Planning (ASAP) research group at Nottingham has played a pioneering role in placing this grand challenge upon the international scientific agenda. The aim of developing automated systems to intelligently select, evolve and develop search methods is an extremely ambitious and demanding research goal. The level of adventure should not be underestimated. The goal of exploring the boundaries between what is possible and what is not (with respect to the automation of the heuristic design process) represents one of the most important current research challenges to face the search and decision support community. Indeed, our aim is to build systems that can automatically create novel decision support software, thus substantially changing the research agenda and raising the level of generality and applicability of decision support systems.

See the project page

To Design, Develop and Implement Modern Heuristic Algorithms for Improved, Adaptive Carrier Management and Strategic Scheduling

Dr Dario Landa-Silva TSB, Industry £ 124,682 02/01/2010 03/01/2012

This KTP project has been a challenging and exciting experience in several aspects. Besides applying our expertise in modelling and optimisation techniques, we had to carry out research at different stages of the project. We extended our knowledge and expertise. We witnessed the successful implementation of the developed computational algorithms in the company partnerís operations. One of our PhD students is now fully engaged with the company and we are looking forward to continue this exciting road towards the full realisation of transport logistics optimisation.

Nationally Taught Course Centre in Operational Research - NATCOR

Professor K.D. Glazebrook EPSRC £ 241,052 01/10/2006 30/09/2011

NATCOR is a collaboration between ten universities to develop and deliver taught courses in Operational Research (OR) to PhD students. The initiative to develop such taught course provision came from the UK Engineering and Physical Sciences Research Council (EPSRC).

To Develop Next Generation Rostering Software Using Advanced Scheduling Techniques

Dr Dario Landa-Silva TSB, Industry £ 111,992 15/02/2009 14/02/2011

The KTP proved to be an effective scheme to achieve commercial impact of our expertise and research on automated decision support and modelling/optimisation techniques. The KTP was an ideal mechanism for helping the company partner to incorporate automated workforce planning and scheduling into their existing software products for the benefit of UK industry. We established a solid link between our research and software development at the company partner, to incorporate automated workforce rostering, while also motivating new exciting ideas for our further research.

An Investigation into Info Biotics

Dr Natalio Krasnogor EPSRC £ 515,565 11/09/2007 10/09/2010

This proposal aims to seek a fundamental rethink into the following issues:
i: What combinations of formal informatics, evolutionary and learning paradigms and biochemical insights are needed for a successful development of InfoBiotics as a principled approach to Artificial Cellular Life research?
ii. What is the balance of each of the former that is needed in order to ask and, be able to, answer scientifically relevant and meaningful Alife questions from an InfoBiotics perspective?
Specific objectives towards addressing these issues are:
The investgation, implementation and testing of (a) new generic (semi) Formal Artificial Cellular Life framework based on "membrane computing", (b) graphical and robust simulation environment for Artificial Cellular Life models based on the chosen formalism, (c) extended membrane systems that include evolution and learning by means of Learning Classifier Systems and (d) testing InfoBiotics as realised by the integration of (a), (b) and (c) above on a scenario inspired from bacterial colony cross-talk

Novel Approaches to Radiotherapy Planning and Scheduling in the NHS

Professor Sanja Petrovic EPSRC £ 268,315 01/11/2005 30/06/2010

The problem of efficient radiotherapy planning and resource management In oncology departments, In terms of both manpower and the availability of equipment, has been recognised as a key to their smooth running. The various activities, starting from patient referral through to the delivery of the appropriate treatment, form a complex system, for which generating a high quality planning and scheduling solution is a challenging real-world problem that significantly impacts on healthcare staff and patients. This ambitious research proposal concerns both the generation of possible radiotherapy treatments, for patients and the scheduling of resources. This is a joint research proposal between two research groups from the University of Nottingham and Coventry University with expertise from differing but complementary disciplines. Two large hospitals, Nottingham City Hospital and the UHCW NHS Trust in Coventry, which are both providing radiotherapy treatment to a large population throughout their respective regions, are acting as collaborators on the project. They will provide real-world data and expertise in the domain of radiotherapy treatment. The proposed research requires a multidisciplinary effort, aiming at combining different operational research and artificial intelligence disciplines within a complex real-world medical environment. A successful outcome to the proposed research would significantly improve the efficiency and the quality of radiotherapy treatment in the UK. It could lead to a reduction of waiting time and waiting lists for treatments, a reduction of stress levels in patients and improved consistency in terms of dose delivery. Most Important of all, it has a definite potential to increase the survival rate of cancer patients.

See the project page

More Effective Multi-objective Meta-Heuristics to Solve Complex Combinatorial Problems

Dr Dario Landa-Silva EPSRC £ 204,877 01/06/2007 31/05/2010

The main aim of this research project is to explore a number of novel and challenging strategies for the design of more effective multi-objective meta-heuristics to tackle complex multi-objective combinatorial problems. This research programme will build on the state of the art multi-objective combinatorial research carried out by the ASAP research group and other researchers in the field. This project will investigate a significant shift to the principles for designing multi-objective meta-heuristics

Regulatory Decision Making

Professor Graham Kendall EPSRC £ 222,411 02/10/2006 01/10/2009

In this proposal we will investigate if we can simulate regulatory group decision making utilising an environment of cooperating and automated decision makers. This ambitious project comprises a multi-disciplinary, inter-institutional team drawn from Computer Science, Psychology and Industrial and Manufacturing Science. The four investigators will be supported by a three year PhD student, based at Cranfield, and a two year Nottingham based research assistant. The first phase of the project will define the regulatory decision contexts (environmental planning, permitting, policy development), individual roles and personality influences. These factors will be incorporated in the simulation environment in the second phase of the project and the resulting system will be analysed in the final phase. The second phase of the project will take the outputs from phase one and create a simulation environment. This environment will initially be built using agent based technology, but other machine learning approaches will be investigated as appropriate. The final phase will involve all members of the team in analysing the resulting system and calibrating its parameters in order to emulate group decision making processes as closely as possible. A key feature of this proposal are 2-day workshops at nine monthly intervals in order for the whole team (investigators, PhD student, RA and project partners) to work together in a focused way.

An Investigation of the Role of Genetic Programming in a Hyper Heuristic Framework

Professor Edmund K. Burke EPSRC £ 227,675 01/10/2005 7/10/2009

This adventurous proposal carried out an innovative and ambitious inter-institutional research programme to explore a series of novel and timely themes within hyper-heuristic development and intelligent reasoning. Recent advances (supported by EPSRC) have demonstrated the potential for success in developing hyper-heuristics (heuristics to choose heuristics, i.e., methods that can develop problem solvers automatically). This research theme is motivated by the goal of developing systems that are fundamentally more general than current technology can support. In this project we investigated the promising role of Genetic Programming within this emerging area of intelligent systems development. Genetic Programming is a set of techniques that can automatically develop solutions to problems in the form of computer programs. It does so, by using methods that are inspired by natural evolution. In the project we investigated and developed hyper-heuristic systems that can evolve programs that can then be used as problem solvers for a particular problem or class of problems. We explored this approach to problem solving across a diverse range of real world application domains including bin-packing, satisfiability, TSP, timetabling, scheduling and financial forecasting. In all these domains our hyper-heuristics produced solvers that are competitive, and, in fact, in many cases superior to state-of-theart human-designed heuristics. A great deal has been learnt in this exploration. We have, for example, been able to formalise the proposed methodology into a series of clearly defined steps, which makes it possible for our beneficiaries to now extend the approach to other domains of application. Furthermore, during the project we have been able to develop a theoretical understanding of the conditions under which a hyper-heuristic approach (whether driven by genetic programming or by some other search technique) can be superior to other techniques, proving mathematically that hyperheuristics can beat a famous theoretical limit for search algorithms known as the No-Free Lunch theorem. Moreover, we have recently developed a prototype system to demonstrate hyper-heuristic evolution of heuristics for packing problems.

Adaptive Multi-objective Heuristic and Meta-heuristic Approaches to Space Allocation

Professor Edmund K. Burke EPSRC £ 205,378 08/04/2005 07/04/2009

The effective allocation of office and teaching space in any large institution or organisation is often difficult, as a number of constraints, ranging from institutional norms to personal preferences, usually have to be taken into account. In the UK higher education sector alone, space is becoming an increasingly high profile issue as surveys have often shown that teaching space is significantly under-used. Rooms might only be in use 70% of the time, and when in use are often only half full. The overall objective of this project is to develop software tools to aid managers to make better use of existing space, and to plan new space so as to obtain higher utilisation. Work will focus on:
Heuristics and Hyperheuristics. Optimising the usage of space within large institutions will inevitably require heuristic search methods. We aim to develop appropriate heuristics for space allocation, and enhance their effectiveness by also developing general-purpose hyperheuristics.
Multi-Criteria Decision Making methods. Making best space usage is not the only goal, but decisions also need to take account of many other criteria, and make a good tradeoff between them.
The work will occur in close liaison with Barry McCollum and Paul McMullan both from the Department of Computer Science Queenís University of Belfast and also of Realtime Solutions Ltd . In particular, we will be developing a suite of problem instances based on real problems supplied via Realtime Solutions Ltd .
Of course, it is not only in higher education that space allocation is a major management issue. Many of the issues in higher education space allocation will transfer over to space allocation problems in a variety of commercial and industrial organisations.

NETWORK: Interdisciplinary Cutting, Packing and Space Allocation

Professor Graham Kendall EPSRC £ 63,212 01/03/2006 28/02/2009

This proposal seeks the funds to establish a UK network in the scientifically and industrially challenging area of cutting, packing and space allocation. It aims to provide a new national foundation and infrastructure to support major interdisciplinary and inter-institutional approaches for the modelling, optimisation, analysis, implementation and understanding of cutting, packing and space allocation methodologies throughout the industrial, commercial and service sectors so as to underpin decision support system development in these sectors. One of the main aims of the network is establish a dialogue between academia and the industrial sector in order to inform the service sectors of the work that is being carried out within academia and bring to their attention the opportunities that exist for them to work with academic researchers (for example, Knowledge Transfer Partnerships, CASE awards etc.) Of course, we will also encourage inter-institutional, interdisciplinary blue skies, adventerous research and this network will enable researchers to collaborate and develop their research ideas.

IDEAS Factory - Chemical Craftwork: Evolvable CHELLware

Dr Natalio Krasnogor EPSRC £ 77,658 01/10/2005 30/09/2008

Darwinian evolution by natural selection has been adopted by living systems as a robust solution to the problems of surviving in and adapting to a changing environment. In other fields computer algorithms which mimic this evolutionary strategy are finding many applications; particularly in electronic engineering, where field programmable gate arrays can be "constructed" by evolutionary programs to perform complicated tasks. This approach to electronic circuit design is known as Evolvable Hardware. In EHW an electronic circuit can change, adapt and reconfigure its own hardware structure in response to environmental changes (e.g. malfunctions, disconnections, modifications of functional requirements, etc.). Our proposal is based on the analogous idea of using evolutionary algorithms to develop chemical functionality in arrays of "programable" chemical reactors, based on current lab-on-a-chip and electrochemical cells. In the future we hope to apply these methods to complex reactors built in artificial vesicles which communicate by chemical signals much like a living cell.

Symposium on Computational Intelligence and Games

Professor Graham Kendall IEEE £ 3,880 01/07/2005 30/06/2006

More information on request.

Automated, Grid-Aware, Three-Tier Protocol for Protein Structure Comparison

Dr Natalio Krasnogor BBSRC £ 66,314 01/02/2005 31/06/2007

Researchers interested in analysing and understanding proteins' sequences, structures and functions have more than 30 genomes at their fingertips (eg. visit NCBI). The comparison of protein structures, and their clustering (according to similarity) is a fundamental aspect of today's biomedical research. The comparison of the 3D structures of protein molecules is a challenging problem. The search for effective solution techniques for this problem is justified because such tools can aid scientists in the development of procedures for drug design, in the identification of new types of protein architecture, in the organization of the known universe of protein structures. They also can help to discover unexpected evolutionary and functional inter-relations between proteins and it could impact upon structure prediction and the methodologies for the evaluation of those predictions.
In this project we are undertaking the implementation of an extended (three-tier) protocol for protein structure comparison building on our recent research progress. The new software will be grid-aware, publicly accessible and will have both an "intuitive" visual interface and also a powerful programmatic application interface (API). It will extend the two-tier protocol described by integrating the Lagrangian Relaxation method for Maximum Contact Map Overlaps and metaheuristics methods for that model. The third layer of the proposed protocol will "harvest" publicly available protein comparison services and will integrate the results of the initial two layers with those harvested from existing software and databases.

Robust Prediction with Explanatory Power for Protein Structure and Related Prediction Problems

Dr Natalio Krasnogor EPSRC £ 209,589 01/02/2005 31/01/2008

This proposal aims to carry out an innovative and ambitious research programme to explore a series of novel and timely themes at the interface of various computer science traditions, with an impact on bioinformatics. Recent advances have demonstrated the potential for success in developing ever more general, intelligent and reliable classification and predictive technologies. We aim to explore and investigate the feasibility of designing and implementing robust classification and predictive systems that can deliver high quality predictions at the same time as human-understandable explanations for those predictions. The problem domain will be bioinformatics. A successful outcome to this challenging proposal could lead to a greater understanding of the issues that underpin predictive and classification software systems in general, and perhaps more importantly, those that have an immediate impact on quality of human life: bioinformatics. It is in domains like this where the availability of human-understandable explanations are as important as correct predictions. We propose to decompose the Protein Structure Prediction into a number of simpler problems and to tackle each one of these with a robust machine learning technique known as a Learning Classifier System (LCS). State-of-the-art LCSs can yield robust, accurate predictions, with the explanatory power not available in other methods. The methodology used to design representation and operators for the LCS will draw on past experience with cascade correlation neural networks (CCN). The contention of this proposal is that breaking the Protein Structure Prediction into these smaller problems, and providing a robust means of finding predictions with explanatory power, will yield information that will be difficult (if not impossible) to obtain with other methods and, ultimately, could lead to better holistic, i.e. re-constructing, approaches for structure prediction.

Models and Algorithms for Complex Scheduling problems

Professor Edmund K. Burke FUNDING BODY £ 21,240 01/10/2004 30/09/2009

More information on request.

Decision Support for the Textile and Leather Industries - A HEROBC innovation and Regional Fellowship (HIRF)

Professor Edmund K. Burke HIRF £ 12,330 01/04/2004 30/09/2005

More information on request.

Hybrid Metaheuristic Optimisation of Chiral Catalysts

J. Hirst EPSRC £ 220,227 01/04/2004 30/9/2007

More information on request.

Commercialisation of Internationally Leading Cutting and Packing Technologies (NIRA)

Professor Edmund K. Burke Nottingham Innovation and Regional Award £ 6,000 01/04/2004 30/09/2005

More information on request.

Prisoner Dilemma Competition

Professor Graham Kendall EPSRC £ 11,848 01/04/2004 30/109/2005

More information on request.

An Investigation of Cutting/Packing and Planning using Automated Algorithm Selection

Professor Graham Kendall EPSRC £ 153,670 02/02/2004 01/02/2007

To date, an effective NFP algorithm has eluded researchers thus making this effective tool unavailable for general use (both academic and commercial). The no fit polygon (NFP) is a powerful, geometric concept that has the potential to allow advances in many domains. This proposal, initially, aims to realise a robust algorithm(s) for the NFP. This is high risk, adventurous research yet, if it can be achieved it opens up many research directions which have not been possible before now. Once robust algorithm(s) have beer, developed we ::!!! investigate he,.-; they can be used !n the context of two domains. However, we will not simply apply the algorithm to the two domains. We will investigate how, when presented with a given problem instance, the selection of the best NFP algorithm is automated in order to solve that problem. Indeed, the approach we develop could select different NFP algorithms, to solve a single problem instance as the nature of the problem will change during the course of search. If this program of research is successful, not only would it present the research community with a robust algorithm for the first time but it will also present a framework that will automate the selection process when a user is presented with a problem they are asked to solve. In order to achieve this we will define a typology for NFP oroblems/aloorithms and use this tvooloav to choose which algorithm to aoolv for the particular ooint in the search space

An Investigation of Cutting/Packing and Planning (EPSRC)

Professor Graham Kendall EPSRC £ 153,670 02/02/2004 01/02/2007

To date, an effective NFP algorithm has eluded researchers thus making this effective tool unavailable for general use (both academic and commercial). The no fit polygon (NFP) is a powerful, geometric concept that has the potential to allow advances in many domains. This proposal, initially, aims to realise a robust algorithm(s) for the NFP. This is high risk, adventurous research yet, if it can be achieved it opens up many research directions which have not been possible before now. Once robust algorithm(s) have beer, developed we ::!!! investigate he,.-; they can be used !n the context of two domains. However, we will not simply apply the algorithm to the two domains. We will investigate how, when presented with a given problem instance, the selection of the best NFP algorithm is automated in order to solve that problem. Indeed, the approach we develop could select different NFP algorithms, to solve a single problem instance as the nature of the problem will change during the course of search. If this program of research is successful, not only would it present the research community with a robust algorithm for the first time but it will also present a framework that will automate the selection process when a user is presented with a problem they are asked to solve. In order to achieve this we will define a typology for NFP problems/algorithms and use this tvooloav to choose which algorithm to aoolv for the particular ooint in the search space.

PLATFORM: Towards More General Optimisation/Search System

Professor Edmund K. Burke EPSRC £ 422,908 01/02/2004 31/05/2009

This far-reaching Platform Grant proposal aims to underpin the broad multi-disciplinary research remit of the Automated Scheduling, Optimisation and Planning (ASAP) Group at the University of Nottingham. It will focus upon investigating and developing a fundamentally more general and adaptive search/optimisation methodology than exists today. This goal represents one of the key research strategies that is currently facing the international optimisation community. The level of adventure should not be underestimated. This is an ambitious aim that would have significant impact on decision support system development and its deployment across a wide range of diverse applications and industries. This overall goal currently lies across several research council funded projects that are held by the ASAP group. A critical element in being able to effectively tackle this exciting and challenging aim is the retention of key research staff who have spent several years working in this area and towards this goal. The level of expertise that is represented by these staff is, quite simply, irreplaceable. This Platform Grant would provide the ASAP group with the means to retain these staff and provide the foundation for its medium to long term research strategy.

Novel Metaheuristics Research Directions in Healthcare Personnel Rostering

Professor Edmund K. Burke EPSRC £ 191,581 01/10/2003 31/03/2007

This ambitious research programme aims to cut across the disciplinary boundaries of Operational Research and Artificial Intelligence and carry out an innovative and timely research initiative in healthcare personnel rostering. This project will explore exciting avenues of research that have recently opened up due to significant advances in scheduling/timetabling technology that have been made by the proposers and others. A key feature of this proposal is to explore adventurous and demanding research challenges in a critically important real world problem area. The project will tackle a range of personnel rostering/scheduling problems across the healthcare sector. Success in this project would not only have an impact on the international scheduling community but it could also have a major impact upon how hospitals are administered and upon the working lives of doctors, nurses and clinicians. It could help to alleviate the current shortage of doctors and nurses that is facing the UK. The project team includes a scientific group from Belgium, a consultancy company from Holland and a software development company from the UK. The team represents the blend of expertise and experience that is required to make significant scientific progress in this notoriously challenging problem area. If successful, the project could yield a much deeper understanding of adaptive real world personnel scheduling systems and of the issues that underpin the development of such systems.

Hybrid Metaheuristic Solutions for Runway Scheduling

Professor Edmund K. Burke EPSRC,NATS £ 40,000 01/10/2003 30/9/2006

Heathrow airport is one of the busiest airports in the world. Constraints to minimise noise to nearby villages mean that at the moment only one runway can be used for departures at any time. It is therefore vital to maximise the throughput of this departure runway.
For reasons of safety it is necessary to provide a safe separation between departing aircraft. This separation depends upon the relative weights of the aircraft and the relative directions of departure. By changing the departure order it is often possible to reduce the total separations required and therefore increase the throughput.
Deparatures are frequent and the controller's work load is high. It is often not possible for a controller to consider all possible orders of the aircraft so an advisory tool would be useful. However even an advisory tool will not always have the time to consider all possible orderings.
This project investigates the possible orders of departure using metaheuristics to examine the search space for good, although not necessarily optimal, orders to increase the throughput of the runway without reducing the safety.

Schedluing Agents for Distributed Timetabling and Rostering

Professor Graham Kendall EPSRC £ 10,350 20/06/2003 19/04/2004

More information on request.

Optimisation and Search Methdology Tutorials

Professor Edmund K. Burke EPSRCLMS £ 5,000 01/02/2003 30/09/2003

More information on request.

Fuzzy Multicriteria Approaches to Scheduling and Rescheduling Problems in Uncertain Environments

Professor Sanja Petrovic EPSRC £ 211,594 01/01/2003 30/09/2006

The main aim of this research is to propose a new methodology for developing automated production scheduling systems using multiple scheduling criteria, in the presence of uncertainty. Scheduling problems will be modelled as decision analysis problems under uncertainty and, consequently, scheduling experts will be given a more important and active role than in classical approaches. The key objectives of the research are:
1. To identify and analyse sources of uncertainty, which are inherent in real-world production scheduling problems, including both parameters and constraints. The identified uncertainties will be formalised using fuzzy logic-based techniques.
2. To propose a suitable framework for the design and development of scheduling models for complex production environments. This will involve: (a) investigation of measures of fuzzy constraint satisfaction, and (b) modelling the preference structure of the schedulers. Based on these, two new types of models will be developed that include the uncertainties identified in 1.) and make compromise solutions across multiple criteria that describe different schedule performance measures, taking into consideration the preferences of the scheduling experts, namely (c) fuzzy multicriteria models based on dispatching rules, and (d) fuzzy multicriteria meta-heuristics for production scheduling. A successful outcome of the modelling effort will result in a tool, which is usable in real-world scheduling environments. In addition, we are aware of the problem of interfacing to a Computer Aided Manufacturing (CAM) platform in order to collect real world data and will address this issue as a feature of the framework.
3. To extend the scheduling framework developed in 2.) with rescheduling models. This will involve: (a) identification of various types of disruptions and uncertainty that can affect a production schedule, (b) development of new rescheduling methods which take into consideration identified disruptions and related uncertainties and use multiple criteria for new schedule construction, based on measures of performance and measures of reschedule stability, and (c) studying the effects of various disruption scenarios on the rescheduling performance measures.
4. To perform sensitivity analysis in order to provide a better understanding of the scheduling models and requirements in different scheduling situations. The sensitivity analysis will be carried out in two directions: (a) investigating how changes to uncertainty in parameters and constraints employed in the developed models affect the schedules; (b) evaluating the sensitivity of schedules to changes of scheduler's preferences toward the performance measures used to evaluate schedules.

See the project page

Using Real Time Information for Effective Dynamic Scheduling

Peter Cowling EPSRC £ 48,939 12/11/2002 11/06/2004

Effective scheduling is essential for achieving performance goals in most sectors of industry and commerce. Scheduling is also an important multidisciplinary research area for Computer Science, Operational Research (OR) and Psychology which has generated a wealth of theoretical results and yielded enhanced operating performance for a considerable number of industrial and commercial enterprises. However, there are significant barriers to the application of scheduling theory to the dynamic, uncertain scheduling environments which are encountered in practice. Many production systems now have the ability to capture data in real-time but few are able to use this data to influence scheduling decisions in real-time. The proposed research will investigate, from a fundamental mathematical perspective, how real-time information may be used to improve the performance and applicability of scheduling models, algorithms and heuristics. We argue that it is possible to make OR techniques more effective and efficient for solving dynamic scheduling problems by using real-time information. Recently, agent technology has been considered as an important approach for developing industrial distributed systems. The problem of dynamic scheduling is one that is receiving increasing attention amongst both researchers and practitioners. From an emphasis on scheduling optimality in the narrow sense provided by a mathematical model in the past, the focus has lately moved to scheduling flexibility and robustness. More researchers have begun to try solving the complex dynamic scheduling problems in a distributed way using the Multi-Agent paradigm. The Multi-Agent paradigm represents one of the most promising approaches to building complex, flexible, and cost-effective scheduling systems because of its distributed and dynamic nature. The overall aim of the project is to investigate how real-time information can be used to improve the design, performance and applicability of a wide range of scheduling models using Multi-agents. The application we are interested in is Steel Making Production.

DNA Mapping by Combinatorial Optimisation

Professor Edmund K. Burke EPSRC £ 10,224 01/09/2003 31/05/2007

More information on request.

A Dual Examination of Scheduling Problems

Professor Sanja Petrovic EPSRC £ 7,800 02/09/2002 01/08/2003

More information on request.

Investigation of Novel Methods to Optimise Shelf Space Allocation

Professor Graham Kendall EPSRC £ 62,947 31/07/2002 31/07/2005

We plan to investigate and further develop recent advances in heuristic optimisation techniques to produce good quality shelf layouts (also called planograms). Specifically, the objectives are to 1. Investigate modelling issues in formulating a shelf layout and develop appropriate models. The models will be capable of being optimised by exact techniques (e.g. linear programming, graph theory etc.) and AI techniques (e.g. genetic algorithms, ant algorithms, evolutionary strategies, multi-objective approaches etc.) 2. Investigate and develop operational research and artificial intelligence techniques to optimise the model developed in 1. The range of techniques we will consider will include initialisation strategies (so that we start searching from reasonable solutions), decomposition (to break the larger problem into sub-problems which may be easier to solve), case based reasoning (both as an initialisation strategy and as a method in its own right) and hybridisation (to combine two (or more) different algorithms). 3. Implement a prototype system for the next generation of planograms. These will produce planograms of higher quality than is currently available, using less time and labour than current methods. 4. Evaluate and assess the model on a range of real problems from the retail sector.

Meta-Heuristic Protein Folding

J. Hirst FUNDING BODY £ 134,844 20/08/2001 28/02/2005

This project, in collaboration with Dr. Jonathan Hirst of the School of Chemistry at the University of Nottingham involves the development of novel metaheuristic optimisation techniques from Computer Science and application to determining the structure and function of protein chains. Recent successes in complex optimisation problems suggest that established methods (such as genetic algorithms, tabu search, simulated annealing) and emerging approaches (eg ant algorithms, case-based reasoning and variable neighbourhood search) warrant investigation in Bioinformatics. We will conduct extensive studies of simplified problems, so that the approaches can be developed, studied and appropriately hybridised, prior to application to real problems, where lack of data and noise can obscure algorithmic deficiencies. We propose then to apply the hybrid meta-heuristic approach to real problems, including protein sequence design and ab initio folding.

Inter disciplinary Scheduling Network

Professor Edmund K. Burke EPSRC £ 62,985 01/05/2001 30/04/2004

This network aims to provide a national foundation and infrastructure to support major new interdisciplinary and inter-institutional approaches for the modelling, optimisation, analysis, implementation and understanding of scheduling decision support systems throughout the industrial, commercial and service sectors so as to enable software vendors to match the needs of these sectors.

An Investigation of Hyper-Heuristic Methods

Professor Edmund K. Burke EPSRC £ 196,343 18/12/2000 17/06/2004

Over the last 40 years or so, many novel computer algorithms in areas such as data-mining, cutting, packing, scheduling and other optimisation applications have been developed. Many fail to have any significant impact in practice as they are too knowledge-intensive or too complicated for most potential users. Often users continue to employ simple heuristic methods such as `largest-first first-fit' or `most-difficult-first' algorithms. Such methods may be relatively straightforward to implement, but individual heuristics do not always perform very well on all problems. There is a serious conflict between using cheap but fragile heuristics and using knowledge-intensive methods that can perform very well but are hard to build and maintain. This proposal concerns hyper-heuristics. In essence, hyper-heuristics are heuristics to choose heuristics. This differs from the widely-used term meta-heuristic, which refers to heuristics which control simpler heuristics for a narrow range of problems, rather than the hyper-heuristic approach of choosing between a range of heuristic approaches to robustly solve a wide range of problems.
The aim of this project is to investigate the application of Hyper-Heuristic methods to wide range of scheduling and planning problems. This is a joint project in association with Napier University, Edinburgh.
As part of this project we have developed a Case-Based Heuristic Selection System . We are also developing prototype choice function and tabu search hyperheuristics. These prototypes will also be made available on these pages.

Representational design principles to humanise automated scheduling systems

P. Cheng ESRC £ 264,100 01/12/2000 31/03/2004

Two primary aims of the project are:
To develop generic principles of external representation aimed to facilitate user comprehension, decision-making and the capacity for problem solving;
To develop methods for raising the level of generality of the scheduling search process by providing the user with a rich palette of heuristics to produce and capture a range of human-controlled hyper heuristics;

Case Based Reasoning Personnel Rostering

Professor Sanja Petrovic EPSRC £ 58,684 01/12/2000 31/08/2004
More information on request.

New Approaches to Produce Efficent Nesting Patterns (TCS)

Professor Edmund K. Burke FUNDING BODY £ 126,668 01/10/2000 30/09/2003

More information on request.

Developing Heuristics and Algorithms for the Irregular Stock Cutting Problem

Professor Edmund K. Burke Esprit Automation,EPSRC £ 28,920 01/10/2000 30/09/2003

The main objective is to develop better solutions to the irregular shape stock cutting problem. This will involve the integration of modern heuristic and metaheuristic methods into Esprit Automation's existing in-house software. There are several factors that may determine the quality of a solution: time to obtain solution, minimisation of waste, multi-head cutting capability. We intend to implement a wide range of possible methods that may be used to obtain high quality solutions such as: genetic algorithms, simulated annealing, tabu search. The secondary aim is to provide the user with a simpler interface to the solution search. This will allow use of the software without the need to supply which type of search to execute and its associated parameters (with, perhaps, the exception of the time / quality trade-off found with all search methods). The decision of which search method to use given any particular problem may include case-based analysis of previous and similar problems and an implementation of hyperheuristic methods.

An Investigation of Case-based Heuristic selection for University Timetabling

Professor Edmund K. Burke EPSRC £ 190,545 27/03/2000 26/10/2003

Creating an educational timetable (be it an exam or a lecture/classroom schedule) has always been considered to be a difficult and problematic task. Research has been carried out on methods and approaches to this problem since the advent of computer technology
The aim of this project is to investigate the possibilities and potential advantages of applying case-based reasoning (CBR) to choosing meta-heuristic and heuristic methods for solving a range of university timetabling problems including course and examination timetabling.
Over the course of this project we have carried out a varied program of research exploring case based reasoning as a heuristic selection process across university examination and course timetabling. Our work has resulted in a far better understanding of case based reasoning and its role in automated timetabling as well as many of the meta-heuristic techniques applied to the problems. In particular, we have:
1) Successfully investigated Meta-heuristic, heuristic and hybrid methods for university timetabling.
2) Deepened our understanding of similarity measures for heuristic selection.
3) Developed a case based reasoning methodology to appropriately select heuristics/meta-heuristics for university timetabling.
4) Implemented a prototype case based system for heuristic selection.
5) Built a critical mass of work in the broad area of case based heuristic selection. Publications directly resulting from this project can be found here.
6) Developed proposals for future work to build on the findings of this project

ASAP Research Group

The University of Nottingham
School of Computer Science
Jubilee Campus
Wollaton Road
Nottingham, NG8 1BB


telephone: +44 (0) 115 8466543
email: asapgroup@nottingham.ac.uk