Kubiak Proportional Optimization and Fairness

1. Auflage 2008
ISBN: 978-0-387-87719-8
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 290 Seiten

Proportional Optimization and Fairness is a long-needed attempt to reconcile optimization with apportionment in just-in-time (JIT) sequences and find the common ground in solving problems ranging from sequencing mixed-model just-in-time assembly lines through just-in-time batch production, balancing workloads in event graphs to bandwidth allocation internet gateways and resource allocation in computer operating systems. The book argues that apportionment theory and optimization based on deviation functions provide natural benchmarks for a process, and then looks at the recent research and developments in the field. Individual chapters look at the theory of apportionment and just-in-time sequences; minimization of just-in-time sequence deviation; optimality of cyclic sequences and the oneness; bottleneck minimization; competition-free instances, Fraenkel's Conjecture, and optimal admission sequences; response time variability; applications to the Liu-Layland Problem and pinwheel scheduling; temporal capacity constraints and supply chain balancing; fair queuing and stride scheduling; and smoothing and batching.

Autoren/Hrsg.

Kubiak, Wieslaw

Inhaltsverzeichnis

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