Skip to main content
main-content

Über dieses Buch

Solving scheduling problems has long presented a challenge for computer scientists and operations researchers. The field continues to expand as researchers and practitioners examine ever more challenging problems and develop automated methods capable of solving them. This book provides 11 case studies in automated scheduling, submitted by leading researchers from across the world. Each case study examines a challenging real-world problem by analysing the problem in detail before investigating how the problem may be solved using state of the art techniques.The areas covered include aircraft scheduling, microprocessor instruction scheduling, sports fixture scheduling, exam scheduling, personnel scheduling and production scheduling. Problem solving methodologies covered include exact as well as (meta)heuristic approaches, such as local search techniques, linear programming, genetic algorithms and ant colony optimisation.The field of automated scheduling has the potential to impact many aspects of our lives and work; this book highlights contributions to the field by world class researchers.

Inhaltsverzeichnis

Frontmatter

Airport Airside Optimisation Problems

Abstract
This chapter aims to give the reader an accessible overview of airside airport operational research problems, with a particular focus upon runway scheduling, which is the subject of the case study. A number of problems are described, highlighting the direction of the research in each area and pointing the reader towards key publications where more information can be gained. Some of the surrounding problems are also outlined, to better understand the airport context. A case study is then provided, describing a system which was developed to aid runway controllers at Heathrow. Importantly, this considers a combination of two separate problems and the way in which these are simultaneously handled by the solution method. Results are provided for the presented case study, showing the potential benefits of decision support in that area. The chapter ends with a discussion of the likely ongoing importance of considering increasingly realistic objectives and constraints, of combining problems, and of targeting the environmental challenge at airports.
Jason A. D. Atkin

Instruction Scheduling in Microprocessors

Abstract
The Central Processing Unit (CPU) in a microprocessor is responsible for running machine instructions as fast as possible so that the machine performance is at its maximum level. While simple in design, in-order execution processors provide sub-optimal performance, because any delay in instruction processing blocks the entire instruction stream. To overcome this limitation, modern highperformance designs use out-of-order (OoO) instruction scheduling to better exploit available Instruction-Level Parallelism (ILP), and both static (compilerassisted) and dynamic (hardware-assisted) scheduling solutions are possible. The hardware-assisted scheduling integrates an OoO core that requires a complex dynamic instruction scheduler and additional datapath structures are utilized to hold the in-flight instructions in program order to support the reconstruction of precise program state. The logic becomes even more complex when superscalar (those capable of executing multiple instructions every clock cycle) designs are used. This chapter gives a brief introduction to instruction scheduling on pipelined superscalar architectures, and, then, explains some of the keystone static and dynamic instruction scheduling algorithms.
Gürhan Küçük, İsa Güney, Dmitry Ponomarev

Sports Scheduling: Minimizing Travel for English Football Supporters

Abstract
The football authorities in England are responsible for generating the fixtures for the entire football season but the fixtures that are played over the Christmas period are given special consideration as they represent the minimum distances that are traveled by supporters when compared with fixtures played at other times of the year. The distances are minimized at this time of the year to save supporters having to travel long distances during the holiday period, which often coincides with periods of bad weather. In addition, the public transport system has limited services on some of the days in question. At this time of the year every team is required to play, which is not always the case for the rest of the season.When every team is required to play, we refer to this as a complete fixture. Additionally, each team has to to play a home game and an away game. Therefore, over the Christmas period we are required to produce two complete fixtures, where each team has to have a Home/Away pattern of HA or AH. In some seasons four complete fixtures are generated where each team is required to have a Home/Away pattern of HAHA (or AHAH).Whether two or four fixtures are generated there are various other constraints that have to be respected. For example, the same teams cannot play each other and we have to avoid (as far as possible) having some teams play at home on the same day. This chapter has three main elements. i) An analysis of seven seasons to classify them as two or four fixture seasons. ii) The presentation of a single mathematical model that is able to generate both two and four fixture schedules which adheres to all the required constraints. Additionally, the model is parameterized so that we can conduct a series of experiments. iii) Demonstrating that the model is able to produce solutions which are superior to the solutions that were used in practise (the published fixtures) and which are also superior to our previous work. The solutions we generate are near optimal for the two fixture case. The four fixture case is more challenging and the solutions are about 16% of the lower bound. However, they are still a significant improvement on the fixtures that were actually used. We also show, through three experimental setups, that the problem owner might actually not want to accept the best solution with respect to the overall minimized distance but might want to take a slightly worse solution but which offers a guarantee as to the maximum distance that has to be traveled by the supporters within each division.
Graham Kendall, Stephan Westphal

