Three Essays on Operations Scheduling with Job Classes and Time Windows E-Book

Alexander Lieder

• Herausgeber: Books on Demand
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 156

Veröffentlichungsjahr: 2016

Beschreibung

This book contains the three scientific essays that constitute the PhD dissertation of Alexander Lieder: [1] A Dynamic Programming Approach for the Aircraft Landing Problem with Aircraft Classes (also published in: European Journal of Operational Research) [2] Scheduling Aircraft Take-Offs and Landings on Heterogeneous and Interdependent Runways (also published in: Transportation Research Part E: Logistics and Transportation Review) [3] Task Scheduling in Long-Term Care Facilities: A Client-Centered approach (also published in: Operations Research for Health Care)

Leseprobe

UNIVERSITÄT MANNHEIM

BETRIEBSWIRTSCHAFTSLEHRE

Inauguraldissertation

zur Erlangung des akademischen Grades

eines Doktors der Wirtschaftswissenschaften

der Universität Mannheim

vorgelegt von

Dekan:

Dr. Jürgen M. Schneider

Referent:

Prof. Dr. Raik Stolletz

Korreferent:

Prof. Dr. Cornelia Schön

Tag der mündlichen Prüfung:

27. November 2015

Contents

Summary

List of Figures

List of Tables

List of Acronyms

1 Introduction

2 A dynamic programming approach for the aircraft landing problem with aircraft classes

2.1 Introduction

2.2 Problem definition

2.2.1 Problem description

2.2.2 MIP model

2.3 Dynamic programming approach

2.3.1 States and transitions

2.3.2 State-space reduction using a dominance criterion

2.4 Numerical study

2.4.1 Performance analysis

2.4.2 Sensitivity analysis

2.4.3 Impact of state space reduction

2.5 Implementation via a rolling horizon approach

2.6 Conclusions and further research

3 Scheduling aircraft take-offs and landings on heterogeneous and interdependent runways

3.1 Introduction

3.2 Related literature

3.2.1 Overview of models

3.2.2 Solution approaches

3.3 Model description

3.4 Dynamic programming approach

3.4.1 State definition

3.4.2 State transition

3.4.3 Dominance rule

3.5 Rolling planning horizon heuristic

3.6 Numerical study

3.6.1 Generation of problem instances

3.6.2 Performance analysis of the exact DP approach

3.6.3 General runway configurations

3.6.4 Rolling planning horizon heuristic

3.7 Consideration of costs for taxiing

3.8 Conclusion and outlook

4 Task scheduling in long-term care facilities: A client-centered approach

4.1 Introduction

4.2 Related literature

4.2.1 Research in nursing homes

4.2.2 Research on task scheduling problems

4.3 Problem description and model formulation

4.4 Dynamic programming approach

4.4.1 States and transitions

4.4.2 State space reduction

4.4.3 Heuristic solution approaches

4.5 Numerical study

4.5.1 Study design

4.5.2 Comparison of solution approaches

4.5.3 Impact of skill substitution

4.5.4 Economies of scale

4.6 Conclusions and further research

5 Conclusions and outlook

5.1 Conclusions

5.2 Further research directions

Bibliography

Appendix 1: Detailed numerical results from Chapter 3

Appendix 2: Source code of the DP approach for the generalized ASP

Curriculum Vitae

Acknowledgements

This dissertation is the result of more than four years that I spent as a research assistant and doctoral candidate at the Chair of Production Management at the University of Mannheim. During this time, I could rely on a number of coauthors, who delivered invaluable input the research articles enclosed in this dissertation. Of course, I would like to start with my supervisor Professor Raik Stolletz, whom I would like to thank for his guidance and support. His combined qualities of being quite demanding and sometimes difficult to convince on the one hand but understanding and supportive on the other were certainly a decisive success factor of this entire project. Of course, I also want to thank my other co-authors: Professor Dirk Briskorn who, together with Raik Stolletz, laid the theoretic foundations of my essential optimization approach and therefore made all of my findings possible in the first place and who was always available for discussing new ideas and helping to resolve problems, and Dennis Moeke and Professor Ger Koole from the VU University in Amsterdam, who were very pleasant and diligent work partners as well as excellent hosts during my brief research visits to their beautiful city.

