Completed Projects

Hyper-heuristics for Routing                                                                                                     

£207,627         

To support Optrak to develop and implement novel and advanced hyper-heuristics based routing technologies for standard and non-standard haulage markets.

OptiMACS - European industrial doctorate for efficient multidisciplinary design Optimization of Multifunctional Aerospace Composite Structures                                                                                                     

€1.3M         

Modern aeronautical structures are increasingly made of composite materials due to their well-known benefits. Optimizing the design of aerospace composites vis-à-vis the entire range of operational constraints (i.e. reliability, stability, strength, weight, noise, manufacturability and cost) to which the aircraft structures are subject, results in a particularly challenging task for the structural designer. Despite the volume of recent work dedicated to new Multidisciplinary Design Optimization (MDO) models and techniques, the ‘No free lunch theorem in optimisation’ is constantly confirmed.

A genuine need is therefore identified for a programme that will: i) Develop, deliver and implement novel and efficient structural MDO technological tools for the European aerospace industry, ii) Nurture and train the next European generation of MDO research professionals. OptiMACS has an intersectoral character, drawing know-how from both academic and industrial research and innovation teams. It also has an intensely multi-disciplinary character, coupling expertise from mechanical, aerospace, manufacturing and software engineering, as well as from the area of applied mathematics.

On the research side, OptiMACS will focus on improving the accuracy and efficiency of the MDO platform currently employed by AIRBUS. This will be achieved by enhancing the design models and criteria related to composites failure and manufacturing, developing and implementing multiscale models for composites as well as investigating advanced MDO algorithms and architectures for enhancing efficiency.

On the training side, OptiMACS will provide a fully supportive environment for 5 ESRs. A training programme aiming at developing both the research as well as the transferable skills of the Fellows has been designed. All Fellows will have the opportunity to work in a multi-disciplinary environment, spending at least 50% of their time at the premises of the industrial beneficiaries.  

ENIGMA (Supervisor Control for ENhanced electrIcal enerGy Management)                                                                                                 

€826,260 (€272,081 to Nottingham)      

As more and more systems on aircraft become electrical, it becomes increasingly important to optimally control systems in the case of generator failures, to safely manage any overloads. This project developed a supervisory controller to manage other controllers to coordinate the handling of overloads, utilising different sources of stored power along with strategic reduction of power to low priority loads, ensuring safety of aircraft even in extreme situations. By guaranteeing to quickly manage overloads, the over-sizing of generators can be reduced, reducing generator and aircraft weight, and contributing to the move towards greener aviation.

European industrial doctorate for advanced, lightweight and silent, multifunctional composite structures

European Commission (Brussels)

€809.000 

Modern aeronautical structures are increasingly made of composite materials due to their well-known benefits. Despite their superior structural characteristics, composite structures exhibit poor dynamic and acoustic isolation levels compared to conventional metallic ones. As a result and in order to maintain the comfort levels in the passenger and payload compartments within acceptable limits, additional acoustic and vibrational isolation technologies (sound packages) are necessary in several transport applications. If non-optimally designed for a certain application, these sound packages can add substantial weight to the structure, compromising the weight benefits gained by the employment of composites.The aforementioned challenges imply an urgent and genuine need for development of lightweight and multifunctional structures, for modern industrial transport applications. The N2N Training Network aims at developing a high-fidelity and efficient Multidisciplinary Design Optimization (MDO) scheme for multifunctional composites having poroelastic inclusions and combining minimum mass with maximum damping and comfort levels.

On the research side, N2N will focus on developing multiscale models for obtaining a comprehensive description of random poroelastic materials coupled to a composite structural segment. Understanding the interaction of acoustic waves with such complex materials is another scientific challenge that the Network will tackle. N2N aims at developing reliable tools for providing accurate optimal designs for multifunctional composite structures that combine lightweight properties with exceptional acoustic and vibration isolation.

On the training side, N2N will provide a fully supportive environment for 3 ESRs. A training programme aiming at developing both the research as well as the transferable skills of the Fellows has been designed. All Fellows will have the opportunity to work in a multidisciplinary (industrial and academic) research environments.

DEAS: EPSRC Digital Economy: Digitally Enhanced Advanced Services (DEAS) NetworkPlus

University of Exeter (PI)

Robert John/Dario Landa Silva (PI)

Aston University (CI)

Cranfield University (CI)

University of Greenwich (CI)                

£1.3M 

3D point clouds are receiving increased attention due to their potential for many important applications, such as real-time 3D immersive telepresence. 

Data-driven Energy Management Systems

£219,492 

To enable and empower customers to transition from 'passive energy customers' into 'proactive energy customers' by bringing big data science and optimisation into the energy management systems.

Optimized Dynamic Point Cloud Compression

€112,467 

3D point clouds are receiving increased attention due to their potential for many important applications, such as real-time 3D immersive telepresence. Compared to traditional video technology, 3D point cloud systems allow free viewpoint rendering, as well as mixing of natural and synthetic objects. However, this improved user experience comes at the cost of increased storage and bandwidth requirements as point clouds are typically represented by the geometry and colour of millions up to billions of 3D points. For this reason, major efforts are being made to develop efficient point cloud compression schemes. The task, however, is very challenging due to the irregular structure of point clouds. To standardize these efforts, the Moving Picture Experts Group (MPEG) launched in January 2017 a call for proposals for 3D point cloud compression technology. In October 2017, the responses were evaluated and the first test model for lossy compression of dynamic point clouds (TMC2) was established. This test model defines a first “common core” algorithm for collaborative work towards the final standard. The aim of OPT-PCC is to contribute to these efforts by developing algorithms that optimize the rate-distortion performance of the test model.

