Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010251031 | QA76.9.D5 I673 2010 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Full of practical examples, Introduction to Scheduling presents the basic concepts and methods, fundamental results, and recent developments of scheduling theory. With contributions from highly respected experts, it provides self-contained, easy-to-follow, yet rigorous presentations of the material.
The book first classifies scheduling problems and their complexity and then presents examples that demonstrate successful techniques for the design of efficient approximation algorithms. It also discusses classical problems, such as the famous makespan minimization problem, as well as more recent advances, such as energy-efficient scheduling algorithms. After focusing on job scheduling problems that encompass independent and possibly parallel jobs, the text moves on to a practical application of cyclic scheduling for the synthesis of embedded systems. It also proves that efficient schedules can be derived in the context of steady-state scheduling. Subsequent chapters discuss scheduling large and computer-intensive applications on parallel resources, illustrate different approaches of multi-objective scheduling, and show how to compare the performance of stochastic task-resource systems. The final chapter assesses the impact of platform models on scheduling techniques.
From the basics to advanced topics and platform models, this volume provides a thorough introduction to the field. It reviews classical methods, explores more contemporary models, and shows how the techniques and algorithms are used in practice.
Author Notes
Yves Robert is a professor in the computer science laboratory at the École Normale Supérieure de Lyon in France. Dr. Robert is also a senior member of the Institut Universitaire de France.
Frédéric Vivien is a researcher at INRIA in France. Dr. Vivien's research interests include scheduling techniques and parallel algorithms for heterogeneous and distributed platforms.
Table of Contents
Preface | p. xi |
Acknowledgments | p. xvii |
List of.Contributors | p. xix |
1 On the Complexity of Scheduling | p. 1 |
1.1 Introduction | p. 1 |
1.2 Scheduling Models | p. 2 |
1.3 Processor (Machine) Scheduling | p. 6 |
1.4 Easy and Hard Problems | p. 11 |
1.5 Complexity Classification of Scheduling Problems | p. 18 |
References | p. 20 |
2 Approximation Algorithms for Scheduling Problems | p. 23 |
2.1 Introduction | p. 23 |
2.1.1 Approximation Algorithms | p. 24 |
2.1.2 Definitions | p. 25 |
2.1.3 Absolute Approximation Algorithms (Case pinf = pSUp) | p. 26 |
2.2 A Fully Polynomial-Time Approximation Scheme | p. 28 |
2.3 Introduction of Precedence Constraints | p. 31 |
2.3.1 Unbounded Number of Processors | p. 31 |
2.3.2 Bounded Number of Processors | p. 31 |
2.4 Introduction of Communication Delays | p. 32 |
2.4.1 Introduction | p. 32 |
2.4.2 Unbounded Number of Processors | p. 33 |
2.4.3 Limited Number of Processors | p. 37 |
2.4.4 Introduction of Duplication | p. 42 |
2.4.5 Large Communication Delays | p. 44 |
2.5 Conclusion | p. 47 |
References | p. 48 |
3 Online Scheduling | p. 51 |
3.1 Introduction | p. 51 |
3.2 Classical Scheduling Problems | p. 52 |
3.2.1 Makespan Minimization | p. 52 |
3.2.2 Flow Time Objectives | p. 57 |
3.2.3 Load Balancing | p. 60 |
3.3 Energy-Efficient Scheduling | p. 62 |
3.3.1 Power-Down Mechanisms | p. 63 |
3.3.2 Dynamic Speed Scaling | p. 67 |
3.4 Conclusion | p. 73 |
References | p. 73 |
4 Job Scheduling | p. 79 |
4.1 Introduction | p. 79 |
4.2 Single Machine Problems | p. 82 |
4.3 Makespan Problems on Parallel Machines | p. 86 |
4.4 Completion Time Problems on Parallel Machines | p. 91 |
4.5 Conclusion | p. 99 |
References | p. 100 |
5 Cyclic Scheduling | p. 103 |
5.1 Introduction | p. 103 |
5.2 Cyclic Scheduling and Uniform Constraints | p. 104 |
5.2.1 Common Features of Cyclic Scheduling Problems | p. 104 |
5.2.2 Uniform Task Systems | p. 106 |
5.2.3 Questions | p. 108 |
5.3 Periodic Schedules of Uniform Task Systems | p. 109 |
5.3.1 Properties of Periodic Schedules | p. 109 |
5.3.2 Critical Circuit of a Strongly Connected Graph | p. 112 |
5.3.3 Computation of an Optimal Periodic Schedule | p. 113 |
5.4 Earliest Schedule of Uniform Task Systems | p. 116 |
5.5 Periodic Schedules of Uniform Task Systems with Resource Constraints | p. 117 |
5.5.1 Which Periodicity? | p. 117 |
5.5.2 Complexity and Iteration Vectors | p. 118 |
5.5.3 Patterns and Iteration Vectors | p. 119 |
5.5.4 Decomposed Software Pipelining: A Generic Approach | p. 121 |
5.6 Dynamic Schedules | p. 124 |
5.7 Conclusion | p. 125 |
References | p. 126 |
6 Cyclic Scheduling for the Synthesis of Embedded Systems | p. 129 |
6.1 Introduction | p. 129 |
6.2 Problem Formulation and Basic-Notations | p. 131 |
6.2.1 Synchronous Dataflow Graphs | p. 131 |
6.2.2 Timed Weighted Event Graphs | p. 132 |
6.2.3 Problem Formulation | p. 133 |
6.3 Precedence Relations Induced by a Timed Marked WEG | p. 134 |
6.3.1 Characterization of Precedence Relations | p. 134 |
6.3.2 Timed Event Graphs | p. 135 |
6.3.3 Equivalent Places | p. 135 |
6.4 Unitary WEGs | p. 137 |
6.4.1 Definitions | p. 138 |
6.4.2 Normalization of a Unitary WEG | p. 139 |
6.4.3 Expansion of a Unitary Timed Marked WEG | p. 141 |
6.4.4 Relationship between Expansion and Normalization | p. 145 |
6.5 Periodic Schedule of a Normalized Timed Marked WEG | p. 147 |
6.5.1 Periodic Schedules | p. 148 |
6.5.2 Properties of Periodic Schedules | p. 148 |
6.5.3 Existence of Periodic Schedules | p. 150 |
6.5.4 Optimal Periodic Schedule | p. 152 |
6.6 Conclusion | p. 154 |
References | p. 154 |
7 Steady-State Scheduling | p. 159 |
7.1 Introduction | p. 159 |
7.2 Problem Formulation | p. 161 |
7.2.1 Platform Model | p. 161 |
7.2.2 Applications | p. 162 |
7.3 Compact Description of a Schedule | p. 163 |
7.3.1 Definition of the Allocations | p. 164 |
7.3.2 Definition of Valid Patterns | p. 166 |
7.4 From Allocations and Valid Patterns to Schedules | p. 167 |
7.4.1 Conditions and Weak Periodic Schedules | p. 167 |
7.4.2 Weak Periodic Schedules and Cyclic Scheduling | p. 169 |
7.5 Problem Solving in the General Case | p. 172 |
7.5.1 Existence of a Compact Solution | p. 173 |
7.5.2 Resolution with the Ellipsoid Method | p. 175 |
7.5.3 Separation in the Dual Linear Program | p. 176 |
7.6 Toward Compact Linear Programs | p. 178 |
7.6.1 Introduction | p. 178 |
7.6.2 Efficient Computation of Valid Patterns under the Bidirectional One-Port Model | p. 179 |
7.6.3 Efficient Computation of Allocations | p. 182 |
7.7 Conclusion | p. 184 |
References | p. 185 |
8 Divisible Load Scheduling | p. 187 |
8.1 Introduction | p. 187 |
8.1.1 Motivating Example | p. 188 |
8.1.2 Classical Approach | p. 188 |
8.2 Divisible Load Approach | p. 191 |
8.2.1 Bus-Shaped Network | p. 192 |
8.2.2 Star-Shaped Network | p. 195 |
8.3 Extensions of the Divisible Load Model | p. 201 |
8.3.1 Introducing Latencies | p. 201 |
8.3.2 Multi-Round Strategies | p. 204 |
8.3.3 Return Messages | p. 214 |
8.4 Conclusion | p. 216 |
References | p. 217 |
9 Multi-Objective Scheduling | p. 219 |
9.1 Motivation | p. 220 |
9.1.1 Once Upon a Time | p. 220 |
9.1.2 Diversity of Objectives | p. 221 |
9.1.3 Motivating Problems | p. 222 |
9.1.4 Summary of Results on Single Objective Problems | p. 223 |
9.1.5 Beyond the Scope of This, This Chapter | p. 223 |
9.1.6 Chapter Organization | p. 224 |
9.2 What Is Multi-Objective Optimization? | p. 225 |
9.3 Overview of the Various Existing Approaches | p. 228 |
9.3.1 Algorithms Building One Trade-off Solution | p. 228 |
9.3.2 Complexity Issues | p. 230 |
9.4 Zenith Approximation on MaxAndSum | p. 233 |
9.5 Pareto Set Approximation on EfficientReliable | p. 235 |
9.5.1 Motivation | p. 235 |
9.5.2 Definition of Pareto Set Approximation | p. 236 |
9.5.3 The Thresholding Approach | p. 237 |
9.6 Fairness as Multi-Objective Optimization | p. 241 |
9.6.1 The Meaning of Fairness | p. 241 |
9.6.2 Axiomatic Theory of Fairness | p. 242 |
9.6.3 Application to Two Agent MinSum | p. 243 |
9.6.4 Problems with Different Objective Functions | p. 245 |
9.6.5 Aggregative Fairness | p. 246 |
9.7 Conclusion | p. 247 |
References | p. 248 |
10 Comparisons of Stochastic Task-Resource Systems | p. 253 |
10.1 Motivation | p. 253 |
10.2 Task-Resource Models | p. 255 |
10.2.1 Static Systems | p. 255 |
10.2.2 Dynamic Systems | p. 256 |
10.3 Stochastic Orders | p. 257 |
10.3.1 Orders for Real Random Variables | p. 258 |
10.3.2 Orders for Multidimensional Random Variables | p. 263 |
10.3.3 Association | p. 264 |
10.4 Applications to Static Problems | p. 265 |
10.4.1 The 1 ¿Ci Problem, Revisited | p. 266 |
10.4.2 PERT Graphs | p. 267 |
10.5 Applications to Dynamic Systems | p. 268 |
10.5.1 Single Queues | p. 269 |
10.5.2 Networks of Queues | p. 272 |
10.5.3 Stochastic Comparisons and Simulation Issues | p. 275 |
References | p. 279 |
11 The Influence of Platform Models on Scheduling Techniques | p. 281 |
11.1 Introduction | p. 281 |
11.2 Platform Modeling | p. 282 |
11.2.1 Modeling the Topology | p. 282 |
1l.2.2 Modeling Point-to-Point Communication Time | p. 284 |
11.2.3 Heterogeneity | p. 288 |
11.2.4 Modeling Concurrent Communications | p. 289 |
11.2.5 Interaction between Communication and Computation | p. 291 |
11.3 Scheduling Divisible Load | p. 292 |
11.3.1 Single Round | p. 293 |
11.3.2 Multi-Round | p. 296 |
11.4 Iterative Algorithms on a Virtual Ring | p. 298 |
11.4.1 Problem Statement | p. 299 |
11.4.2 Complete Homogeneous Platform | p. 299 |
11.4.3 Complete Heterogeneous Platform | p. 300 |
11.4.4 Arbitrary Heterogeneous Platform | p. 301 |
11.5 Data Redistribution | p. 302 |
11.5.1 The Matching Approach | p. 304 |
11.5.2 The Elastic Flows Approach | p. 306 |
11.6 Conclusion | p. 307 |
References | p. 307 |
Index | p. 311 |