Approximation in batch and multiprocessor scheduling [Elektronische Ressource] / Tim Nonner

Sujets

• Informatik

Informations

• Publié par: albert-ludwigs-universitat_freiburg
• Publié le: 01 janvier 2010
• Nombre de lectures: 9
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

.
Approximation in Batch and
Multiprocessor Scheduling
Dissertation
zur Erlangung des Doktorgrades
der Technischen Fakultat¨
der Albert-Ludwigs-Universitat¨
Freiburg im Breisgau
Tim Nonner
Dezember 2010Albert-Ludwigs-Universit¨at Freiburg
Technische Fakultat¨
Dekan: Prof. Dr. Bernd Becker
Referent: Prof. Dr. Susanne Albers
Koreferent: Prof. Dr. Sven O. Krumke
Tag der Promotion: 3. Dezember 2010Abstract
This thesis is about scheduling problems where jobs arrive over time. Depending
ontheproblem,weconsiderthecasethateachjobhasadeadline,ortherelaxation
thatthesumofflowtimesorcompletiontimesneedtobeminimized. Sincemostof
thediscussedproblemsareNP-hard,thegoalistofindpolynomialtimealgorithms
with provable approximation guarantee, preferably in an on-line setting.
In the first part of this thesis, we consider batch scheduling problems for the case
that each job has a deadline, and hence two jobs may be added to the same batch
if their due intervals intersect. We first present a framework that unifies all batch
cost structures discussed in this part. For instance max-batching, where the cost
of each batch is the maximum weight of any contained job. We show that max-
batchingisstronglyNP-hardinthiscontextifthesizeofeachbatchisadditionally
restricted by a constant capacity constraint, and we also give a polynomial time
approximation scheme (PTAS) for this case. Moreover, we consider a minmax-
variant of max-batching which finds application in the area of data aggregation.
We show that this variant is strongly NP-hard as well, and we present a quasi-
polynomial time approximation scheme (QPTAS) and moreover a PTAS for the
case that the due interval lengths are constants. Finally, we show that the closely
related batch cost structure used in joint replenishment results in an APX-hard
problem, which is hence not likely to admit an approximation scheme, but we
show that it admits a randomized 5/3-approximation algorithm. The results of
this part are published in [1, 2, 3, 4].
Inthesecondpartofthisthesis,multiprocessorschedulingproblemsarediscussed.
We give the first proof that the competitive ratio of the well-known algorithm
SRPT is strictly smaller than 2 for completion time scheduling on identical ma-
chines. Specifically, we give the upper bound 1:86. Since it is harder to find
approximation guarantees for flow time scheduling, we investigate this case in the
context of speed-scaling, where it is allowed to arbitrarily increase the speed of
each processor subject to some reasonable penalty. For this model, we present
a general approach to transform single processor algorithms into multiprocessor
algorithms. This yields new or improved constant approximation guarantees for
basicallyallvariantsofspeed-scaled multiprocessorscheduling. Theresultsofthis
part are published in [5, 6].Acknowledgement
I would like to thank my advisor Prof. Susanne Albers for her trust to let me
pursue independent research during my three years in Freiburg. Furthermore, I
would like to thank Prof. Sven Krumke for accepting the burden of being the
second corrector and Maxim Sviridenko for offering me the possibility to spend
some thrilling months in the Theory Group of the IBM T.J. Watson Research
Center near NYC.
Thisthesiswouldnothavebeenpossiblewithoutthemanyhoursoffruitfuldiscus-
sions with my coauthors. I am especially indebted to my long-term collaborator
Alexander Souza for countless debates, usually first in the office, and then in
the beer gardens around Freiburg. If he would not have been around to discuss
half-baked ideas during my first two years, I would have surely dropped out in
frustration. Thanks also to all the other people that moved through our depart-
ment for their pleasant company, namely Gero Greiner, Fabian Schiller, Christian
Gunia, Tobias Jacobs, Stefan Eilts, SonjaLauer, andmy next-door neighbors An-
nette Bieniusa and Markus Degen. Another thanks goes to Prof. Riedmiller and
his nice group for giving me a new home in my third year when I was literally on
my own.
Throughout my thesis, I was gratefully supported by the DFG graduate school
Embedded Microsystems,which includedageneroustravelbudgetthatallowedme
to present work at numerous conferences. Thanks also to Manuela Kniss for her
patientadministrativesupportandWolfgangPaulatfortakingcareofalltechnical
matters. Finally, I would like to thank my parents for always encouraging me to
follow my interests.Contents
1 Introduction 9
1.1 Scheduling with Release Times . . . . . . . . . . . . . . . . . . . 10
1.2 Approximation and Competitive Analysis . . . . . . . . . . . . . . 11
1.3 Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I Batch Scheduling 15
2 Introduction to Batch Scheduling 17
2.1 Model and Definitions . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Chain and Minsum 23
3.1 Geometric Interpretation . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Application in Max-Batching . . . . . . . . . . . . . . . . . . . . 24
3.3 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 A Unified Approach for k <1 . . . . . . . . . . . . . . . . . . . 26
3.5 Dynamic Programming for k =1 . . . . . . . . . . . . . . . . . . 27
3.6 On-line Algorithms for all k . . . . . . . . . . . . . . . . . . . . . 29
3.7 A PTAS for k <1 . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.7.1 Trading Nodes for Accuracy . . . . . . . . . . . . . . . . . 33
3.7.2 Interpretation of a Schedule as a Function . . . . . . . . . 36
3.7.3 Easy Instances . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7.4 Normal Schedules . . . . . . . . . . . . . . . . . . . . . . . 38
3.7.5 A Quasipolynomial Time Algorithm for Easy Instances . . 41
3.7.6 A QPTAS . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.7.7 A PTAS for Easy Instances . . . . . . . . . . . . . . . . . 45
3.7.8 Partial Schedules . . . . . . . . . . . . . . . . . . . . . . . 47
3.7.9 Trading Tuples A for Accuracy . . . . . . . . . . . . . . . 483.7.10 Trading Integer Tuples a for Accuracy . . . . . . . . . . . 52
3.8 NP-Hardness for k <1 . . . . . . . . . . . . . . . . . . . . . . . 58
4 Chain and Minmax 65
4.1 Application in Data Aggregation . . . . . . . . . . . . . . . . . . 65
4.1.1 Transit Times . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.1.2 Flow Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 A QPTAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.1 Trading Nodes for Accuracy . . . . . . . . . . . . . . . . . 68
4.3.2 Dynamic Programming . . . . . . . . . . . . . . . . . . . . 70
4.4 A PTAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.4.1 Normal Schedules . . . . . . . . . . . . . . . . . . . . . . . 71
4.4.2 Exponential Growth . . . . . . . . . . . . . . . . . . . . . 73
4.4.3 Decomposition . . . . . . . . . . . . . . . . . . . . . . . . 76
4.4.4 Iterated Rounding . . . . . . . . . . . . . . . . . . . . . . 78
4.4.5 Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.5 NP-Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5 Shallow Tree and Minsum 87
5.1 Application in Joint Replenishment . . . . . . . . . . . . . . . . . 87
5.1.1 Period-Indexed Delay Costs and Demands . . . . . . . . . 88
5.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.3 A 5/3-Approximation Algorithm . . . . . . . . . . . . . . . . . . . 89
5.3.1 LP-Formulation and Continuous Schedules . . . . . . . . . 90
5.3.2 Greedy Selection of Retailer Orders . . . . . . . . . . . . . 93
5.3.3 Selecting Warehouse Orders as a Grid. . . . . . . . . . . . 94
5.3.4 The Generalized Tally Game . . . . . . . . . . . . . . . . . 95
5.3.5 Random Selection of Warehouse Orders . . . . . . . . . . . 98
5.4 APX-hardness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6 Conclusion and Open Problems 105
II Multiprocessor Scheduling 107
7 Introduction to Multiprocessor Scheduling 109
7.1 Model and Definitions . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 Outline. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1128 SRPT and Completion Time Scheduling 115
8.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.1.1 Weighted Completion Time . . . . . . . . . . . . . . . . . 115
8.1.2 Flow Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.2 Discrete Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.3 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.4 SRPT is 1:86-Competitive . . . . . . . . . . . . . . . . . . . . . . 118
8.4.1 Basic Operations . . . . . . . . . . . . . . . . . . . . . . . 122
08.4.2 Merging and to Form . . . . . . . . . . . . . . . . 129
8.4.3 Construction of from . . . . . . . . . . . . . . . . . . 132
08.4.4 Merging and to Form . . . . . . . . . . . . . . . . . 135
8.4.5 Analysis of Δ via Two Potentials . . . . . . . . . . . . . . 137
9 Speed-Scaling 143
9.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.1.1 Speed-Scaling vs. Speed Augmentation . . . . . .