Introduction to Scheduling

by Robert; Yves

• ISBN13: 9781420072730
• ISBN10: 1420072730
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-11-18
• Publisher: CRC Press

Summary

Reviewing classical methods as well as realistic models and algorithms, this book offers a through introduction to scheduling presented by highly respected experts. It covers fundamental concepts and basic methods, as well as recent research and applications with a special focus on distributed systems and computational grids, Topics covered include online scheduling, stochastic task-resource systems, and platform models. Though the book takes a rigorous approach, it provides enough background to be self-contained and fully accessible to computer scientists, mathematicians, and researchers in related fields. Examples, theorems, and pedagogical proofs are provided to create an interactive learning format.

Table of Contents

Preface	p. xi
Acknowledgments	p. xvii
List of.Contributors	p. xix
On the Complexity of Scheduling	p. 1
Introduction	p. 1
Scheduling Models	p. 2
Processor (Machine) Scheduling	p. 6
Easy and Hard Problems	p. 11
Complexity Classification of Scheduling Problems	p. 18
References	p. 20
Approximation Algorithms for Scheduling Problems	p. 23
Introduction	p. 23
Approximation Algorithms	p. 24
Definitions	p. 25
Absolute Approximation Algorithms (Case pinf = pSUp)	p. 26
A Fully Polynomial-Time Approximation Scheme	p. 28
Introduction of Precedence Constraints	p. 31
Unbounded Number of Processors	p. 31
Bounded Number of Processors	p. 31
Introduction of Communication Delays	p. 32
Introduction	p. 32
Unbounded Number of Processors	p. 33
Limited Number of Processors	p. 37
Introduction of Duplication	p. 42
Large Communication Delays	p. 44
Conclusion	p. 47
References	p. 48
Online Scheduling	p. 51
Introduction	p. 51
Classical Scheduling Problems	p. 52
Makespan Minimization	p. 52
Flow Time Objectives	p. 57
Load Balancing	p. 60
Energy-Efficient Scheduling	p. 62
Power-Down Mechanisms	p. 63
Dynamic Speed Scaling	p. 67
Conclusion	p. 73
References	p. 73
Job Scheduling	p. 79
Introduction	p. 79
Single Machine Problems	p. 82
Makespan Problems on Parallel Machines	p. 86
Completion Time Problems on Parallel Machines	p. 91
Conclusion	p. 99
References	p. 100
Cyclic Scheduling	p. 103
Introduction	p. 103
Cyclic Scheduling and Uniform Constraints	p. 104
Common Features of Cyclic Scheduling Problems	p. 104
Uniform Task Systems	p. 106
Questions	p. 108
Periodic Schedules of Uniform Task Systems	p. 109
Properties of Periodic Schedules	p. 109
Critical Circuit of a Strongly Connected Graph	p. 112
Computation of an Optimal Periodic Schedule	p. 113
Earliest Schedule of Uniform Task Systems	p. 116
Periodic Schedules of Uniform Task Systems with Resource Constraints	p. 117
Which Periodicity?	p. 117
Complexity and Iteration Vectors	p. 118
Patterns and Iteration Vectors	p. 119
Decomposed Software Pipelining: A Generic Approach	p. 121
Dynamic Schedules	p. 124
Conclusion	p. 125
References	p. 126
Cyclic Scheduling for the Synthesis of Embedded Systems	p. 129
Introduction	p. 129
Problem Formulation and Basic-Notations	p. 131
Synchronous Dataflow Graphs	p. 131
Timed Weighted Event Graphs	p. 132
Problem Formulation	p. 133
Precedence Relations Induced by a Timed Marked WEG	p. 134
Characterization of Precedence Relations	p. 134
Timed Event Graphs	p. 135
Equivalent Places	p. 135
Unitary WEGs	p. 137
Definitions	p. 138
Normalization of a Unitary WEG	p. 139
Expansion of a Unitary Timed Marked WEG	p. 141
Relationship between Expansion and Normalization	p. 145
Periodic Schedule of a Normalized Timed Marked WEG	p. 147
Periodic Schedules	p. 148
Properties of Periodic Schedules	p. 148
Existence of Periodic Schedules	p. 150
Optimal Periodic Schedule	p. 152
Conclusion	p. 154
References	p. 154
Steady-State Scheduling	p. 159
Introduction	p. 159
Problem Formulation	p. 161
Platform Model	p. 161
Applications	p. 162
Compact Description of a Schedule	p. 163
Definition of the Allocations	p. 164
Definition of Valid Patterns	p. 166
From Allocations and Valid Patterns to Schedules	p. 167
Conditions and Weak Periodic Schedules	p. 167
Weak Periodic Schedules and Cyclic Scheduling	p. 169
Problem Solving in the General Case	p. 172
Existence of a Compact Solution	p. 173
Resolution with the Ellipsoid Method	p. 175
Separation in the Dual Linear Program	p. 176
Toward Compact Linear Programs	p. 178
Introduction	p. 178
Efficient Computation of Valid Patterns under the Bidirectional One-Port Model	p. 179
Efficient Computation of Allocations	p. 182
Conclusion	p. 184
References	p. 185
Divisible Load Scheduling	p. 187
Introduction	p. 187
Motivating Example	p. 188
Classical Approach	p. 188
Divisible Load Approach	p. 191
Bus-Shaped Network	p. 192
Star-Shaped Network	p. 195
Extensions of the Divisible Load Model	p. 201
Introducing Latencies	p. 201
Multi-Round Strategies	p. 204
Return Messages	p. 214
Conclusion	p. 216
References	p. 217
Multi-Objective Scheduling	p. 219
Motivation	p. 220
Once Upon a Time	p. 220
Diversity of Objectives	p. 221
Motivating Problems	p. 222
Summary of Results on Single Objective Problems	p. 223
Beyond the Scope of This, This Chapter	p. 223
Chapter Organization	p. 224
What Is Multi-Objective Optimization?	p. 225
Overview of the Various Existing Approaches	p. 228
Algorithms Building One Trade-off Solution	p. 228
Complexity Issues	p. 230
Zenith Approximation on MaxAndSum	p. 233
Pareto Set Approximation on EfficientReliable	p. 235
Motivation	p. 235
Definition of Pareto Set Approximation	p. 236
The Thresholding Approach	p. 237
Fairness as Multi-Objective Optimization	p. 241
The Meaning of Fairness	p. 241
Axiomatic Theory of Fairness	p. 242
Application to Two Agent MinSum	p. 243
Problems with Different Objective Functions	p. 245
Aggregative Fairness	p. 246
Conclusion	p. 247
References	p. 248
Comparisons of Stochastic Task-Resource Systems	p. 253
Motivation	p. 253
Task-Resource Models	p. 255
Static Systems	p. 255
Dynamic Systems	p. 256
Stochastic Orders	p. 257
Orders for Real Random Variables	p. 258
Orders for Multidimensional Random Variables	p. 263
Association	p. 264
Applications to Static Problems	p. 265
The 1 ¿Ci Problem, Revisited	p. 266
PERT Graphs	p. 267
Applications to Dynamic Systems	p. 268
Single Queues	p. 269
Networks of Queues	p. 272
Stochastic Comparisons and Simulation Issues	p. 275
References	p. 279
The Influence of Platform Models on Scheduling Techniques	p. 281
Introduction	p. 281
Platform Modeling	p. 282
Modeling the Topology	p. 282
Modeling Point-to-Point Communication Time	p. 284
Heterogeneity	p. 288
Modeling Concurrent Communications	p. 289
Interaction between Communication and Computation	p. 291
Scheduling Divisible Load	p. 292
Single Round	p. 293
Multi-Round	p. 296
Iterative Algorithms on a Virtual Ring	p. 298
Problem Statement	p. 299
Complete Homogeneous Platform	p. 299
Complete Heterogeneous Platform	p. 300
Arbitrary Heterogeneous Platform	p. 301
Data Redistribution	p. 302
The Matching Approach	p. 304
The Elastic Flows Approach	p. 306
Conclusion	p. 307
References	p. 307
Index	p. 311
Table of Contents provided by Ingram. All Rights Reserved.