asap
University of Nottingham >
School of CS >
a s a p
Group Research Seminars 2011 |
(TBD= To be determined; TBC= To Be Confirmed; TBA = To Be Announced)
Seminars are in room C60 at 11:00 unless announced otherwise.
|
Time: Internal seminars are generally 30mins and held on Thursdays at 11:00 and 11:30. * : Seminars organised by School (for venue and time please follow the link on date). Previous seminars 2007-2008 2006-2007 2005-2006 2004-2005 2003-2004 2002-2003 2001-2002 1999-2000 ABSTRACTS 8 March, 2012, Tim Curtois,ASAP : "Title: TBC" Abstract: TBC 1 March, 2012, Jose Arturo Castillo Salazar,ASAP : "Title: TBC" Abstract: TBC 23 February, 2012, Yuri Bykov,ASAP : "Title: TBC" Abstract: TBC 16 February, 2012, Urszula Neuman,ASAP : "Title: TBC" Abstract: TBC 9 February, 2012, Gabriela Ochoa,ASAP : "Title: TBC" Abstract: TBC 2 February, 2012, Tiago Pais,ASAP : "Title: TBC" Abstract: TBC 26 January, 2012, Daw Khin Thein Lwin (Khin),ASAP : "Title: TBC" Abstract: TBC 19 January, 2012, Dr Alessandro Condotta,Visiting Speaker : "Abstract: This seminar will address scheduling problems in which each " job has multiple operations interleaved by fixed time-lags. Such problems raised a lot of interest in literature due to their computational complexity and since they underlie many practical scheduling problems ranging from multi-function radar to manufacture scheduling. In the first part of the seminar, I will introduce a new scheduling problem with fixed time-lags arising in healthcare and I will show an innovative approach for its solution. Specifically, the problem consists of scheduling treatment appointments in an outpatient chemotherapy clinic. In this special setting, during each appointment, a nurse performs to a patient specific treatment tasks that must be interleaved by fixed time intervals. The solution approach I will describe substantially increases the number of patients that can be treated using available resources. In the second part of the seminar, I will present a tabu-search algorithm for the solution a simplified version of the problem where each job has two operations. In particular, I will show how the short cycle property of the underlying disjunctive graph can be used to design efficient local-search algorithms for the class of scheduling problems with fixed time-lags. Lastly, I will demonstrate a complexity result that excludes the possibility of designing efficient neighbourhood moves fixing the sequence of first operations of the jobs. 12 January, 2012, Mustafa Misir,Visiting Speaker : "Abstract: Selection hyper-heuristics are expressed as " problem-independent approaches to solve different search and optimisation problems. Their problem-independent nature is considered as an opportunity to facilitate generality. For the generality purpose, it is required to design a hyper-heuristic with the ability to manage different heuristic sets in order to profit from their strengths. During this management process, heuristics should be assessed relying on their online performance and other factors such as execution time limit should equally be taken into account. HyFlex is a useful software framework to test the generality of hyper-heuristic approaches across a range of problems using distinct heuristic sets. In this talk, the design principles of an adaptive selection hyper-heuristic (CHeSC 2011 winner) will be discussed from a generality perspective. Then, a detailed empirical analysis on HyFlex will be presented to show both the performance and the adaptive behaviour of the developed approach. 15 December, 2011, Stefan Ravizza,ASAP : "Title: How OR can aid airport ground movement" Abstract: The airport ground movement optimisation problem links other important airport airside operations together and is an area where OR can help practitioners to master many challenging tasks they face. We will discuss two key elements of this problem. Firstly, accurate taxi time prediction is needed in order to estimate the time an aircraft needs to travel on each taxiway. Secondly, a routing and scheduling problem has to be solved to guide aircraft from source to destination locations (usually either runways or gates/stands) in a conflict-free manner. Our taxi time prediction method is based upon multiple linear regression and enables a prediction to be made where the effects of other aircraft are eliminated. This is important since these effects will be considered in the routing algorithm. The decision support system for the routing problem is based on a sequential graph-based algorithm and utilises the taxi time predictions. The results for this combined approach predict a potential improvement in the total taxi time of about 24% for a real-world dataset from Zurich Airport. Importantly, the approach is able to provide routings in real-time and the gap between the delay for the solution which was found and a lower bound was only 2.2%. Exploring different heuristics to find a better aircraft sequence than first-come-first-served resulted in an additional reduction of this gap of about 37% where re-routing was kept to a minimum. 15 December, 2011, Stanislava Armstrong,ASAP : "Title: The Effects of Release Levels and Trajectory Lengths on the " Aircraft Arrival Sequence Abstract: In the literature, the control problem within the stacks and the control problem between the stacks and the runway are not usually considered when the aircraft arrival problem is being tackled. When used at airports like Heathrow, where aircraft are currently released predominantly from the bottom level of each stack, such algorithms could lead to solutions that achieve very good objective function values, but may not always be applicable in practice. The aim of this work is not only to find feasible arrival sequences, but also to investigate the potential benefits which can be achieved at Heathrow if some slight tactical changes are made. In this presentation we will show the impact which varying the number of release levels has on the aircraft arrival sequence. Furthermore, we will consider the effects of extending the lengths of the trajectories from the stack to the runway for some of the aircraft. This will allow the aircraft remaining in the stacks to ladder down faster into the release levels in those cases and as a result a better sequence may become feasible. 08 December, 2011, Anas Elhag,ASAP : "Title: Hyperheuristics for Grouping Problems" Abstract: Many well known combinatorial optimization problems such as Data Clustering, Exam Timetabling, and Graph Colouring are classified as Grouping Problems since they all share the common general task of attempting to partition a set of objects U into a collection of mutually disjoint subsets ui of U such that each object is in exactly one subset. Each one of these problems has been tackled individually, and many problem-specific solutions are available in the literature. Hyper-heuristics is an emerging solution methodology which attracted massive research attention in the last few years. Hyper-heuristics aim at raising the level of generality at which optimisation systems can operate and to produce optimization systems that are applicable across problem domains and able to find good-enough, soon-enough, cheap-enough" solutions to as many optimization problems as possible. The objective of this research is to study the applicability of Hyper-heuristics on Grouping Problems and how they can be used to improve the best solutions found so far for these problems in the literature. In this presentation, a review about Grouping Problems is provided identifying their main solution representations such as the LLE and the GGA representations, the multi-objective nature of most of them as well as other key challenges. Also, some multi-objective hyper-heuristic frameworks - which are currently being tested using a recently-proposed grouping solution representation known as the Linear Linkage Encoding LLE" - are shown, together with the future possibilities for extending and improving them. 08 December, 2011, Monica Banerjea,ASAP : "Title: Application of two hyper-heuristics to different problem domains" Abstract: In this presentation we will overview the application of two hyper-heuristics developed for personnel scheduling problems to other domains included in the hyper-heuristic framework HyFlex. We have applied the hyper-heuristics to one dimensional bin packing problems, permutation flow shop problems and the Boolean satisfiability problems 24 November, 2011, Ahmed Kheiri,ASAP : "Title: A Dominance based Hyper-heuristic" Abstract: Hyper-heuristics represent a class of search methodologies which explore the space of heuristics rather than the space of solutions, directly. Recently, hyper-heuristic tools have been implemented and made publicly available to support rapid development and research, such as HyFlex and Hyperion. HyFlex, currently, provides implementation of six problem domains along with the relevant low level heuristics for each domain. We propose a dominance based hyper-heuristic which is motivated by the idea of dynamically grouping the low level heuristics that are expected to perform relatively well into a list of active heuristics. This hyper-heuristic is implemented as an extension to HyFlex and the empirical results indicate that the approach is successful performing better than some previously proposed hyper-heuristics. 24 November, 2011, Amadeo Asco,ASAP : "Title: Constructive Algorithms Analysis and Genetic Algorithm for the" Over-constraint Airport Baggage Sorting Station Allocation Problem Abstract: Better assignments of airport resources can improve the quality of service which airlines and airports provide, help them to keep to published schedules, reducing service disruptions and minimising changes or delays due to lack of resource availability. We consider the assignment of baggage sorting stations to flights which have already been scheduled and assigned to gates. We modelled the problem and discuss the results, in terms of various different objectives, of applying different constructive algorithms to the problem. A Genetic Algorithm was also implemented for the problem and we evaluate the effect of providing good initial solutions against randomly generated solutions. Experimental results indicate that our developed GA provides better solutions than various other metaheuristic methods which were tested, and also better than Gurobi was able to achieve within 24 hours. 15 November, 2011, Jakub Marecek,ASAP : "Title: Recent Trends in Convex Programming, with Applications" Abstract: There is a rich history of research in convex programming, going back at least to Lagrange. Perhaps surprisingly, though, there has also been a considerable progress in the past five years. Newly developed methods allow for the solution of instances with millions of variables. Thousands of practical applications have changed a number of fields in Engineering and may well change much in Combinatorial Optimisation as well. This talk provides a survey of the developments and presents a few applications co-developed by the presenter. Step-by-step, the talk covers: the role of conic programming in combinatorial optimisation probabilistic guarantees for convex programming relaxations accelerated first-order methods for convex programming lock-free parallelisation of first-order methods hardware implementations with applications in, among others, signal decoding for fast wireless internet (LTE), university course timetabling, parameter setting in scanning tunneling microscopes, and sales forecasting. 10 November, 2011, John-Paul Clarke,Visiting Speaker : "Abstract: Economic efficiency is a critical concern in aviation. Given " the ever increasing price of fuel, air transportation system users are constantly seeking ways to reduce congestion and delays and thus the amount of fuel as well as the time that is required to complete each mission. The impact of air transportation on the environment is also a critical issue for the aviation industry. Local opposition (on environmental grounds) to airport expansion and to changes in the terminal area routes that are flown by arriving and departing aircraft has either delayed or prevented much needed increases in capacity. Separately, concerns about climate change have called into question the efficiency of operations. Thus, aviation noise, emissions, and fuel usage must be addressed in a comprehensive way if aviation is to grow at the rate necessary to support economic expansion. I will present the details of an architecture and associated optimization algorithms that have been developed for managing surface and terminal area operations, as well as results of simulation studies and flight trials that have been conducted to evaluate the benefits that would be achieved if the aforementioned architecture and optimization algorithms were to be implemented. Further, I will discuss the genesis, development and evaluation of new operational procedures, and show how simulation and optimization techniques may be applied within the context of systems engineering to develop these procedures. 03 November, 2011, David Hodge,Visiting Speaker : "Abstract: I will give an quick overview of the history of bandit theory; " discussing objectives, restlessness and the powerful subsidy/charge based-approach. I will then give a brief overview of the different problems I have worked on in the field. I will discuss where bandit indices yield excellent heuristics for otherwise very difficult resource allocation problems. I will also discuss recent work on asymptotic optimality with a view to highlighting the many areas where the result could be of use. As well as applications to inventory management and batch arrival queues. 27 October, 2011, Per Kristian Lehre,ASAP : "Title:Running Time Analysis of Meta-heuristics" Abstract: Evolutionary algorithms (EAs) and other meta-heuristics have been applied successfully in many optimisation domains. However, a major critique has been the lack of a solid theoretical foundation. In particular, a theory that allows the performance of meta-heuristics to be predicted has until now been largely missing. This talk will cover recent advances in running time analysis of EAs. As an introductory example, we will show how to estimate the expected optimisation time of the simple (1+1) EA on selected example problems. We will then consider new analytic techniques based on drift analysis and multi-type branching processes that allow more realistic EAs with complicated population dynamics to be handled. If time allows, we will discuss black-box complexity theory which describes common limits on the efficiency of broad classes of meta-heuristics 20 October, 2011, Michael Orlov,Visiting Speaker : "Title:Evolving unrestricted Java software with FINCH" Abstract: FINCH (Fertile DarwINian ByteCode Harvester), is a methodology for evolving Java bytecode, enabling the evolution of extant, unrestricted Java programs, or programs in other languages that compile to Java bytecode. FINCH is based upon the notion of compatible crossover, which produces correct programs by performing operand stack-, local variables-, and control flow-based compatibility checks on source and destination bytecode sections--unlike earlier work that uses restricted subsets of the Java bytecode instruction set as a representation language for individuals in genetic programming. We demonstrate FINCH's unqualified success at solving a host of problems, including simple and complex regression, trail navigation, image classification, array sum, tic-tac-toe, and evolution of game heuristics. FINCH exploits the richness of the Java Virtual Machine architecture and type system, ultimately evolving human-readable solutions in the form of Java programs. The ability to evolve Java programs will hopefully lead to a valuable new tool in the software engineer's toolkit. 30 June, 2011, Ha Duong (Maverick),ASAP : "Title: n overhead estimation approach for three dimensional strip " packing problem with stability constraint. Abstract: In this talk, an overhead estimation approach is proposed for the three dimensional strip packing problem with rectangular boxes. The inputs for the three dimensional strip packing problem are a set of boxes and a container with is open dimension. The output is a packing plan of all the boxes in the container so that the required open dimension is minimised. In this work, stability constraint is considered so that all boxes are supported by other boxes or the container. The overhead estimation approach utilise the maximum contact heuristic and select the best option from a number of packing choices at each state of packing. The method is tested to compare with the other method from the literature and shows high performance of the three dimensional strip packing problem with stability constraint. 30 June, 2011, Huanlai Xing,ASAP : "Title: A Population Based Incremental Learning for Delay Constrained " Network Coding Resource Minimization Abstract: This talk concerns multicast routing problem in telecommunications networks. In traditional routing, each intermediate node simply replicates the incoming data packets and forwards a copy to its downstream node(s), adopting the store-and-forward data processing scheme. However, the maximum throughput of a multicast session may not often be achieved by using such a scheme. In contrast, with code-and-forward data processing scheme at the network-layer, network coding allows any intermediate node to re-process (encode and decode) data packets received from different incoming links if necessary, thus is capable of achieving a maximized multicast throughput according to the MAX-FLOW MIN-CUT theorem. In network coding based multicast, coding operations are expected to be minimized as they not only incur additional computational cost at corresponding nodes in network but also increase data transmission delay. On the other hand, delay constraint must be concerned particularly in delay sensitive applications, e.g. video conferencing. In this talk, I will introduce the problem of minimizing the amount of coding operations required while meeting the end-to-end delay constraint in network coding based multicast. A population based incremental learning (PBIL) algorithm is developed for this problem. 21 June, 2011, James Walker,ASAP : "Title: Adaptive Iterated Local Search for Cross-domain Optimisation" Abstract: We propose two adaptive variants of a multiple neighborhood iterated local search algorithm. These variants employ online learning techniques, also called adaptive operation selection, in order to select which perturbation to apply at each iteration step from a set of available move operators. Using a common software interface (the HyFlex framework), the proposed algorithms are tested across four hard combinatorial optimisation problems: permutation flow shop, 1D bin packing, maximum satisfiability, and personnel scheduling (including instance data from real-world industrial applications). Using the HyFlex framework, exactly the same high level search strategy can be applied to all the domains and instances. Our results confirm that the adaptive variants outperform a baseline iterated local search with uniform random selection of the move operators. We argue that the adaptive algorithms proposed are general yet powerful, and contribute to the goal of increasing the generality and applicability of heuristic search. 21 June, 2011, Jamie Twycross,ASAP : "Title: Computational modelling of the ABA signalling pathway." Abstract: I will present a summary of recent work relating to the modelling of the abscisic acid signalling pathway in plants and concomitant development of the Infobiotics modelling platform. 14 June, 2011, German Terazzas Angulo,ASAP : "Title: Programmable Self-Assembly Porphyrins" Abstract: Self-assembly is a phenomenon found in nature that can be seen as an information-driven process and, hence, be better exploited by directly linking it to computation. Taken as an operational hypothesis this assumption implies that desired emergent phenomena could in principle be programmed into self-assembling nanosystems. This talk presents part of our interdisciplinary research work which pursues the design, optimisation and exploitation of molecular self-assembly. In this occasion, I will introduce a parity calculator designed in terms of programmable self-assembly tiles which can perform any set of discrete information processing steps. These tiles are ultimately manufactured using porphyrin molecules and deposited on a substrate in order to perform the parity calculation by means of self-assembly. 14 June, 2011, Abdullah Muhammed,ASAP : "Title: Candidate List-based Constructive Heuristic to Solve a Real World " Examination Timetabling Problem. University Putra Malaysia Abstract: This talk describes a real world examination timetabling problem at the University Putra Malaysia. Considering the room assignment, our real world problem can be classified as a capacitated examination timetabling problem. In order to measure the solution quality, three soft constraints are evaluated; exam spreading, room ownership assignment and whether the last timeslot of the day is used. For the exam spread constraint, we have made some modification to the Carter spreading formula to cope with 5 timeslots per day. Room assignment has to be minimised with respect to the rooms used which are owned by other faculties. The issue of safety motivates trying to avoid using the last timeslot of the day. The constructive heuristic results are compared to the current manual solution produced by the problem owner. Our constructive heuristic results are always feasible which, is not the case for the manually produced solution. In fact, with the introduction of a larger candidate list our solution quality is far superior. Varying candidate list sizes are explored to see gauge effect, as well as utilizing various graph colouring heuristics. 7 June, 2011, Jingpeng Li,ASAP : "Title: An Investigation of a Pattern Recognition Based Intelligent " Search Method Abstract:For most scheduling problems, a solution can be considered from two different perspectives: the actual schedule specifying how some operations are planned; and the rule sequence by which how the schedule is built. Under both circumstances, solutions consist of components. This means that good patterns (i.e. promising building blocks or good partial solutions) can be identified. In this research, we propose a pattern recognition-based new framework towards the target of designing more intelligent and more flexible search systems. The role of pattern recognition is to classify the quality of resulting solutions, based on the solution structure rather than the solution cost. Hence, the general contributions of this work are in the line of insights and recommendations than real solutions. The hospital personnel scheduling and the educational timetabling are used as the case studies. For each case, we apply neural networks as the tool for pattern recognition, and demonstrate its availability by classification results on large data sets. In addition, we present some theoretical and experimental results in terms of runtime speedup. We believe that our work sheds light on the development of more advanced intelligent decision support systems. 31 May, 2011, Geert de Maere,ASAP : "Title: optimised runway sequencing" Abstract: I will introduce a pruned dynamic programming algorithm for optimal runway sequencing, modelled as a single machine scheduling problem with asymmetric sequence dependent setup times. Unlike previous work, which tends to solve the simplified problems, our approach is able to deal with complex real world scenarios. It has obtains optimal results for all investigated instances, with an average runtime of less than 8 seconds, and a maximum runtime of less than 82 seconds. In contrast, previous methods (two of them published in Operations Research) have failed to obtain optimal results when applied to these instances due to the combinatorial explosion. Our pruned dynamic program is underpinned by six core principles; inferring complete orders within sets of separation-identical jobs; inferring partial orders between sets of separation-identical jobs; inferring partial orders between sets of non-separation-identical jobs; pruning of solution based upon comparative costs; state aggregation; and inter stage pruning. I will discuss the results of a rigorous analysis of the algorithm and discuss the potential real world improvements that could be obtained. 24 May, 2011, Maria Franco,ASAP : "Title: Modelling the Initialisation Stage of the ALKR Representation for " Discrete Domains and GABIL Encoding Abstract: Models in Genetic Based Machine Learning (GBML) systems are commonly used to gain understanding of how the system works and, as a consequence, adjust it better. In this work we propose models for the probability of having a good initial population using the Attribute List Knowledge Representation (ALKR) for discrete inputs using the GABIL encoding. We base our work in the schema and covering bound models previously proposed for XCS. The models are extended to (a) deal with the combination of ALKR+GABIL representation, (b) explicitly handle datasets with niche overlap and (c) model the impact of using covering and a default rule in the representation. The models are designed and evaluated within the framework of the BioHEL GBML system and are empirically evaluated using first boolean datasets and later also nominal datasets of higher cardinality. The models in this paper allow us to evaluate the challenges presented by problems with high cardinality (in terms of number of attributes and values of the attributes) as well as the benefits contributed by each of the components of BioHEL's representation and initialisation operators. 17 May, 2011, Prof Peter Cowling ,Visiting Speaker : "adversarial, stochastic and decision nodes." Abstract: There is considerable current excitement over the potential of Monte Carlo Tree Search algorithms (particularly UCT (http://senseis.xmp.net/?UCT)), which have produced professional-level computer Go players in the past couple of years, a significant step towards addressing one of the major outstanding research questions of Artificial Intelligence (http://oase.nutn.edu.tw/FUZZ_IEEE_2009/result.htm). In the first part of this talk we will discuss very recent work on Monte Carlo Tree Search as a general-purpose way of searching minimax trees (e.g. for Go) and other trees (e.g. for multiplayer games and decision problems with uncertainty and incomplete information). When dealing with uncertainty and incomplete information, a common approach is to use a particular determinization, by assuming that all players know all information and that all random events are known in advance. We average over a number of determinizations, and choose the move with the best average score, yielding strong play for games such as Bridge and Scrabble. We will discuss the advantages and shortcomings of determinization, by reviewing our work on searching the decision trees for the card games Dou Dhi Zhu and Magic:The Gathering and the board game Lord of the Rings:The Confrontation. We will discuss approaches to handling decision trees with uncertainty and hidden information, culminating in our recent work on Information Set Monte Carlo Tree Search. as well as the work of others to create strong players for other games. This work is taking place as part of a large consortium consisting of the Universities of Bradford, Imperial, Essex and Rejkjavik and 3 industrial partners, which recently received EPSRC funding to investigate this area. In the second part of the talk we will change tack and consider combinatorial spaces arising in optimisation problems (which may of course be regarded as single player games with decision and possibly stochastic nodes) and explore recent research work into general-purpose search heuristics for optimisation (hyperheuristics), particularly in the case when we have a very large number of low level heuristics. We point towards the possibility that techniques that have yielded breakthroughs in computer Go may yield advances in other areas, including hyperheuristics. 10 May, 2011, Rong Qu,,ASAP : "Title: Case Based Reasoning in Timetabling: How can it help?" Abstract: Case based reasoning (CBR) represents one of the knowledge based techniques, and has been widely applied to some knowledge rich applications including help desk and legal advice, etc. Some attempts have been made to use CBR in scheduling. These include timetabling, production scheduling and nurse rostering problems, etc. This talk overviews some observations and lessons learned in applying CBR in timetabling problems. The research issue of case representation in case based scheduling is highlighted in two distinct CBR approaches to timetabling problems. It is demonstrated that CBR can potentially act effectively as an intelligent approach for scheduling problems, however, several challenging research issues have to be carefully addressed. Some research directions in this challenging topic are be outlined. 3 May, 2011, Jaume Bacardit,,ASAP : "Title: Data Mining Protein Structures' Topological Properties to Enhance " Contact Map Predictions Abstract: Protein structure prediction is still, after many decades of research, one of the main unsolved problems in computational biology. The potential impact of having accurate models of the structure of proteins is enormous, e.g. new medicines, better crops and, in general, a better insight into life's inner workings. In this seminar we show our work in modelling the structure of proteins using a variety of topological graphs. We also show that using data mining algorithms, it is feasible to predict some properties of these graphs based on the primary sequence of a protein. Furthermore, we will show how these topological predicted features can enhance the prediction of proteins' contact maps with good accuracy (as assessed in the last two editions of the CASP competition). 29 March, 2011, Dr Benjamin Kloepper ,Visiting Speaker University of Paderborn Germany : "Abstract: The presentation will be split into three parts. The first part" introduces a knowledge-based scheduling approach designed for application in rescheduling system: Data Mining techniques are used to extract scheduling knowledge from optimal algorithms and to implement a depth-first like scheduling approach. The learning approaches uses dispatching rules to classify scheduling decisions made by the optimal algorithms. The second part introduces a transfer of this method to implement an online planning or real time decision making procedure for a self-optimizing railway vehicle. The third part gives an overview of current research: Scheduling for Self-Optimizing Manufacturing Systems. To consider the special properties of self-optimizing systems, the scheduling process has to support alternative work plans and the internal state-trajectories of the involved manufacturing resources. 22 March, 2011, Andrew Parkes,ASAP : "Title: Searching for an Understanding of Heuristics" Abstract: Many combinatorial search problems on realistically-sized instances can only effectively be solved using heuristics tailored to the problem. Usually, such heuristics are generated using a mix of input from human experts and with a lot of trial and error. This makes them expensive and time consuming to create. In this talk, we study the creation of heuristics for online bin-packing problems. The desired heuristic is a an index policy assigning scores to various choices. We use a direct matrix representation of the policy and optimise its performance using a standard Genetic Algorithm. This can be regarded as a form of parameter tuning, but potentially with many thousands of parameters. The resulting policies substantially out-perform human-generated policies. They also show interesting and unexpected structures that suggest the framework could be used as a basis to help to understand heuristics. 15 March, 2011, John Lees-Miller,Visiting Speaker : "Abstract: Personal Rapid Transit (PRT) is a new transport mode in which " computer-guided pod cars carry passengers between stations in a dedicated network of guideways. Much like taxis, PRT vehicles run on demand, not on schedules, and they run directly from origin to destination, without stopping at stations along the way. The world's first PRT system will open at Heathrow airport this year. The main focus of this talk is the 'Proactive Empty Vehicle Redistribution' problem, which is to move idle vehicles in anticipation of future passenger requests, based on historical demand data. Two new heuristics for this problem are described; one is based on dynamic vehicle routing techniques, and the other is based on repeatedly solving transportation problems. Simulation tests show that these heuristics can substantially reduce passenger waiting times with a modest increase in empty vehicle travel. Several other OR problems that arise in the design and operation of PRT systems will also be discussed. 10 March, 2011, Greet Vanden Berghe,Visiting Speaker : "Title:Solution methodologies for structured combinatorial optimisation problems" Abstract: The talk focuses on problems that combine characteristics of different known combinatorial optimisation problems, e.g. nurse rostering and vehicle routing in the home care scheduling problem, and scheduling and packing in the lock scheduling problem. Without giving a formal definition, this type of combinatorial optimisation problems will be referred to as `structured' problems. Until now, structured combinatorial optimisation problems often withstand efforts to solve them satisfactorily by state of the art methods, and maybe as a consequence, have not always been subject to profound research. Solution approaches for this type of problem, if available at all, usually combine a model for the entire problem with a general purpose heuristic solver. These methods do not provide information about the solution quality or the optimality gap. One interesting avenue of research involves decomposing a problem into tractable subproblems. In such an approach, a solution to one subproblem can be used as input to solve another subproblem. Clearly, there can be different ways to decompose a problem, and to merge the partial solutions into a feasible solution to the original problem. Examples of heuristic strategies for solving structured combinatorial optimisation problems will be discussed. 8 March, 2011, Greet Vanden Berghe,Visiting Speaker : "Title: Modelling issues in real combinatorial optimisation problems a nurse rostering case" Abstract: Nurse rostering has attracted the attention of many researchers and practitioners. It is interesting to notice that many different variants of the problem exist. The main differences between nurse rostering problems constitute personnel characteristics such as experience, skill and contract, in addition to work characteristics like coverage constraints, shifts. The number and the type of the objectives, and the hard and soft constraints vary among problem definitions. In this talk, we concentrate on two particular modelling issues that require a lot of attention in order to make nurse rostering approaches re-usable in different settings, and eventually in a real world environment. The first problem considers the rolling horizon. It deals with constraint evaluation across planning periods. Secondly, we present a model for dealing with idle days and absence requests in a different manner. It offers an extension to existing constraint definitions. 1 March, 2011, Ozgur Ulker,ASAP : "Title: Experimental Analysis of the Components of the Objective Function " in the Office Space Allocation problem Abstract: Office Space Allocation (OSA) problem refers to the assignment of entities to office spaces subject to the hard/soft constraints and minimisation of space misuse. In this talk, the effects of the components (space underuse/overuse, space misuse, and soft constraint violation penalty) of the objective function on the difficulty of the problem will be discussed. A parameterised OSA instance data generator (which adjusts space underuse/overuse/misuse, and soft constraint violation penalties) was developed for this study. The test instances were solved using the Gurobi ILP solver. The talk will focus on how the changes on the parameters of the instance generator effect the difficulty (in terms of proof of optimality) of the OSA instances, the effect of the weight of the soft constraint penalty and how much the space misuse elements can deviate from intended values. 1 March, 2011, Rupa Jagannathan,ASAP : "Title: A two-phase case-based reasoning system for radiotherapy " treatment planning Abstract: Radiotherapy treatment planning for head, neck and brain cancer is a complex decision-making process that relies heavily on the subjective experience of clinicians. The aim of a treatment plan is to apply radiation to kill tumour cells, while minimising the damage to healthy tissue and critical organs in the vicinity of the tumour. In this talk, I describe a two phase case-based reasoning system that generates treatment plans based on plans of similar patients that were treated in the past. Each phase of the system focusses on retrieving a solution that provides a particular parameter of the treatment plan. 25 February, 2011, Professor David Pelta, Granada University : "Title: Multi-agents based search for dynamic optimization problems: a gentle introduction" Abstract: Telecommunications, infrastructures, services and, in general, all the aspects concerning the information society, give raise to a set of complex problems where several objectives may need to be satisfied, that may vary with time, or where uncertainty of diverse types may exist in the values of the variables, coefficients, or even in the objectives. Also, alternatives that were bad in the past can be good nowadays or vice versa; criteria that were important before become irrelevant now, etc., and moving in this dynamic scenarios is a challenge. The development of solving strategies in the area of intelligent systems that may work in such dynamic and imprecise scenarios raises new challenges that are being addressed from different points of view by the international scientific community. Many problems in this context can be modeled as dynamic optimization problems (DOPs) in which some elem (outside the ASAP group) have started to use it in their studies. Such a popularity is caused by unique properties of the LAHC. At the previous ASAP seminar it was shown that it is very simple and easy to tune search technique, but simultaneously strong enough: it outperforms the Great Deluge algorithm (GDA) and works on the same level as Simulated Annealing (SA) and Threshold Accepting (TA) method. With further investigation, the LAHC reveals more and more its wonderful properties. First, it is not sensitive to initialization. Second, it can have tens (or maybe hundreds) of different variants and modifications. These variants perform differently with different problems, which is a very promising area of future research. Probably the most interesting property of the LAHC is its robustness: it keeps working in situations where the cooling-schedule based algorithms (SA, TA and GDA) fail. The most recent study of the LAHC has revealed that it can serve not only as an optimization technique, but it also can provide an unified measure of the complexity of different problems (of different types). Maybe this can help to get an answer to a many-decades optimization dilemma: what is more effective: a number of short runs (including a reheating strategy) or just a single long run of a search procedure? 17 February, 2011, Michael Clark,ASAP : "TBA" TBA 17 February, 2011, John Drake,ASAP : "Title: Controlling Crossover in a Selection Hyper-heuristic Framework" Abstract: In evolutionary algorithms, crossover is used to recombine two candidate solutions to yield a new solution which hopefully inherits good material from both. Crossover is increasingly being included in general purpose hyper-heuristic frameworks such as HyFlex and Hyperion however little work has been done to assess how best to utilise it. As a single-point search hyper-heuristic operates on a single candidate solution and two candidate solutions are needed for crossover, a mechanism is needed to control the choice of the other solution. In this work we present a framework for controlling a list of candidate solutions for use as a second solution in crossover. We will present results for a number of selection hyper-heuristics and CPLEX over three benchmark libraries for an NP-hard optimisation problem; the multidimensional 0-1 knapsack problem (MKP). 15 February, 2011, Mashael Maashi,ASAP : "Title: An investigation of Multi-objective Hyper-heuristics to solve " Multi-objective optimisation problems Abstract: Hyper-heuristics have drawn increasing attention from researchers in recent years. However, the majority of research in this area has been limited to single objective optimisation. Hyper-heuristics for multi-objective optimisation problems is a relatively new area of research. This research, for the first time, investigates hyper-heuristics hybridised with multi-objective evolutionary algorithms (MOEA) in order to tackle multi-objective problems. The main aim of this research is to investigate a multi-objective hyper-heuristic approach for multi-objective optimisation problems utilising multi-objective evolutionary algorithms. We are attempting to create more robust algorithms that are capable of generating better results when compared with existing MOEA approaches. We propose a framework based on three multi-objective evolutionary algorithms. NSGAII, SPEA2 and MOGA are selected to act as the low level heuristics in the proposed Multi-objective Hyper-heuristics MOHH approach. We may later extend this set of algorithms to include NPGA and MOMGA. The WFG test suite is selected, as our test suite from the various multi-objective test suites available, as it has the most desirable features. In addition, four performance metrics are selected as a feedback mechanism for MOHH approach. Our work to date is as follows: 1. A literature review has been carried out, covering the main issues addressed by this thesis. 2. We have analysed the various test suite available and chosen to use the WFG test suite. 3. Three multi-objectives evolutionary algorithms NSGAII, SPEA2 and MOGA have been implemented. 4. A multi-objective hyper-heuristics framework has been designed. We are now in the process of implementing the MOHH and designing the first set of experiments. 10 February, 2011, Tim Pigden,Optrak : "Object-Orientated Problem definitions for real-world vehicle routing problems" Abstract: The classic "VRP" problem definition is a long way removed from daily logistics practice - a simplification of transport planning going back to the 1950s. Although this model is extended for other standard problems (CVRP, VRPTW etc) these models remain overly simplistic and fail to encapsulate the complex requirements of commercial systems. This talk presents an Object-Oriented/Function model that covers a wide range of real-world cases and encapsulates data and constraints. It will be shown alongside a matching xml-based file definition, sample data and working code (using the Scala programming language) to validate problem data and solutions. 8 February, 2011, Azhar Ali Shah Syed,ASAP : "Title: Artificial Cells Based on Novel Diblock Copolymers - Modeling and Computation" Abstract: This research is based on James Smaldon's recent PhD dissertation on 'Modelling tools and methodologies for rapid protocell prototyping'. The dissertation provides a framework for utilizing the multiscale modeling approach that includes atomistic molecular dynamics, mesoscale dissipative particle dynamics (DPD) and P-Systems to study the structure and properties of different components related to the e literature on automatic program generation employs such population based search approaches, to allow a computer system to search a space of programs. In this presentation, I will present an alternative approach based on local search. There are many local search methodologies which allow successful search of a solution space, based on maintaining a single incumbent solution and searching its neighbourhood. However, these techniques have not yet been employed to search a space of programs. I will show that local search of programs can be more successful at automatic program generation than current evolutionary computation methodologies. 7 December, 2010, Stefan Ravizza,ASAP : "Ground Movement at Airports" Abstract: Determining efficient airport operations is an important problem for airports, airlines, passengers and other stakeholders. Moreover, it is likely to become even more so given the traffic increases which are expected over the next few years. The ground movement problem is especially important since it forms the link between the other airside problems, such as arrival sequencing, departure sequencing and gate/stand allocation. This presentation highlights various important open areas of research for ground movement, shows results of the scalability of various algorithms which have been tested on real-world scenarios and provides an extensive statistical analysis to identify and model the most relevant factors affecting the variability of taxi times. The developed statistical model already shows promising results for two different European hub airports. Importantly, it is not only useful for predicting total taxi times, but it also allows the effects of individual elements to be disregarded, allowing predictions to be used in scheduling and routing algorithms which simulate/predict these elements themselves. 7 December, 2010, Jack Chaplin,ASAP : "Computing using photoswitching molecules" Abstract: Unconventional methods of computation have been explored for sometime, looking for new and interesting ways of expanding our computational horizons. This project aims to utilise light sensitive molecules to show a proof of concept of applicability to computation, and we demonstrate implementations of data registers and logic gates including several logically complete sets. 25 November, 2010, George Steiner : "The Earliness-Tardiness Scheduling Problem with Due Date Assignment and Resource-Dependent Processing Times" abstract: We study the earliness-tardiness scheduling problem on a single machine with due date assignment and controllable processing times. The model has applications in just-in-time scheduling and situations where part of the work can be outsourced. We analyze the problem with three different due date assignment methods and two different processing time functions. For each combination of these, we provide a polynomial-time algorithm to find the optimal job sequence, due date values and resource allocation minimizing an objective function which includes earliness, tardiness, due date assignment, makespan and total resource consumption costs. 23 November, 2010, Dario Landa-Silva,ASAP : "Automated Transportation Planning: Multi-carrier and Fleet Scenarios" Abstract: This talk describes a couple of scenarios in the area of transportation planning in which the goal is to produce a plan for the delivery (sometimes also collection) of goods from the customer warehouses to a set of different consignees. A transportation plan indicates what shipments are assigned to each vehicle load plus information about routes, pickup and delivery times, etc. In the first scenario called multi-carrier planning, vehicle loads are planned and then assigned to specific carriers in order to minimise cost. In the second scenario called fleet planning, trips are planned for each vehicle in the fleet and the goal is to maximise the utilisation of the fleet while delivering as many shipments as possible. Models and solutions procedures involving optimization and heuristic techniques are applied in order to produce transportation plans which are being used in practice by our industrial partner in this project. 16 November, 2010, Stanislava Armstrong,ASAP : "Multi-Objective Dynamic Programming Approach for Aircraft Landing Sequencing with Stack Holding" Abstract: Busy airports experience periods when demand exceeds runway capacity, which leads to an accumulation of aircraft circling in nearby stacks. This causes delays, which can adversely affect ground resource utilization and may have implications for connecting flights. Therefore, an accurate estimation of landing times could contribute to better resource allocation and time management. Due to potential safety threats and fairness considerations, the arrival stacks can limit the possible landing sequences and therefore they should be modelled to obtain a more realistic solution. We have developed a multi-objective dynamic programming approach that derives a realistic landing sequence whilst making use of the specifics and the constraints enforced by the holding patterns. I will discuss the problem, explain the solution method and present some preliminary results. 16 November, 2010, Gabriela Ochoa,ASAP : "The first Cross-domain Heuristic Search Challenge" Abstract: The first Cross-domain Heuristic Search Challenge (CHeSC 2011, http://www.asap.cs.nott.ac.uk/chesc2011/index.html) seeks to bring together practitioners from operational research, computer science and artificial intelligence who are interested in developing more generally applicable search methodologies. The challenge is to design a search algorithm that works well, not only across different instances of the same problem, but also across different problem domains. This seminar will overview the main features of this international event, and will serve as a launch opportunity for the ASAP challenge that will be running in parallel with the international competition. 12 November, 2010, Anthony Goldbloom,CEO of Kaggle : "Crowdsourcing data modelling" abstract: Data modelling competitions allow researchers and companies to post their problem and have it scrutinised by the worlds data scientists. Since the solution to many of today's pressing problems rely on data-driven insights, data modelling competitions are a powerful way to address many 21st century challenges. By exposing a problem to a wide range of analysts and techniques, data modelling competitions turn out to be great way to get the most out of a dataset, given its inherent noise and richness. For example, Kaggle recently ran a bioinformatics competition requiring participants to pick markers in HIV s genetic sequence that predictthe talk will include sample applications in the domains of telecommunications, bioinformatics, and software engineering. 2 November, 2010, Graham Kendall,ASAP : "Some of the Issues Surrounding Sports Scheduling" Abstract: In this talk I will briefly discuss some of the progress that we made to date on the sports scheduling research that we have undertaken. I will also present some of the other issues that we have had to address in trying to achieve our primary objectives. This has included developing Google Map applications and geocoding postcodes in order to allow greater manipulation of the data that we have collected. I will also discuss the data collection aspects of the problem, which has proved to be the most time consuming part of the overall project. 26 October, 2010, Pawel Widera,ASAP : "Research in the cloud - the case of protein structure comparison" Abstract: In the field of bioinformatics the practical aspect of research is very important. It is not enough to present a theoretical result to gain the attention of the community. Often even a working implementation of a method is not enough, as usually a complex and time-consuming setup is required to make it run. These are the reasons why web services became a preferable method of research exposition. They are not only bringing the new tools just a few clicks away from the users but they also enable them to perform experiments quickly by utilising the power of distributed computing. In this talk I will describe two approaches to build a web service able to handle large data sets required in multi-criteria protein structure comparison. Starting from the currently available cluster-based ProCKSI server architecture I will discuss an alternative approach based on the so called "cloud computing" technology. Then I will present a prototype application working on the Google App Engine platform and discuss its limitations and performance. Finally, I will try to answer an ultimate question whether the research in the cloud is the next big thing or an epic fail. 26 October, 2010, Jonathan Blakes,ASAP : "Development and deployment of a cross-platform open-source software package" Abstract: During my PhD I have worked within a team to deliver a desktop application for modelling, in-silico experimentation and analysis of biological systems that we have call the Infobiotics Workbench. My efforts have mainly focused on developing the Infobiotics Dashboard, an intuitive graphical user interface for configuring and performing Infobiotics experiments and visualising the results. The first part of this talk will demonstrate some of the functionality of the 'dashboard' and discuss the design decisions taken during its development. The second part will unpick issues arising from those choices, in particular managing differences in target platforms, and the solutions we devised to overcome them. Along the way I will highlight the academically less-glamourous but important and time-consuming aspects of a software release: documentation, installers, testing, soliciting user feedback and releasing the code. 19 October, 2010, Tim Curtois,ASAP : "Applying a general rostering model to a diverse collection of benchmark instances including the 2010 nurse rostering competition instances" Abstract: In my previous ASAP seminar I presented the outline of a general and flexible model which we believed could be used to model the varying rostering problems found in different workplaces. The aim of the model was to raise the level of generality and to develop a robust solver which could be applied to the various versions of the rostering problem without having to re-engineer the model or algorithms. This time I will present the results of using this model on our large collection of diverse benchmark rostering instances. I will also present the results of applying the model and algorithms to the 2010 nurse rostering competition instances. 19 October, 2010, Enrico Glaab,ASAP : "Learning pathway-based decision rules to classify microarray cancer samples" Abstract: In this talk, I will present a new machine learning method to extract simple decision rules for tumour sample classification from microarray gene expression data. The approach is based on findings from cancer biology, according to which oncogenic diseases often result from the deregulation of cellular signalling pathways (consisting of several functionally related genes and proteins) rather than from a single, specific genetic event. Therefore, in contrast to previous statistical learning approaches discriminating between different disease states based on the expression levels of single genes, the method presented here analyses relations between the expression levels of multiple genes in pairs of cellular pathways. By identifying changes in these relations across the disease classes, the algorithm generates a collection of simple decision rules and combines them into an ensemble classification model. Results for two large-scale microarray studies, containing samples from prostate cancer and B-cell lymphoma patients, show that the method provides compact and comprehensible sets of classification rules and can help to identify functional associations between cellular pathways and genetic diseases. 12 October, 2010, Jason Atkin,ASAP : "Airport optimisation" Abstract: I will talk about some of the airport optimisation work which has been done with Heathrow and some which is still going on. I will mainly concentrate upon departure runway optimisation and pushback time allocation, but will also discuss the differences between arrival and departure sequencing problems and give an overview of some of the other optimisation problems which have to be handled. The two main problems which will be discussed have many similarities to machine scheduling problems with sequence dependent set-up or processing times, but have important problem specifics which have to be taken into account. 5th March 2009. Qiang Guo (John), ASAP "Applying Grouping Method for Cutting and Packing Problems" The Grouping Genetic Algorithm has been previously applied to one-dimensional bin packing problems and obtained some good results. We are extending the method to multi-dimensional problems. The idea is to reuse of good building blocks and avoid bad ones. During the developing of this technique, we have observed some factors which may have significant influence on results. The project is still on-going and we will appreciate any comments /discussion on this technique. 26th February 2009. Gabriela Ochoa, ASAP "HyFlex: A Flexible Framework for the Design and Analysis of Hyper-heuristics" This seminar is more like a tutorial than a research talk. The first part of the talk will present an overview and a classification of hyper-heuristic approaches. The second part will introduce Hyflex, a novel OO framework for supporting research into modern search methodologies (especially but not only hyper-heuristics). This is a team effort (Tim, Antonio, Matt and me). The emphasis of the HyFlex framework lies in providing the algorithm components that are problem specific, thus liberating algorithm designers from needing to know the problem domains specific details. The design efforts of HyFlex's users will instead be focused on designing high-level strategies to intelligently combine the provided tools. 19th February 2009. Jingpeng Li, ASAP "A New Data Mining Based Multi-objective Optimisation Framework" Multi-objective optimization is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints. In this presentation, I will briefly introduce a new data mining based multi-objective optimisation framework. Firstly, we generate an initial solution by whatever method, such as a heuristic or mathematical approach. We then use any local search method to search the neighbouring area of the initial solution and identify a new solution. Next, we evaluate the quality of the newly-obtained solution under multiple objectives, by the method of compromise programming. Later, we set a criterion to decide if the solution can be accepted, by any of the methods such as hill-climbing, simulated annealing, tabu search, and our newly-proposed falling tide optimisation. After accepting a new solution, we update the maintained Pareto set which contains a number of solutions, with each solution being no worse than any other solutions for all objectives and being better in at least one objective. The following four steps are executed in a loop, until a stopping condition met. In the meaning time, we use a data mining processor to aid or speed up the search. Data mining is the search for relationships and global patterns that exist in large databases but which are hidden among them. By data mining, we can predict the quality of resulting solutions, without calculating their actual objective values. 19th February 2009. Jonathan Blakes, ASAP "The case for another systems biology modelling environment" Systems biology is a growing interdisciplinary field that aims understand the normal and abnormal functioning of organisms by modelling the relationships between molecular species in living cells. There is a large body of software, often developed in academia, to assist with the building and simulation of such models. This talk will give an overview of recent computational modelling approaches in systems biology and the associated software landscape. It presents the case for the development of a new modelling environment aims to improve the user experience of biologists by making models easier to build and to refine, while increasing the complexity of and scales over which models can be built. 12th February 2009. Xiang Song, Research associate in School of Mathematics, University of Cardiff "Variant Beam Search Implementation for the Irregular Shape Bin Packing Problem" The talk presents progress on the design of an evolutionary algorithm which uses the concept of volume dominance instead of conventional Pareto dominance to assign fitness to solutions in multi-objective optimization (MOO). We have previously proposed volume dominance to promote a good balance between convergence and diversity in MOO. Volume dominance has improved the performance of other algorithms and now we combine it with other features such as ranking and crowding techniques. Preliminary experiments on multiple knapsack problems shows that the presented algorithm significantly improves the diversity of the non-dominated solutions set when compared to SEAMO2, SPEA2, NSGA2. 12th February 2009. Khoi Le, ASAP "Volume Dominance Within a Multi-objective Evolutionary Algorithm" The talk presents progress on the design of an evolutionary algorithm which uses the concept of volume dominance instead of conventional Pareto dominance to assign fitness to solutions in multi-objective optimization (MOO). We have previously proposed volume dominance to promote a good balance between convergence and diversity in MOO. Volume dominance has improved the performance of other algorithms and now we combine it with other features such as ranking and crowding techniques. Preliminary experiments on multiple knapsack problems shows that the presented algorithm significantly improves the diversity of the non-dominated solutions set when compared to SEAMO2, SPEA2, NSGA2. 5th February 2009. Yuri Bykov, ASAP "Late Acceptance Strategy - the new general-purpose optimisation metaheuristic" The Late Acceptance Strategy is a recently invented optimisation methodology, which has been publicly presented on PATAT 2008 conference. It was adapted to Hill-Climbing algorithm (LAHC - Late Acceptance Hill-Climbing) and applied to Exam Timetabling Problems. This search technique has only one parameter, very simple for implementation and tuning and, at the same time, its performance is not worse (or even better) than the most powerful metaheuristics, such as Simulated Annealing. Its high quality was confirmed by ASAP group members who already implemented it and I suppose that more other researches will be interesting to apply it to their problems. 29th January 2009. Zalilah Abd Aziz, ASAP "An Ant-based hyperheuristic for Vehicle Routing Problem" One of the aims for hyperheuristics is to raise the generality of an optimisation system. The objective is to produce a more general system that is able to solve a wider range of problem domains. In this presentation, I will explain briefly the concept of Ant-based hyperheuristics and the Vehicle Routing Problem. 29th January 2009. Antonio Vazquez, ASAP "Discovering interesting algorithm variants using genetic programming" An exciting new application of genetic programming is the automatic discovery of procedures to solve difficult combinatorial problems. Researchers so far have built new algorithms from scratch by combining primitive operators or components of known algorithms into fully working procedures. In this work, we (1) start with a well known heuristic, (2) identify one of its components which is easy to modify and has an important contribution to performance, (3) use genetic programming to find an improved compatible new component, and (4) replace the old component with the new one. We have used this methodology to find variants of the well known NEH heuristic to solve the permutation flow shop problem with different objective functions, and constraints. We demonstrate that, according to certain metrics, the new heuristic variants are as successful on their target problems as is NEH on the problem for which it was originally designed. 22nd January 2009. Rupa Jagannathan, ASAP "Dealing with missing values in a clinical case-based reasoning system" In clinical case-based reasoning systems, missing values in the case-base pose a common but serious problem that impairs the performance of the system. Imputing or estimating missing values by making an informed guess is popular in many knowledge-based systems but once the imputation has been performed, the system needs to be adjusted to acknowledge the fact that imputed values are only estimates of original values. In this talk, I will introduce an imputation method that exploits the correlation between clinical data by filtering the case-base according to attributes correlated to the missing attribute. I will also present a framework that shows how any imputation method can be used in a case-based reasoning system to reflect the quality of the imputation method in the similarity calculation and account for the inherent uncertainty associated with imputation. 22nd January 2009. Sven Groenemeyer, ASAP "Cyclic Job-Shop Scheduling with one Transport Robot" Many jobs in industrial production and elsewhere consist of sets of tasks or operations which have to be processed on different machines. However, for this processing there are several conditions or constraints which have to be satisfied. In large-scale productions identical jobs are performed many times. To deal with such situations, cyclic scheduling problems are introduced which will be presented in this talk. Furthermore, we assume that the jobs are transported between the machines by one robot. Thus, we have additional constraints concerning the robot moves. In this talk, we will show the advantages and disadvantages of cyclic scheduling in general. Most authors considering the problem including a transport robot assume that the route of the robot is given in advance. Thus, we will show how the route the robot takes to transport the different jobs between the machines can influence the quality of possible solutions. Additionally we present some ideas for local search heuristics to solve the general problem. 15th January 2009. Patrick Moratori, ASAP "Match-Up Strategies for Job Shop Rescheduling" We investigate the problem of integrating new rush orders into the current schedule of a real world job shop floor. Satisfactory rescheduling methods must keep stability of the shop, by introducing the fewest number of changes in the ordering of operations, while maintaining the same levels of the schedule performance criteria. This paper introduces a number of match-up strategies that modify only part of the schedule in order to accommodate new arriving jobs. These strategies are compared with the right-shift and the total-rescheduling methods, which are optimal regarding stability and performance, but ineffective for performance and stability, respectively. Statistical analysis indicates that the match-up strategies are comparable to right-shift for stability, and as good as total-rescheduling for performance. 15th January 2009. Juan Pedro Castro Gutierrez, ASAP "From Infeasible to Feasible Solutions for the VRPTW Using a MOPSO Approach" This presentation is intended to show the ability of a discrete particle swarm optimization algorithm (DPSO) to evolve solutions from infeasibility to feasibility for the Vehicle Routing Problem with Time Windows (VPRTW). The proposed algorithm incorporates some principles from multi-objective optimization to allow particles to conduct a dynamic trade-off between objectives in order to reach feasibility. The main contribution of this paper is to demonstrate that without incorporating tailored heuristics or operators to tackle infeasibility, it is possible to evolve very poor infeasible route-plans to very good feasible ones using swarm intelligence. 11th December 2008. Ying Xu, ASAP "A Variable Descent Search Algorithm for Multicast Routing Problem" The rapid evolution of real-time multimedia applications requires Quality of Service based multicast routing in underlying computer networks. The constrained Steiner Tree, as the underpinning mathematical structure, is a well-known NP-complete problem. In this paper we investigate variants of variable neighborhood search for the delay-constrained least-cost multicast routing problems. The neighborhood structures designed in the variable neighborhood search approaches are based on the idea of path replacement in trees. They are simple, yet effective, enabling a flexible search over the solution space of this complex problem with multi-constraints. A large number of simulations demonstrate that our algorithm is highly efficient in solving the delay-constrained least-cost multicast routing problem in terms of both the total tree cost and execution time. To our knowledge, this is the first study of variable neighborhood search on delay-constrained least-cost multicast routing problem. It outperforms other algorithms and heuristics over a range of problem instances. 11th December 2008. Nor Hayati Abdul Hamid, ASAP "Maximising Stadium Attendance : A Case Study of Malaysian Football" Malaysian football is seeing a decrease in the number of supporters at stadiums. We propose that a level of importance is defined for each fixture, which we then maximise. This is in the expectation that the more important a match, the more attractive it will be for supporters. 4th December 2008. Fang He, ASAP "A Hybrid Constraint Programming Approach for Nurse Rostering Problems" Due to the complexity of nurse rostering problems (NRPs), pure Constraint Programming (CP) approaches have shown to be ineffective in solving these highly constrained problems. We investigate a two-stage hybrid CP approach on real world benchmark NRPs. In the first stage, a CP model is used to generate weekly rosters consist of high quality shift sequences satisfying a subset of constraints. An iterative forward search is then adapted to extend them to build complete feasible solutions. Variable and value selection heuristics are employed to improve the quality of the solution built. In the second stage, a simple Variable Neighborhood Search is used to quickly improve the solution obtained. The basic idea of the approach is based on the observations that high quality nurse rosters are consist of high quality shift sequences. By decomposing the problems into solvable sub-problems for CP, the search space of the original problems are significantly reduced. The results on benchmark problems showed the efficiency of this hybrid CP approach when compared to the state-of-the-art approaches in the literature. 4th December 2008. Sam Allen, ASAP "A Novel Heuristic/Metaheuristic Approach to the Three-Dimensional Strip-Packing Problem" Although cutting and packing research has received significant attention in recent years it has generally concentrated on one or two-dimensional packing. Though this has many real-life practical applications - paper, metal, glass or other sheet material cutting, basic pallet loading etc., and several more theoretical ideas such as multi-processor scheduling it is not directly applicable or translatable to other industrial problems, such as three-dimensional block cutting (e.g. foam, wood, marble etc.), load planning (trucks, air cargo etc.) or multi-dimensional limited resource scheduling. The proposed packing strategy developed for the 3-dimensional strip-packing problem draws inspiration from the ideas proposed for the equivalent two-dimensional problem algorithm presented by Burke et al in 2004, whilst adding a number of substantial changes and improvements in order to make it applicable to the three-dimensional problem. The results so far are extremely competitive and show a lot of potential for future applications. The heuristics created scale well to large problems and also create high quality solutions for two-dimensional problems, which are being explored in conjunction with a University spin out company, Aptia Solutions Ltd who specialise in creating automated nesting and machine control cutting software. 27th November 2008. Djamila Ouelhadj, ASAP "A Cooperative Hyper-heuristic Framework for Scheduling" The aim of this research work is to investigate the role of cooperative decision making in the selection process of low level heuristics within a distributed hyper-heuristic framework to enhance performance and robustness. The cooperative hyper-heuristic framework is an agent-based system composed of a Coordinator Hyper-Heuristic Agent (CHHA) and a population of Low Level Heuristic Agents (LLHA). The HHA manages the cooperative selection of the low level heuristics to apply at each decision point of the search space. The LLHAs perform different search strategies using different low level heuristics, and coopearte synchronously or asynchronously through the CHHA. Cooperation is based on the solution pool strategy, in which the LLHAs cooperate through the synchronous/asynchronous exchange of elite solutions of the low level heuristics. Experimental results for a set of permutation flow shop benchmark instances illustrate the performance of the asynchronous/asynchronous cooperative hyper-heuristics. 27th November 2008. Amr Soghier, ASAP "An Adaptive Graph Based Hyper-heuristic using GRASP for Exam Timetabling Problems" We propose an approach where two low-level graph heuristics, Saturation Degree (SD) and Largest Weighted Degree (LWD) are dynamically hybridised in the construction phase of a Greedy Random Adaptive Search Procedure (GRASP) to construct solutions for exam timetabling problems. The problem is initially solved using an intelligent adaptive LWD and SD graph hyper-heuristic, which constructs the restricted candidate list (RCL) in the first phase of GRASP. It is observed that the SD heuristic is essential to construct a feasible solution but that it does not perform well at the early stages of the construction. Therefore, LWD is used until a certain switching point is reached. The hyper-heuristic determines the best switching point adaptively after evaluating the quality of the solutions produced. Steepest descent is used in the improvement phase of GRASP to improve the quality of td candidate structures. The energy function is commonly defined as a linear combination of energy terms designed by human experts. Although a vast amount of scientific effort has been put into development of these energy components, not much is known about how they should be combined into the energy function. To test the hypothesis that less restricted combination of the energy terms may lead to more accurate prediction, we have designed a genetic programming algorithm to evolve the energy function for protein structure prediction. The talk will introduce a number of different GP designs that we came up with and present the results of evaluation of their accuracy on a set of protein structures generated by the real predictor. 6th November 2008. Jakub Marecek "Decomposition, Reformulation, and Diving" In many real-life optimisation problems, there are multiple interacting components in a solution. For example, different components might specify assignments to different kinds of resource. Often, each component is associated with different sets of soft constraints, and so with different counts of their violations. The goal is then to minimise a linear combination of such counts of violations related to particular components of a solution. On the example of Udine Course Timetabling, this paper studies an approach to such problems, which can be denoted as multiphase exploitation of multiple objective-/value-restricted submodels. In this approach, only one computationally difficult component of a problem and a subset of objectives is considered at first. This produces partial solutions, which define interesting neighbourhoods in the search space of the complete problem. Using integer programming, it is easy to implement heuristics producing solutions with bounds on their quality. 30th October 2008. Graham Kendall "Balancing Conflicting Objectives for English Football" Previous work minimised the distance travelled by English football clubs over the Christmas/New Year period. In doing so various constraints have to be respected. One of these relates to /clashes/ which measures how many /paired/ teams play at home on the same day. The schedules that are actually used allow a certain number of clashes and our previous work used these values for our investigations. In this work we explore if travel distances are significantly increased if we reduce the number of clashes below those that were used in practise. The results from seven seasons will be presented. 23rd October 2008. Alberto Castellini "Metabolic P systems for modelling biological processes" Metabolic P systems, shortly MP systems, are a class of P systems proved to be effective and successful for modeling biological phenomena related to metabolism. Equivalences between this formalism and, respectively, autonomous ODE and Hybrid Functional Petri nets have been recently proved, and several biological processes have been modelled, such as the lac operon gene regulatory mechanism in glycolytic pathway and the mitotic cycles in early amphibian embryos. A Java virtual laboratory, called MetaPlab, have been also developed which supports the synthesis and the simulation of MP models by means of an extensible plugin-based architecture. In this talk I introduce a new technique, based on neural networks, for the synthesis of MP regulation functions, namely the functions that regulate the dynamics of an MP system, and I show some results achieved by this methodology. 23rd October 2008. Joe Obit "Great Deluge with Non-linear Decay Rate for Solving Course Timetabling Problems" Course timetabling is the process of allocating, subject to constraints, limited rooms and timeslots for a set of courses to take place. Usually, in addition to constructing a feasible timetable (all constraints satisfied), there are desirable goals like minimising the number of undesirable allocations (e.g. courses timetabled in the last timeslot of the day). The construction of course timetables is regarded as a complex problem common to a wide range of educational institutions. The great deluge algorithm explores neighbouring solutions which are accepted if they are better than the best solution so far or if the detriment in quality is no larger than the current water level. In the original great deluge, the water level decreases steadily in a linear fashion. In this paper, we propose a modified version of the great deluge algorithm in which the decay rate of the water level is non-linear. The proposed method produces new best results in 4 of the 11 course timetabling problem instances used in our experiments. 16th October 2008. Pedro Rocha "Constructive Approaches to Radiotherapy Scheduling" With the increase in the number of cancer cases and new government regulations for cancer treatment, radiotherapy scheduling has gained a lot of importance recently. In this paper, four constructive approaches to radiotherapy scheduling are introduced, as well as a GRASP based algorithm for improving the solution obtained by the constructive approaches. These algorithms are investigated on real-world data obtained from the Nottingham University Hospitals NHS Trust, UK. 9th October 2008. Robert `Bob' Oates: "Immunology, Signal Processing and RatSLAM" A large proportion of bio-inspired computing is based on abstracted models of the brain and nervous system. However, from an engineering perspective, there is a largely-overlooked mechanism within the body that performs information processing, contains aspects of memory and decision making and lends itself perfectly to parallel computation: the immune system. This talk will provide a simple introduction to the basics of immunology and go on to demonstrate how these mechanisms have inspired a variety of novel algorithms. The talk will go on to focus on a relatively new algorithm within the field of artificial immune systems based on the operation of dendritic cells developed by Dr Julie Greensmith at the University of Nottingham and explain how we intend to fuse this algorithm with The University of Queenslands RatSLAM algorithm to provide an immune-inspired robotic security system. 2nd October 2008. Minaya Villasana: "An approach to cancer chemotherapy scheduling" We start with a mathematical model that can capture qualitative features of tumour growth and it's interaction with the immune system. The purpose is to use the drug as a controller of the system, taking the tumour level to desired states. In mathematical terms, we are guiding the tumour into the basin of attraction of a tumour-free stable equilibrium of the dynamical system. We will focus on the modelling aspect of the problem formulations, give a brief summary of the most important results up to date, work in progress, and future directions. 4th September 2008. Nikola Todorovic: "Bee Colony Optimisation for Nurse Rostering" We propose a novel bee colony optimisation approach to the nurse rostering problem. The bee colony optimisation algorithm belongs to the class of stochastic swarm optimisation methods. It is motivated by the foraging habits of honey bees. In iterations, artificial bees collectively improve their solutions. The algorithm for nurse rostering was designed to be a combination of constructive and improving phases. In the constructive phase, unscheduled shifts are being assigned to available nurses, while the improving phase aims to improve the current solution within the defined neighbourhood. An intelligent discarding of the portion of a large neighbourhood is performed for which it is predicted that it will not lead to the improvement of the objective function. The algorithm was tested on real world data from hospitals in Belgium. The results show that the bee colony optimisation is able to efficiently find solutions that are competitive compared to the solutions produced by other algorithms. 23rd July 2008. Michel Toulouse: "A cooperation/diffusion search algorithm and applications to hyper-heuristics" Search steps in population based methods make use of information gathered from several points. In cooperative neighborhood based methods, information is obtained from points (solutions) generated by several independent search programs running concurrently. This information is then integrated in the decision process of neighborhood based search methods allowing for cooperation among search methods. However, centralized cooperation schemes involving many programs are difficult to define and cumbersome to implement. In this talk, I describe a decentralized cooperation/diffusion scheme in which information is gathered and used cooperatively in several small scale cooperative algorithms. This information then diffuses across many cooperative algorithms, forming a single large scale cooperative problem solving system. Cooperative search could be seen as a mean to address the heuristic selection problem. I will describe new algorithms which are initial avenues to hybrid cooperation/diffusion schemes with hyper-heuristics. 9th July 2008. Jacomine Grobler: "Metaheuristics for multiple machine multi-objective production scheduling" Production scheduling has been fascinating researchers since the early 1950s. Customers increasingly expect to receive the right product, at the right price, at the right time. To meet these requirements, manufacturing companies need to improve their production scheduling performance. This talk investigates the application of particle swarm optimization and differential evolution in a multiple machine multi-objective scheduling environment. Production down time and sequence-dependent set-up times were also considered in this work. Various solution representations, and multi-objective optimization strategies were investigated and benchmarking against currently used algorithms on real customer data demonstrated significant performance improvement. 12th June. 2008. Jiawei Li (Michael): "An approach to accelerate heuristics for exam timetabling" The successful application of metaheuristic methods in exam timetabling problems shows that those good solutions for a specific timetabling have some common features. If the problems could be simplified according to these common features, good solutions would be kept in the reduced search space and then heuristic methods could be much efficiently not only in improving the speed of converging to a feasible solution but also that the quality of resulted timetable could be improved. In this talk, I am about to introduce a new approach that combines compatible examinations in order to accelerate both the initial timetable construction, as well as a later search. The conditions for combining exams are described, and we show that we are able to offer some guarantees as to the quality of solutions that remain in the reduced search space. The approach is applied to one of the standard benchmarks in this area; the St. Andrews83 instance. The results verify the effectiveness of this approach in simplifying examination timetabling problems, speeding up initial timetable construction and assisting any subsequent search. 5th June 2008. Mujgan Sagir: "Analytic Network Process, Multiobjective Educational Timetabling Problems and Approaches" This talk briefly summarizes the ongoing educational timetabling researches of the speaker. Besides, an introduction of the Analytic Network Process (ANP), the generalization of the Analytic Hierarchy Process (AHP), is given. The reason to introduce ANP here is the need to prioritize different criteria or multiple objectives of the optimization problems and ANP can be used for this purpose. Because the solution of any decision model strongly depends on its parameters, if the model does not represent the real problem, the outcome of the model may not be a valid one. Educational timetabling problems (ETP) are usually difficult to solve due to the complex and varied nature of them. Each system has its own constraints and therefore hard to get a general approach that will handle all type of problems. Besides 0-1 discreteness increases the complexity. We are interested in different types of educational timetabling problems as faculty-course, faculty-course-room, faculty-course-room-time slot, or invigilator assignments and also exam scheduling. They mostly have multiple and both qualitative and quantitative objectives. Two-phased solution methods (dividing the problem into two different sub problems which are then solved consecutively), a methodology for finding non-dominated solutions, considering participant preferences and using analytic network process are some topics characterize the solution approaches of our works. There are also on going researches with a research group of the speaker related to three dimensional pallet loading, open vehicle routing, and assortment problems. The total time (40-50 minutes) of the talk is going to be used by introducing the ANP, and the ETP researches of the speaker as about 20-25 minutes for each. |
| Comments to mvh at cs.nott.ac.uk |
