Blazewicz / Blazewicz / Ecker Handbook on Scheduling

From Theory to Applications
1. Auflage 2007
ISBN: 978-3-540-32220-7
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 647 Seiten

Reihe: International Handbooks on Information Systems

This book provides a theoretical and application-oriented analysis of deterministic scheduling problems in advanced planning and computer systems. The text examines scheduling problems across a range of parameters: job priority, release times, due dates, processing times, precedence constraints, resource usage and more, focusing on such topics as computer systems and supply chain management. Discussion includes single and parallel processors, flexible shops and manufacturing systems, and resource-constrained project scheduling. Many applications from industry and service operations management and case studies are described. The handbook will be useful to a broad audience, from researchers to practitioners, graduate and advanced undergraduate students.

Autoren/Hrsg.

Blazewicz, Jacek

Ecker, Klaus H.

Pesch, Erwin

Schmidt, Günter

Weglarz, Jan

Inhaltsverzeichnis

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