Handbook of Scheduling: Algorithms, Models, and Performance Analysis

✍ Scribed by James H. Anderson, Joseph Y-T. Leung

• Publisher: Chapman and Hall/CRC
• Year: 2004
• Tongue: English
• Leaves: 1139
• Edition: 1
• Category: Library

✦ Synopsis

Over the past few years, the field of scheduling has changed dramatically because of the complexity of the problems now involved. This has led many researchers to develop approximation algorithms that can handle these more difficult kinds of scheduling problems. This in turn has resulted in enormous growth of the field and a wide body of knowledge that has never been pulled together into one volume-until now. Handbook of Scheduling: Algorithms, Models, and Performance Analysis collects all of the up-to-date information on approximation algorithms into one resource that will prove useful to a wide range of users from computer science, industrial engineering, operations research, and management science.

✦ Table of Contents

Handbook of Scheduling......Page 1
© 2004 by CRC Press LLC......Page 4
Dedication......Page 5
Preface......Page 6
The Editor......Page 7
Contributors......Page 8
Contents......Page 12
1 Introduction and Notation......Page 18
I Introduction......Page 17
References......Page 25
2.2 Time Complexity of Algorithms......Page 27
2.2.1 Bubble Sort......Page 28
2.3 Polynomial Reduction......Page 29
2.3.5 0/1-Knapsack Decision......Page 30
2.4 NP-Completeness and NP-Hardness......Page 35
2.5 Pseudo-Polynomial Algorithms and Strong NP-Hardness......Page 36
2.6 PTAS and FPTAS......Page 38
References......Page 40
3 Some Basic Scheduling Algorithms......Page 41
References......Page 57
II Classical Scheduling Problems......Page 59
4.1 Introduction......Page 61
4.2 A Brief State of the Art......Page 62
4.3 Elimination Rules: Basic Concepts......Page 65
4.4 Extensions......Page 68
4.5 Local Shaving......Page 72
4.6 Computational Experiments......Page 73
4.7 Conclusion......Page 76
References......Page 77
5 Flexible Hybrid Flowshops......Page 80
6 Open Shop Scheduling......Page 113
7 Cycle Shop Scheduling......Page 127
References......Page 146
8 Reducibility among Scheduling Classes......Page 149
9.1 Introduction......Page 191
9.2 Some Basic Algorithms and Relationships......Page 192
9.3 Preemptive Scheduling......Page 193
9.4 Nonpreemptive Scheduling......Page 194
9.5 Scheduling with Precedence Constraints......Page 196
References......Page 197
10.1 Introduction......Page 201
10.2 Single Machine Problems without Release Dates......Page 202
10.3 Single Machine Problems with Release Dates......Page 203
10.4 Parallel Machine Problems......Page 207
References......Page 210
15......Page 211
39......Page 212
11.1 Introduction......Page 213
11.2 Algorithms for Problems with Precedence Constraints......Page 215
11.3 Unrelated Machines......Page 228
11.4 Approximation Schemes for Problems with Release Dates......Page 231
11.5 Conclusions and Open Problems......Page 238
References......Page 239
8......Page 240
32......Page 241
57......Page 242
12.1 Introduction......Page 243
12.2 Minimizing the Number of Late Jobs on a Single Machine......Page 244
12.3 Minimizing the Weighted Number of Tardy Jobs......Page 248
12.4 Scheduling with Release Dates......Page 250
12.5 Scheduling with Deadlines......Page 253
12.6 Scheduling on m Parallel Machines......Page 255
References......Page 259
13.1 Introduction......Page 260
13.2 Branch-and-Bound Procedure......Page 262
13.4 No-Good Recording......Page 263
13.6 Local Dominance Properties......Page 264
13.7 Dominance Rule Relying on Scheduled Jobs......Page 266
13.8 Dominance Rules Relying on Unscheduled Jobs......Page 267
13.9 Comparing Dominance Rules with Previous
Ones......Page 274
13.10 Look-Ahead Propagation Rule......Page 275
13.11 Experimental Results......Page 276
References......Page 279
18......Page 280
14.1 Single Machine Problems......Page 282
14.2 Identical Parallel Machine Problems......Page 290
14.3 Summary of Complexity Results......Page 314
References......Page 316
15 Online Scheduling......Page 319
16 Convex Quadratic
Relaxations in
Scheduling......Page 362
III
Other
Scheduling
Models......Page 377
45 University Timetabling......Page 980