It is my pleasure to extend my greetings and thanks to my dear colleagues, who mostly came to Mannheim from other parts of the country like I did and who became not only valuable work partners but also close friends that I had lots of good times with and that I could always count on (in no particular order): Hendrik Guhlich, Justus Arne Schwarz, Gregor Selinka, Andrej Saweljew, Emilio Zamorano, Axel Franz, Sophie Weiss, Annika Becker, Semën Nikolajewsi, and Jannik Vogel. I wish them all the best for their own dissertation and/or habilitation projects and their future careers, and I hope we stay in touch. I would also like to thankfully mention the other chairs of the Area Operations Management whose chair holders and research assistants were always pleasant colleagues who gave helpful input to my research on numerous occasions, and Christian Weitert and Oliver Schmitzer who introduced me to living and working in Mannheim and who made my first months here quite enjoyable.

At least as important for the success of this project as an outstanding working environment was that I could always count on the unconditional love and support from my family and friends: From my beloved significant other Lavinia, my parents Frank and Eva, my brother Stefan and his family, and from my friends back home in North Rhine-Westphalia who actually took the time to travel to Mannheim for the occasional visits which were always a great pleasure. Thank you.

Finally, I would like to thank the Erich Becker Foundation, a foundation of the FraPort AG, in Frankfurt am Main. From 2013 to 2015, their stipend for aviation-related research projects granted me substantial financial support that made it possible for me to visit fellow researchers and scientific conferences across Europe in order to present and discuss my research. For more information on the Erich Becker Foundation I gladly refer to their web site, www.erich-becker-stiftung.de.

Mannheim, September 2015,

Alexander Lieder

Summary

Operations scheduling is the assignment of individual tasks to resources and the definition of start times for all tasks. It encompasses the problems of task assignment and sequencing. Goals of operations scheduling are the adherence to service targets and an efficient usage of constrained resources. Therefore, well-planned schedules can significantly contribute to a company’s success. This dissertation presents optimization approaches for three single-stage scheduling problems with multiple resources, job classes, and time windows from two different areas of application.

The first essay discusses the aircraft landing problem (ALP) that emerges at highly utilized airports. A set of aircraft is approaching the airport and to each aircraft a runway and a landing time have to be assigned. The goal is to minimize the weighted sum of delays from the aircraft’s target landing times while maintaining the necessary separation between all pairs of landings. We provide an efficient dynamic programming-based optimization approach for this problem while most other authors restrict themselves to heuristic solution approaches. The second essay generalizes this solution approach in order to solve the ALP under more realistic constraints. It takes aircraft take-offs as well as runway systems with heterogeneous and interdependent runways into account. The third essay provides an exact solution approach for a task scheduling problem in a long-term care facility that, from a mathematical point of view, has similarities with the ALP. A set of care tasks must be assigned to a set of care workers while meeting the respective clients’ preferred task start times as closely as possible. Different from the ALP, tasks can be scheduled earlier than their target time and require the care worker to have at least a certain qualification level.

In the absence of other optimization approaches for the considered scheduling problems in the literature, in our numerical studies we compare the performance of our approaches to a standard solver and to basic dispatching rules. For problem instances that cannot be solved efficiently with the proposed optimization approaches, we provide heuristic solution approaches based on state space truncation and on a rolling planning horizon.

List of Figures

2.1 Distribution of target landing times and aircraft classes

3.1 Example of a basic problem instance with solutions

3.2 Schematic representation of Frankfurt Airport (Germany)

4.1 Examples of sub-optimal task assignments

4.2 Convex, piecewise linear penalty function

5.1 UML class diagram of the DP’s data structure

List of Tables

2.1 Separation requirements (in seconds)

2.2 Overview of related articles

2.3 Sets, parameters, and variables of the MIP model

2.4 Standard problem instances from Bianco et al. (1999)

2.5 Comparison of computation times for 10 problem instances and 4 cost functions

2.6 Computation times for the different problem sizes (in seconds)

2.7 Computation times for the different interarrival times (in seconds)

2.8 Impact of the state-space reduction on computation time and state space

3.1 Separation requirements (in seconds)

3.2 Overview of related Literature with heterogeneous or interdependent runways

3.3 Overview of related Literature with single or independent runways (2010–2015)

3.4 Sets, parameters, and variables of the MIP formulation

3.5 Example application of the dominance rule

3.6 Distribution of operation classes (w(a))

