ISBN: 3790815160
TITLE: Contributions to Economics
AUTHOR: Dondorf
TOC:

1 Introduction 1
1 l Motivation and Objectives 1
1.2 Outline 4
2 Optimisation Model 7
2.1 The General Single-Mode Model 8
2.1.1 Activities and Resources 8
2.1.2 Temporal Constraints 9
2 1 3 The Model 13
2.1.4 Schedules and Performance Measures 14
2.1.5 Domains of Decision Variables 15
2.1.6 Special Cases 15
2.2 Extension to Multiple Execution Modes 16
2.2.1 Modes 16
2.2.2 Resources 17
2 2 3 The Model 18
3 Constraint Propagation 19
3.1 Constraint Satisfaction and Optimisation 19
3.1.1 The Constraint Satisfaction Problem 20
3.1.2 The Constraint Optimisation Problem 21
3.1.3 Constraint Graphs 21
3.2 Concepts of Consistency 22
3.2.1 k-Consistency 22
3.2.2 Domain-Consistency 24
3.2.3 Bound Consistency 24
3.3 Consistency Checking 25
3.3.1 Consistency Tests 25
3.3.2 Consistency Checking Algorithms 26
3.3.3 Uniqueness of the Fixed Point 28
3.4 Constraint Programming 29
4 Consistency Tests 31
4.1 Basic Concepts 32
4.2 Consistency Tests for Temporal Constraints 34
4.3 Interval Consistency 36
4.4 Disjunctive Sub-Problems 38
4.4.1 Disjunctive Activity Pairs 38
4.4.2 Selection of Disjunctive Sub-Problems 40
4.5 Disjunctive Interval Consistency Tests 41
4.5.1 Input/Output Test 41
4.5.2 Input-or-Output Test 45
4.5.3 Input/Output Negation Test 48
4.5.4 Summary and Generalisation 49
4.5.5 Relation to Interval Consistency 50
4.5.6 Lower Level Consistency 52
4.5.7 Sequence Consistency Does Not Imply k-b-Consistency 54
4.5.8 Shaving 55
4.6 Cumulative Interval Consistency Tests 56
4.6.1 Unit-Interval Consistency 56
4.6.2 Activity Interval Consistency 57
4.6.3 Minimum Slack Intervals 60
4.6.4 Fully and Partially Elastic Relaxations 61
4.7 Multi-Mode Consistency Tests 62
4.8 Summary 64
5 A Branch-and-Bound Algorithm 67
5.1 Previous Solution Approaches 68
5.2 Constraint Propagation 70
5.2.1 Consistency Tests 70
5.2.2 Some Properties of the Earliest Start Times 70
5.3 The Branch-and-Bound Algorithm 71
5.3.1 The Branching Scheme 71
5.3.2 Upper and Lower Bounds 77
5.3.3 Some Properties of Active Schedules 78
5.4 Computational Experiments 80
5.4.1 Implementation of the Algorithm 80
5.4.2 Bidirectional Planning 80
5.4.3 Characteristics of the Test Sets 81
5.4.4 Experiments for the Problem PS|temp|C_max 83
5.4.5 Experiments for the Problem PS|prec|C_max 93
5.5 Summary 100
6 Multi-Mode Extension of the Branch-and-Bound Algorithm 103
6.1 Previous Work 103
6.2 Constraint Propagation 105
6.3 Extended Branching Scheme 105
7 Applications in Airport Operations Management 109
7.1 Scheduling of Ground Handling Operations 110
7.2 Gate Scheduling 112
7.2.1 Introduction 112
7.2.2 Literature Review 115
7.2.3 Problem Description 116
7.2.4 Constraint Propagation 124
7.2.5 A Branch-and-Bound Algorithm 124
7.2.6 Lower Bounds 127
7.2.7 Problem Partitioning 129
7.2.8 Layered Branch-and-Bound 133
7.2.9 Large Neighbourhood Search 135
7.2.10 Computational Experiments 136
8 Summary and Conclusions 143
List of Figures 147
List of Tables 149
List of Symbols 151
References 155
END
