Handbook on Scheduling (eBook)

FOREWORD 6
Contents 7
1 Introduction 13
2 Basics 21
2.1 Sets and Relations 21
2.2 Problems, Algorithms, Complexity 23
2.3 Graphs and Networks 33
2.4 Enumerative Methods 44
2.5 Heuristic and Approximation Algorithms 47
3 Definition, Analysis and Classification of Scheduling Problems 69
3.1 Definition of Scheduling Problems 69
3.2 Analysis of Scheduling Problems and Algorithms 74
3.3 Motivations for Deterministic Scheduling Problems 77
3.4 Classification of Deterministic Scheduling Problems 80
4 Scheduling on One Processor 85
4.1 Minimizing Schedule Length 85
4.2 Minimizing Mean Weighted Flow Time 95
4.3 Minimizing Due Date Involving Criteria 107
4.4 Minimizing Change-Over Cost 126
4.5 Other Criteria 134
5 Scheduling on Parallel Processors 149
5.1 Minimizing Schedule Length 149
5.2 Minimizing Mean Flow Time 180
5.3 Minimizing Due Date Involving Criteria 185
5.4 Other Models 194
6 Communication Delays and Multiprocessor Tasks 210
6.1 Introductory Remarks 210
6.2 Scheduling Multiprocessor Tasks 216
6.3 Scheduling Uniprocessor Tasks with Communication Delays 232
6.4 Scheduling Divisible Tasks 239
7 Scheduling in Hard Real-Time Systems 253
7.1 Introduction 253
7.2 Basic Notions 258
7.3 Single Processor Scheduling 262
7.4 Scheduling Periodic Tasks on Parallel Processors 274
7.5 Resources 275
7.6 Variations of the Periodic Task Model 276
8 Flow Shop Scheduling 280
8.1 Introduction 280
8.2 Exact Methods 283
8.3 Approximation Algorithms 291
8.4 Scheduling Flexible Flow Shops 300
9 Open Shop Scheduling 330
9.1 Complexity Results 330
9.2 A Branch and Bound Algorithm for Open Shop ScheduUng 332
10 Scheduling in Job Shops 353
10.1 Introduction 353
10.2 Exact Methods 360
10.3 Approximation Algorithms 368
10.4 Conclusions 395
11 Scheduling with Limited Processor Availability 405
11.1 Problem Definition 406
11.2 One Machine Problems 409
11.3 Parallel Machine Problems 411
11.4 Shop Problems 422
11.5 Conclusions 425
12 Scheduling under Resource Constraints 433
12.1 Classical Model 433
12.2 Scheduling Multiprocessor Tasks 444
12.3 Scheduling with Continuous Resources 458
13 Constraint Programming and Disjunctive Scheduling 484
13.1 Introduction 484
13.2 Constraint Satisfaction 486
13.3 The Disjunctive Scheduling Problem 500
13.4 Constraint Propagation and the DSP 504
13.5 Conclusions 537
13.6 Appendix: Bound Consistency Revisited 538
14 Scheduling in Flexible Manufacturing Systems 546
14.1 Introductory Remarks 546
14.2 Scheduling Dynamic Job Shops 549
14.3 Simultaneous Scheduling and Routing in some FMS 557
14.4 Batch Scheduling in Flexible Flow Shops under Resource Constraints 566
15 Computer Integrated Production Scheduling 590
15.1 Scheduling in Computer Integrated Manu-facturing 591
15.2 A Reference Model for Production Scheduling 596
15.3 IPS: An Intelligent Production Scheduling System 604
Index 638