AI-Driven Secured Connected and Autonomous Vehicles (AI-DRIVEs)

£31,781 

This project assesses machine learning in cyber security of Connected and Autonomous Vehicles (CAVs) with both software and hardware simulation of Vehicle-to-Vehicle (V2V) or Vehicle-to-anything (V2X) communications. The AI-driven solutions sustain a prototype demonstrator to provide Security as Service (SaaS) comply to 5G standard for companies in the automotive sector to take up. The project brings together expertise in connectivity, autonomy and machine learning to develop a fit for purpose prototype that satisfies industry standards in secured V2X connectivity, close to market, and with high trustworthiness among end users.

Multi-objective timetabling with fairness

£149,103 

This KTP project between the University of Nottingham and EventMAP will further our collaborative work in the emerging area of ‘fairness’ measures in timetabling and scheduling. In the case of higher education, introducing the concept of subjective ‘fairness’ into the workings of their products is an important step to improving the overall satisfaction levels of teachers, students and university staff with their day-to-day work. So, for example, those sometimes unavoidable, less-than-ideal compromises in timetables – which timetablers will know as violations of soft constraints – can be distributed in an equitable way amongst affected parties while still maintaining a maximally efficient timetable. It should go without saying that this incorporation of fairness measures into EventMAP's work will greatly increase the value that can be brought to improving student experience and staff satisfaction levels for the academic clients.

Encouraging Lifelong Learning for an Inclusive and Vibrant Europe (ENLIVEN)

£392,000 

This is a project within a consortium of 10 European countries. At the COL Lab, School of Computer Science , the project focuses on knowledge discovery, based on analysing large databases collected from the consortium member countries, to establish knowledge bases within case based reasoning systems for policy making in lifelong learning in Europe. The objectives include to mine knowledge from large amount of data, and to develop intelligent decision support systems to support policy makers throughout the policy making process for adult lifelong learning.

Predictive and Prescriptive Analytics with Optimisation for Business Intelligence

£207,551 

This KTP project seeks to enable PXtech to develop predictive and prescriptive analytics with optimisation capability to maintain their leading industry position as a Business Intelligence Solution provider through the application of advanced data analysis, data mining, machine learning, modelling and optimisation techniques. The project will develop techniques to predict future outcomes in order to prescribe long-term planning that aligns with the market needs. Predictive and prescriptive analytics including optimisation will help a business to discover patterns and develop new models to predict (resulting in deeper insights) and prescribe (resulting in better planning), in order to improve business performance.

OPTIMISED: Operational Planning Tool Interfacing Manufacturing Integrated Simulations with Empirical Data

€196,153 

OPTIMISED is a 10-party, three year, EU-funded consortium project, comprising SME's, large companies and research institutions from across Europe.  The key aims of the project are contained in the full project title: Operational Planning Tool Interfacing Manfacturing Integrated Simulations with Empirical Data. 

OPTIMISED will develop and demonstrate a manufacturing scheduling optimisation system, which uses real-time smart sensors and big data analytics to monitor, react to and improve manufacturing performance.  Within the scope, the impact of energy management on factory planning and optimisation witll be speciaically addressed.

OPTIMISED will use the principles of Measure, Simulate, Optimise.

Automated Intelligent Decision Support Using Hyper-Heuristics

This grant will support a two-year long collaborative research project through exchange of visits with Prof Nelishia Pillay and a PhD student from the School of Mathematics, Statistics and Computer Science at University of KwaZulu-Natal. Intelligent decision support systems are playing an increasingly important role in providing solutions to various computational problems in society, industry, academia and government. However, the design, development and maintenance of heuristic methods underpinning those intelligent decision support systems are extremely challenging, time-consuming and so costly, often requiring human expert intervention. This collaboration aims to study adaptive, effective, generic, reusable and low-cost hyper-heuristics automating the heuristic design process for intelligent decision support, focusing on vehicle routing, packing and timetabling domains.

COSLE (Collaborative Optimisation in a Shared-Logistics Environment)

Dario Landa-Silva (PI)

Robert John (CI)

This project (led by Microlise Ltd) is to develop an innovative service to enable collaboration in a shared freight transport logistics environment. We will bring location data (about where goods, vehicles, senders and consignees are at any time, etc.) and environmental data (weather, traffic, events, etc.) together with GPS, vehicle telematics, optimisation, image processing and mobile technology (including augmented reality). This innovative service will enable a shared distribution concept to reduce freight empty runs and create business opportunities for users at all levels.

Channel 4 Project

An ASAP team is working with Channel 4 (a national TV company) in order to investigate the application of optimisation techniques to the scheduling of commercials during advertising breaks. The objective is to provide schedules that increase advertising effectiveness and lead to greater advertiser satisfaction.

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

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)

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

More information on request.

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

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

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

More information on request.

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

More information on request.

Hybrid Metaheuristic Optimisation of Chiral Catalysts

More information on request.

Commercialisation of Internationally Leading Cutting and Packing Technologies (NIRA)

More information on request.

Prisoner Dilemma Competition

More information on request.

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

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)

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

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

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

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.

Scheduling Agents for Distributed Timetabling and Rostering

More information on request.

Optimisation and Search Methdology Tutorials

More information on request.

Fuzzy Multicriteria Approaches to Scheduling and Rescheduling Problems in Uncertain Environments

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

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

More information on request.

A Dual Examination of Scheduling Problems

More information on request.

Investigation of Novel Methods to Optimise Shelf Space Allocation

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

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

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

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

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

New Approaches to Produce Efficent Nesting Patterns (TCS)

More information on request.

Developing Heuristics and Algorithms for the Irregular Stock Cutting Problem

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

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