3.7 Basic problem cases: Impact of runway load

3.8 Basic problem cases: Impact of planning horizon

3.11 Rolling planning horizon heuristic for FRA’s runway setting

3.12 Impact of taxi costs

4.1 Overview of care worker qualification levels

4.2 Sets, parameters, and variables of the MIP

4.3 Properties of the problem instances

4.4 Comparison of solution approaches

4.5 Impact of skill substitution

4.6 Economies of scale

5.1 Basic setting (2 interdep. runways; diag. sep. 40 sec.)

5.2 Basic setting (2 independent runways)

5.3 Basic setting (2 interdep. runways; diag. sep. 40 sec.)

5.4 Basic problem setting with taxi costs

List of Acronyms

ACO

Ant colony optimization

ADP

Approximate dynamic programming

ALNS

Adaptive large neighborhood search

ALP

Aircraft Landing Problem

ASP

Aircraft Scheduling Problem

ATFM

Air traffic flow management

B&B

Branch-and-Bound

CP

Constraint programming

CPS

Constrained position shifting

DMU

Decision making unit

DP

Dynamic program(ming)

FAA

US Federal Aviation Administration

FCFS

First come, first served

HC

Hill climbing

GA

Genetic algorithm

ICAO

International Civil Aviation Organization

ILS

Iterated local search

IP

Integer program(ming)

MIP

Mixed integer program(ming)

MU

Monetary unit

QL

Qualification level

ROP

Resource occupation profile

RPH

Rolling planning horizon

SA

simulated annealing

TMA

Terminal Maneuvering Area

VI

Valid inequalities

VNS

Variable neighborhood search

1 Introduction

The problem of operations scheduling emerges wherever goods are produced or services are provided. In the hierarchical planning framework of a company it is found on the lowest level as it is the planning step with the shortest planning horizon but the highest level of detail. Operations scheduling assigns individual tasks, such as an elementary step in a production or service delivery process, to a resource, such as a worker or a machine, and defines a start time for each task, i.e., it encompasses the planning problems of task assignment (“who does what”) and sequencing (“in which order”). It is straightforward to show that scheduling problems are inherently difficult: If we assume a single-stage scheduling problem with m resources and n tasks, there are up to n! sequences for the tasks to be performed and mn ways to assign the tasks to resources. Nevertheless, well-planned schedules are essential for a company’s success as they contribute to the adherence to service targets and to an efficient usage of constrained resources.

In this dissertation, we present efficient dynamic programming-based optimization approaches for three single-stage scheduling problems with multiple resources, job classes, and time windows that emerge in practice in two areas of application: Chapters 2 and 3 address the aircraft landing problem (ALP) and the aircraft scheduling problem (ASP), respectively, that emerge at highly utilized airports. Chapter 4 addresses a task scheduling problem in a long-term care facility. To cope with the high difficulty of scheduling problems, we exploit the properties of the particular problems to develop specialized solution approaches that derive optimal schedules significantly faster than a standard solver can. For the scheduling problems under consideration, standard solution approaches such as Branch-&-Bound that are implemented in standard solvers like CPLEX are very inefficient and require prohibitive computation times to derive optimal schedules for problem instances of realistic size.

The first article of this dissertation (Chapter 2) presents an efficient optimization approach for the ALP with aircraft classes. The article was co-authored by Dirk Briskorn and Raik Stolletz.1 In the ALP, a set of aircraft is approaching an airport and to each aircraft a runway and a landing time have to be assigned. The goal is to minimize the weighted sum of delays from the aircraft’s target landing times while maintaining sequence-dependent minimum separation times between all pairs of consecutive landings on the same runway. Delayed aircraft landings incur high expenditures for airlines, passengers, airport operators, and air traffic controllers (Cook and Tanner, 2011).

We make the realistic assumption, that the set of aircraft can be divided into a small number of aircraft classes with the same delay cost function and the same separation requirements. A previous article on the ALP by Briskorn and Stolletz (2014) discusses the theoretical complexity of this problem and outlines an exact dynamic programming (DP) approach. A straightforward implementation of their approach, however, results in excessive computation times even for small problem instances. A thorough examination of the DP’s state space reveals a high level of symmetry and redundancy. The optimization approach proposed in this article makes use of a new dominance criterion to curtail the size of the state space while maintaining optimality. We perform extensive numerical tests on an implementation of the approach to demonstrate its efficiency. We use standard problem instances from the literature and a large set of generated problem instances with realistic assumptions and show that the DP with the proposed dominance criterion outperforms a standard solver. In the subsequent chapters of this dissertation, two different generalizations of the proposed optimization approach are developed.

