Proportional Optimization and Fairness (eBook)

Preface 7
Contents 12
List of Figures 17
List of Tables 19
Preliminaries 20
The Theory of Apportionment and Just-In-Time Sequences 23
2.1 Introduction 23
2.2 The Apportionment Problem 24
2.3 Which Apportionment? 25
2.4 Apportionment Methods 28
2.5 What is Impossible? 32
2.6 Coalitions and Schisms 36
2.7 From Apportionments to Just-In-Time Sequences 38
2.8 Which Just-In-Time Apportionments? 39
2.9 The Consistency ofWebster’s Method 45
2.10 Exercises 48
2.11 Comments and References 49
Minimization of Just-In-Time Sequence Deviation 50
3.1 Introduction 50
3.2 Minimization of Total Deviation 51
3.3 The Transformation to the Assignment Problem 52
3.4 The Monge Property of Assignment Costs 58
3.5 The Equivalence 63
3.6 The Solution 65
3.7 Minimization of Maximum Deviation 67
3.8 The Bottleneck Assignment 67
3.9 The Bottleneck Monge Property 69
3.10 Exercises 70
3.11 Comments and References 71
Optimality of Cyclic Sequences and the Oneness 72
4.1 Introduction 72
4.2 Symmetries of Cijks for Symmetric Fis 74
4.3 The Folding, Shuffling, and Unfolding of Sequences 82
4.4 Optimality of Cyclic Solutions for Total Deviation 88
4.5 Optimality of Cyclic Solutions for Maximum Deviation 89
4.6 The Oneness 93
4.7 Exercises 96
4.8 Comments and References 97
Bottleneck Minimization 98
5.1 Introduction 98
5.2 The PositionWindow Based Algorithm 99
5.3 The Complexity 104
5.4 Bounds on the Bottleneck 105
5.5 Main Properties 108
5.6 The Absence of Competition 109
5.7 Exercises 120
5.8 Comments and References 120
Competition-Free Instances, The Fraenkel’s Conjecture, and Optimal Admission Sequences 122
6.1 Introduction 122
6.2 The Competition-Free and the Power-of-Two Instances 124
6.3 Bottleneck of the Competition-Free Instances 125
6.4 Polygons of the Competition-Free Instances 128
6.5 Characteristics of Competition-Free Instances 132
6.6 The Competition-Free Instances for n = 3 135
6.7 Putting it Together 138
6.8 Fraenkel’s Conjecture and Competition-Free Instances 141
6.9 Regular Sequences and Multimodular Functions 145
6.10 Optimal Admission of Arrivals 150
6.11 Multimodular Function on Just-In-Time Sequences 153
6.12 Exercises 155
6.13 Comments and References 155
Response Time Variability 157
7.1 Introduction 157
7.2 Optimization and Complexity 160
7.3 Heuristics 173
7.4 Mathematical Programming Formulation 176
7.5 The Algorithm 180
7.6 Exercises 181
7.7 Comments and References 182
Applications to the Liu–Layland Problem and Pinwheel Scheduling 183
8.1 Introduction 183
8.2 The Liu–Layland Problem 184
8.3 Just-In-Time Solution of the Liu–Layland Problem 187
8.4 Divisor Methods for the Liu–Layland Problem 190
8.5 The Pinwheel Scheduling 197
8.6 Applications to Pinwheel Scheduling 200
8.7 Exercises 208
8.8 Comments and References 209
Temporal Capacity Constraints and Supply Chain Balancing 210
9.1 Introduction 210
9.2 The Car Sequencing Problem: A Model of Temporal Capacity Constraints 212
9.3 The Complexity of the Car Sequencing Problem 213
9.4 Dynamic Programming for the Car sequencing Problem 217
9.5 Simple Necessary Conditions 219
9.6 IP Formulation and Heuristics for the Car Sequencing Problem 220
9.7 Mixed-Model, Pull Supply Chains 222
9.8 Balanced Words and Model Delivery Sequences 224
9.9 Option Delivery Sequences 227
9.10 Periodic Synchronized Delivery 229
9.12 Exercises 238
9.13 Comments and References 239
Fair Queueing and Stride Scheduling 241
10.1 Introduction 241
10.2 The Story of Tiles: The Start, The Finish, or The In-Between 242
10.3 Fair Queueing 244
10.4 Which Queueing Fairness? 248
10.5 Stride Scheduling 253
10.6 Peer-To-Peer Fairness 258
10.7 Exercises 261
10.8 Comments and References 262
Smoothing and Batching 264
11.1 Introduction 264
11.2 A Real-Life System 267
11.3 Problem Definition 268
11.4 Pareto Optimization 274
11.5 Axiomatic Approach 276
11.6 EIP Method and Optimization 280
11.7 Computational Experiment 281
11.8 Exercises 284
11.9 Comments and References 285
References 286
Index 293