Educational Timetabling

Abstract
This chapter is an introduction to the problems of timetabling educational institutions such as high schools and universities. These are large problems with multiple sources of NP-completeness, for which robust solvers do not yet exist, although steady progress is being made. This chapter presents the three main problems found in the literature: high school timetabling, university examination timetabling, and university course timetabling. It also examines some major subproblems of these problems: student sectioning, single student timetabling, and room assignment. This chapter also shows how real-world instances of these problems, with their many constraints, can be modelled in full detail, using a case study in high school timetabling as an example.
Jeffrey H. Kingston

Automated Shift Design and Break Scheduling

Abstract
Shift design and break scheduling are important employee scheduling problems that arise in many contexts, especially at airports, call centers, and service industries. The aim is to find a minimum number of legal shifts, the number of workers assigned to them, and a suitable number of breaks so that the deviation from predetermined workforce requirements is minimized. Such problems have been extensively investigated in Operations Research and recently have been also tackled with Artificial Intelligence techniques. In this chapter we outline major characteristics of these problems and provide a literature survey over solution techniques to solve them. We then describe in detail two state-of-the-art approaches based on local search techniques. Finally, we discuss our experiences with the application of one of these techniques in a real life case study.
Luca Di Gaspero, Johannes Gärtner, Nysret Musliu, Andrea Schaerf, Werner Schafhauser, Wolfgang Slany

Nurse Rostering: A Complex Example of Personnel Scheduling with Perspectives

Abstract
Nurse rostering is an attractive research domain due to its societal relevance, while academics are intrigued by its combinatorial complexity. Descriptions of nurse rostering problems vary largely across the literature, which makes it almost impossible to track down scientific advances of models and corresponding approaches. The present chapter introduces a mathematical formulation of a generic nurse rostering model. It provides common elements present in most nurse rostering research as well as important hospital constraints that are usually omitted from academic models. The new mathematical model satisfies all the basic requirements for future nurse rostering research and practical developments. Finally, the importance of public datasets is discussed, together with the characteristics of the various benchmark instances and research results obtained working on these instances.
Pieter Smet, Patrick De Causmaecker, Burak Bilgin, Greet Vanden Berghe

Radiotherapy Scheduling

Abstract
This chapter concerns radiotherapy scheduling problems identified at two cancer centres in the UK. The scheduling of radiotherapy pretreatment and treatment appointments is a complex problem due to various medical and scheduling constraints, such as patient category, machine availability, a doctors’ rota, waiting time targets (i.e., the time when a patient should receive the first radiotherapy fraction, etc.), and, also, due to the size of the problem (i.e., number of machines, facilities and patients). Different objectives need to be considered including minimisation of the number of patients who do not meet their waiting time targets, minimisation of usage of overtime slots, minimisation of machines idle time, and so on. Motivated by heuristics developed for production scheduling problems, two novel heuristics-based approaches to scheduling of radiotherapy patients are developed. Both approaches involve priority rules; while one of the approaches applies the a priori selected priority rules, the other one employs a genetic algorithm (GA) to select priority rules which will lead to the best scheduling performance. Different experiments are carried out to analyse the performance of the two radiotherapy scheduling approaches.
Dobrila Petrovic, Elkin Castro, Sanja Petrovic, Truword Kapamara

Recent Advances in Evolutionary Algorithms for Job Shop Scheduling