The second article (Chapter 3), co-authored by Raik Stolletz,2 takes additional constraints into account that apply to the ALP in practice: Many airports have parallel or intersecting runways that cannot be operated independently, or heterogenous runways, i.e., not all runways can be used by all aircraft classes. Also, if both aircraft take-offs and landings are considered, the official separation requirements issued by aviation authorities do not fulfill the triangle inequality. Therefore, separation must also be ensured between pairs of non-consecutive operations and between pairs of operations on different runways. As both take-offs and landings are considered, we refer to this problem as ASP instead of ALP. As the ASP has been subject to a large number of papers published over the recent years, this article also provides an extensive review of recent related literature. None of the reviewed papers proposes an efficient and exact solution approach for the discussed problem setting. The new, generalized optimization approach proposed in this chapter considers interdependent and heterogeneous runways as well as non-triangular separation times. The state space, the state transitions, and the dominance rule of the DP are redefined accordingly. Due to the additional information that the DP requires in each state, the complexity of this approach is higher compared to the approach proposed in Chapter 2. The numerical tests, however, show that it is still efficient for many realistic problem instances.

In practice, fast solutions for the ASP are essential as air traffic controllers need information in near real time. To derive fast solutions for problem instances that require too much computation time to be solved to optimality, we propose a rolling planning horizon (RPH) heuristic that decomposes the problem into a series of smaller, interconnected problems that are solved iteratively. The performance of the generalized optimization approach and of the RPH heuristic is tested on a large set of problem instances, assuming realistic runway systems with interdependent and heterogeneous runways such as London-Heathrow and Frankfurt Airport. While the ASP is intractable for a standard solver, the DP approach solves most instances in less than one minute. The problem instances that feature the runway system and the traffic density of Frankfurt Airport take several minutes to be solved to optimality. For these instances, however, the RPH heuristic returns optimal or close-tooptimal results within significantly reduced computation times. On average, the weighted sum of delays can be reduced to approximately one third compared to first-come-first-served (FCFS) runway schedules as applied in practice.

The third article of this dissertation (Chapter 4), co-authored by Dennis Moeke, Ger Koole, and Raik Stolletz,3 discusses a scheduling problem from a different area of application: We consider a long-term care facility for elderly people. The residents of this facility have demand for various care tasks at specified times throughout the day. Each task has to be assigned to a care worker with the respective qualification level while meeting the respective client’s preferred start time as closely as possible. Although the demographic change in Europe suggests that elderly care will gain much importance in the near future, the amount of research on service delivery in long-term care facilities is very limited. The literature review presents previous research on such facilities and on related task scheduling problems, but no related article addresses the problem at hand.

From a mathematical point of view, this task scheduling problem shares some properties with the ALP discussed in Chapter 2: the preferred task start times correspond to the target landing times of the set of aircraft and the workforce performing the tasks corresponds to the runway system handling the landings. The problem differs from the ALP in the following aspects: The care workers have hierarchical qualification levels, i.e., highly qualified workers can perform tasks with low qualification requirements, but not vice versa. Also, tasks can be scheduled to start before their target time with a respective earliness penalty. The task durations are not sequence-dependent but the number of different task types, each defined by task duration and required qualification level, is much higher than the number of aircraft classes in typical ALP instances.

To optimally solve the task scheduling problem, we generalize the DP approach for the ALP presented in Chapter 2. The generalized approach allows the assignment of early task start times and considers the heterogeneous workforce with hierarchical qualification levels. New feasibility and dominance checks are introduced that increase the computational performance. Especially the possibility of early task start times significantly increases the DP’s state space and the computation time. Therefore, we introduce a heuristic DP with a truncated state space to solve instances with otherwise prohibitive computation times. In the numerical study, we derive optimal and heuristic task schedules for real-world problem instances provided by a Dutch long-term care facility. Compared to an FCFS scheduling policy, we achieve an improved performance in terms of total deviation from the client’s preferred task start times. The truncated DP returns close-to-optimal schedules.