Handbook on Scheduling

by Blazewicz, J.

• ISBN13: 9783540280460
• ISBN10: 3540280464
• Format: Hardcover
• Copyright: 2007-09-03
• Publisher: Springer Verlag

Summary

This handbook covers not only in a unified approach the most important scheduling models and methods, it also put special emphasis to their relevance to practical situations. Many applications from industry and service operations management and case studies are described. Because the book offers some preliminaries concerning basic notions from discrete mathematics, it can also used by beginners. As a consequence, the handbook is an indispensable source for a broad audience, ranging from researchers to practitioners, graduate and advanced undergraduate students in computer science/engineering, operations research, industrial and real-time engineering, management science, business administration, information systems, and applied mathematics curricula.

Table of Contents

Introduction	p. 1
References	p. 7
Basics	p. 9
Sets and Relations	p. 9
Problems, Algorithms, Complexity	p. 11
Problems and Their Encoding	p. 11
Algorithms	p. 13
Complexity	p. 16
Graphs and Networks	p. 21
Basic Notions	p. 21
Special Classes of Digraphs	p. 22
Networks	p. 25
Enumerative Methods	p. 32
Dynamic Programming	p. 33
Branch and Bound	p. 33
Heuristic and Approximation Algorithms	p. 35
Approximation Algorithms	p. 35
Local Search Heuristics	p. 37
References	p. 52
Definition, Analysis and Classification of Scheduling Problems	p. 57
Definition of Scheduling Problems	p. 57
Analysis of Scheduling Problems and Algorithms	p. 62
Motivations for Deterministic Scheduling Problems	p. 65
Classification of Deterministic Scheduling Problems	p. 68
References	p. 71
Scheduling on One Processor	p. 73
Minimizing Schedule Length	p. 73
Scheduling with Release Times and Deadlines	p. 74
Scheduling with Release Times and Delivery Times	p. 81
Minimizing Mean Weighted Flow Time	p. 83
Minimizing Due Date Involving Criteria	p. 95
Maximum Lateness	p. 96
Number of Tardy Tasks	p. 104
Mean Tardiness	p. 109
Mean Earliness	p. 113
Minimizing Change-Over Cost	p. 114
Setup Scheduling	p. 114
Lot Size Scheduling	p. 117
Other Criteria	p. 122
Maximum Cost	p. 122
Total Cost	p. 127
References	p. 130
Scheduling on Parallel Processors	p. 137
Minimizing Schedule Length	p. 137
Identical Processors	p. 137
Uniform and Unrelated Processors	p. 158
Minimizing Mean Flow Time	p. 168
Identical Processors	p. 168
Uniform and Unrelated Processors	p. 169
Minimizing Due Date Involving Criteria	p. 173
Identical Processors	p. 173
Uniform and Unrelated Processors	p. 179
Other Models	p. 182
Scheduling Imprecise Computations	p. 182
Lot Size Scheduling	p. 185
References	p. 190
Communication Delays and Multiprocessor Tasks	p. 199
Introductory Remarks	p. 199
Scheduling Multiprocessor Tasks	p. 205
Parallel Processors	p. 205
Dedicated Processors	p. 213
Refinement Scheduling	p. 219
Scheduling Uniprocessor Tasks with Communication Delays	p. 221
Scheduling without Task Duplication	p. 222
Scheduling with Task Duplication	p. 225
Scheduling in Processor Networks	p. 226
Scheduling Divisible Tasks	p. 228
References	p. 236
Scheduling in Hard Real-Time Systems	p. 243
Introduction	p. 243
What is a Real-Time System?	p. 244
Examples of Real-Time Systems	p. 245
Characteristics of Real-Time Systems	p. 246
Functional Requirements for Real-Time Systems	p. 247
Basic Notations	p. 248
Structure of a Real-Time System	p. 248
The Task Model	p. 249
Schedules	p. 250
Single Processor Scheduling	p. 252
Static Priority Rules	p. 253
Dynamic Priority Scheduling	p. 262
Scheduling Periodic Tasks on Parallel Processors	p. 264
Resources	p. 265
Variations of the Periodic Task Model	p. 266
References	p. 267
Flow Shop Scheduling	p. 271
Introduction	p. 271
The Flow Shop Scheduling Problem	p. 271
Complexity	p. 273
Exact Methods	p. 274
The Algorithms of Johnson and Akers	p. 274
Dominance and Branching Rules	p. 277
Lower Bounds	p. 278
Approximation Algorithms	p. 282
Priority Rule and Local Search Based Heuristics	p. 282
Worst-Case Analysis	p. 285
No Wait in Process	p. 289
Scheduling Flexible Flow Shops	p. 291
Problem Formulation	p. 291
Heuristics and Their Performance	p. 294
A Model	p. 296
The Makespan Minimization Problem	p. 297
The Mean Flow Time Problem	p. 311
References	p. 316
Open Shop Scheduling	p. 321
Complexity Results	p. 321
A Branch and Bound Algorithm for Open Shop Scheduling	p. 323
The Disjunctive Model of the OSP	p. 323
Constraint Propagation and the OSP	p. 326
The Algorithm and Its Performance	p. 332
References	p. 341
Scheduling in Job Shops	p. 345
Introduction	p. 345
The Problem	p. 345
Modeling	p. 345
Complexity	p. 348
The History	p. 349
Exact Methods	p. 352
Branch and Bound	p. 353
Lower Bounds	p. 353
Branching	p. 355
Valid Inequalities	p. 358
Approximation Algorithms	p. 360
Priority Rules	p. 360
The Shifting Bottleneck Heuristic	p. 362
Opportunistic Scheduling	p. 365
Local Search	p. 367
Conclusions	p. 387
References	p. 388
Scheduling with Limited Processor Availability	p. 397
Problem Definition	p. 398
One Machine Problems	p. 401
Parallel Machine Problems	p. 403
Minimizing the Sum of Completion Times	p. 403
Minimizing the Makespan	p. 404
Dealing with Due Date Involving Criteria	p. 412
Shop Problems	p. 414
Flow Shop Problems	p. 414
Open Shop Problems	p. 417
Conclusions	p. 417
References	p. 419
Scheduling under Resource Constraints	p. 425
Classical Model	p. 425
Scheduling Multiprocessor Tasks	p. 436
Scheduling with Continuous Resources	p. 450
Introductory Remarks	p. 451
Processing Speed vs. Resource Amount Model	p. 452
Processing Time vs. Resource Amount Model	p. 461
Ready Time vs. Resource Amount Model	p. 466
References	p. 471
Constraint Programming and Disjunctive Scheduling	p. 477
Introduction	p. 477
Constraint Satisfaction	p. 479
The Constraint Satisfaction and Optimization Problem	p. 479
Constraint Propagation	p. 481
The Disjunctive Scheduling Problem	p. 493
The Disjunctive Model	p. 494
Solution Methods for the DSP	p. 497
Constraint Propagation and the DSP	p. 497
Some Basic Definitions	p. 498
Precedence Consistency Tests	p. 500
Lower-Level Bound-Consistency	p. 500
Input/Output Consistency Tests	p. 509
Input/Output Negation Consistency Tests	p. 516
Input-or-Output Consistency Tests	p. 522
Energetic Reasoning	p. 523
Shaving	p. 527
A Comparison of Disjunctive Consistency Tests	p. 528
Precedence vs. Disjunctive Consistency Tests	p. 530
Conclusions	p. 530
Appendix: Bound Consistency Revisited	p. 531
References	p. 535
Scheduling in Flexible Manufacturing Systems	p. 539
Introductory Remarks	p. 539
Scheduling Dynamic Job Shops	p. 542
Introductory Remarks	p. 542
Heuristic Algorithm for the Static Problem	p. 543
Computational Experiments	p. 549
Simultaneous Scheduling and Routing in some FMS	p. 550
Problem Formulation	p. 550
Vehicle Scheduling for a Fixed Production Schedule	p. 552
Simultaneous Job and Vehicle Scheduling	p. 557
Batch Scheduling in Flexible Flow Shops under Resource Constraints	p. 559
Introduction - Statement of the Problem	p. 559
Mathematical Formulation	p. 560
Heuristic Solution Approach	p. 570
Implementation and Computational Experiment	p. 577
References	p. 579
Computer Integrated Production Scheduling	p. 583
Scheduling in Computer Integrated Manufacturing	p. 584
A Reference Model for Production Scheduling	p. 589
IPS: An Intelligent Production Scheduling System	p. 597
Interactive Scheduling	p. 604
Knowledge-based Scheduling	p. 619
Integrated Problem Solving	p. 624
References	p. 628
Index	p. 631
Table of Contents provided by Ingram. All Rights Reserved.