Abstract
Scheduling decides the order of tasks to efficiently use resources considering criteria such as minimization of the number of late tasks, minimization of the completion time, minimization of the idle times of the machines, etc. Approaches for solving scheduling problems can be divided into three broad groups: (a) exact methods that produce exact optimal solutions, (b) approximation methods that find high quality near optimal, and (c) hybrid methods based on the first two. Approximate methods can be easily combined with other types of heuristics and can be applied to a wide range of problems.
In the category of approximation algorithms, evolutionary algorithms (EAs) are very promising tools for the problems with dynamic characteristics, contradicting multi-objectives and highly nonlinear constraints. For EAs to be effective and efficient for a combinatorial optimisation problem like scheduling, the structure of an EA needs to be designed carefully to exploit the problem structures. An appropriate representation for the problem and the type of search operators suitable for the representation should be studied because they directly affect the search efficiency of the EA.
In this chapter, our focus will be on EAs for job shop scheduling problems (JSP). First, JSP will be formulated as an optimization problem and approaches for JSP will be given briefly. Second, EAs will be introduced and the key issues in the application of EAs for JSP will be emphasized. Third, various representations used in EAs for handling JSP will be described and advantages and drawbacks of different representations will be described based on the results from the literature. Forth, crossover and mutation operators designed for particular representations will be illustrated and their strength and limitations will be discussed. Almost all successful applications of evolutionary combinatorial optimisation include some kind of hybrid algorithms, where both EAs and local search were used. The seventh topic of this chapter is devoted to local search strategies which are frequently integrated into EAs.
Bahriye Akay, Xin Yao

Multi-objective Grid Scheduling

Abstract
Grid computing is a distributed paradigm that coordinates heterogeneous resources using decentralized control. Grid computing is commonly used by scientists for executing experiments. Scheduling jobs within Grid environments is a challenging task. Scientists often need to ensure not only a successful execution for their experiments but also they have to satisfy constraints such as deadlines or budgets. Both of these constraints, execution time and cost, are not trivial to satisfy, as they are conflict with each other, eg cheaper resources are usually slower than expensive ones. Hence, a multi-objective scheduling optimization is a more challenging task in Grid infrastructures. This chapter presents a new multi-objective approach, MOGSA (Multi-Objective Gravitational Search Algorithm), based on the gravitational search behaviour in order to optimize both objectives, execution time and cost, with the same importance and also at the same time. Two studies are carried out in order to evaluate the quality of this new approach for grid scheduling. Firstly, MOGSA is compared with the multiobjective standard and well-known NSGA-II (Non-Dominated Sorting Genetic Algorithm II) to prove the multi-objective optimization suitability of the proposed algorithm. Secondly two real grid schedulers (WMS and DBC) are also compared with MOGSA. TheWMS (WorkloadManagement System) is considered because of it is part of the most used European grid middleware - gLite - and also the DBC (Deadline Budget Constraint) algorithm from Nimrod-G participates in this evaluation due to its good performance keeping the deadline and budget per job. Results point out the superiority of MOGSA in all the studies carried out. MOGSA offers more quality solutions than NSGA-II and also better performance than current real schedulers.
María Arsuaga-Ríos, Miguel A. Vega-Rodríguez

Dynamic Multi-objective Job Shop Scheduling: A Genetic Programming Approach

Abstract
Handling multiple conflicting objectives in dynamic job shop scheduling is challenging because many aspects of the problem need to be considered when designing dispatching rules. A multi-objective genetic programming based hyperheuristic (MO-GPHH) method is investigated here to facilitate the designing task. The goal of this method is to evolve a Pareto front of non-dominated dispatching rules which can be used to support the decision makers by providing them with potential trade-offs among different objectives. The experimental results under different shop conditions suggest that the evolved Pareto front contains very effective rules. Some extensive analyses are also presented to help confirm the quality of the evolved rules. The Pareto front obtained can cover a much wider ranges of rules as compared to a large number of dispatching rules reported in the literature.Moreover, it is also shown that the evolved rules are robust across different shop conditions.
Su Nguyen, Mengjie Zhang, Mark Johnston, Kay Chen Tan

Dynamic Vehicle Routing: A Memetic Ant Colony Optimization Approach

Abstract
Over the years, several variations of the dynamic vehicle routing problem (DVRP) have been considered due to its similarities with many real-world applications. Several methods have been applied to address DVRPs, in which ant colony optimization (ACO) has shown promising results due to its adaptation capabilities. In this chapter, we generate another variation of the DVRP with traffic factor and propose a memetic algorithm based on the ACO framework to address it. Multiple local search operators are used to improve the exploitation capacity and a diversity scheme based on random immigrants is used to improve the exploration capacity of the algorithm. The proposed memetic ACO algorithm is applied on different test cases of the DVRP with traffic factors and is compared with other peer ACO algorithms. The experimental results show that the proposed memetic ACO algorithm shows promising results.
Michalis Mavrovouniotis, Shengxiang Yang

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise