Scheduling in Computer and Manufacturing Systems
1st Edition
Published on 10. November 1992
Book
Hardback
IX, 311 pages
978-3-540-55958-0 (ISBN)
Description
This text provides a theoretical and application-oriented analysis of deterministic scheduling problems arising in computer and manufacturing environments. In such systems, processors (machines) and possible other resources are to be allocated among tasks in such a way that certain scheduling objectives are met. Various scheduling problems are discussed where different problem parameters such as task processing times, urgency weights, arrival times, deadlines, precedence constraints and processor speed factors are involved. Polynomial and exponential time optimization algorithms as well as approximation and heuristic approaches are presented and discussed in the context of particular problems. The most important classical results are surveyed, with particular attention paid to single-processor scheduling. Then more general models are studied, including parallel processors, resource-constrained scheduling, flexible flow shops, dynamic job shops, and flexible manufacturing systems. Besides the algorithmic approach, a general knowledge-based tool is presented for solving a broad class of practical scheduling problems.
For the presentation of algorithms, a PASCAL-like notation is chosen and used in almost all cases. For the convenience of less advanced readers, basic concepts from scheduling theory and related areas such as computational complexity analysis are included.
For the presentation of algorithms, a PASCAL-like notation is chosen and used in almost all cases. For the convenience of less advanced readers, basic concepts from scheduling theory and related areas such as computational complexity analysis are included.
More details
Language
English
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
College/higher education
Professional and scholarly
Research
Illustrations
97 s/w Abbildungen, 12 s/w Tabellen
97 illustrations, 12 tables
Dimensions
Height: 24.2 cm
Width: 17 cm
Weight
645 gr
ISBN-13
978-3-540-55958-0 (9783540559580)
DOI
10.1007/978-3-662-00074-8
Schweitzer Classification
Other editions
New editions
Jacek Blazewicz | Klaus H. Ecker | Günter Schmidt
Scheduling in Computer and Manufacturing Systems
Book
07/1994
2nd Edition
Springer
€85.55
Article exhausted; check different version
Additional editions
Jacek Blazewicz | Klaus Ecker | Günter Schmidt
Scheduling in Computer and Manufacturing Systems
E-Book
12/2012
1st Edition
Springer
€85.59
Available for download
Content
1 Introduction.- References.- 2 Preliminaries.- 2.1 Sets and Relations.- 2.2 Problems, Algorithms, Complexity.- 2.2.1 Problems and their Encoding.- 2.2.2 Algorithms.- 2.2.3 Complexity.- 2.3 Graphs and Networks.- 2.3.1 Basic Notions.- 2.3.2 Special Classes of Digraphs.- 2.3.3 Networks.- 2.4 Enumerative Methods.- 2.4.1 Dynamic Programming.- 2.4.2 Branch and Bound.- 2.5 Heuristic and Approximation Algorithms.- References.- 3 Formulation of Scheduling Problems.- 3.1 Definition of Scheduling Problems.- 3.2 Analysis of Scheduling Problems and Algorithms.- 3.3 Motivations for Deterministic Scheduling Problems.- 3.4 Classification of Deterministic Scheduling Problems.- References.- 4 Single Processor Scheduling.- 4.1 Minimizing Schedule Length.- 4.1.1 Scheduling with Release Times and Deadlines.- 4.1.2 Scheduling with Release Times and Delivery Times.- 4.2 Minimizing Mean Weighted Flow Time.- 4.3 Minimizing Due Date Involving Criteria.- 4.3.1 Maximum Lateness.- 4.3.2 Number of Tardy Tasks.- 4.3.3 Tardiness Problems.- 4.3.4 Earliness and Lateness Problems.- 4.4 Other Criteria.- 4.4.1 Minimizing Maximum Cost.- 4.4.2 Minimizing Mean Cost.- 4.5 Minimizing Change-Over Cost.- 4.5.1 Setup Scheduling.- 4.5.2 Lot Size Scheduling.- References.- 5 Parallel Processor Scheduling.- 5.1 Minimizing Schedule Length.- 5.1.1 Identical Processors.- 5.1.2 Uniform and Unrelated Processors.- 5.2 Minimizing Mean Flow Time.- 5.2.1 Identical Processors.- 5.2.2 Uniform and Unrelated Processors.- 5.3 Minimizing Due Date Involving Criteria.- 5.3.1 Identical Processors.- 5.3.2 Uniform and Unrelated Processors.- 5.4 Other Models.- 5.4.1 Semi-Identical Processors.- 5.4.2 Scheduling Multiprocessor Tasks.- References.- 6 Static Shop Scheduling.- 6.1 Flow Shop Scheduling.- 6.2 Open Shop Scheduling.- 6.3 Job Shop Scheduling.- 6.3.1 Basic Ideas.- 6.3.2 Branch and Bound Algorithm.- 6.3.3 Simulated Annealing.- 6.3.4 Computational Results.- References.- 7 Resource Constrained Scheduling.- 7.1 Classical Model.- 7.2 Scheduling Multiprocessor Tasks.- 7.3 Scheduling with Continuous Resources.- 7.3.1 Introductory Remarks.- 7.3.2 Processing Speed vs. Resource Amount Model.- 7.3.3 Processing Time vs. Resource Amount Model.- 7.3.4 Ready Time vs. Resource Amount Model.- References.- 8 Scheduling in Flexible Manufacturing Systems.- 8.1 Introductory Remarks.- 8.2 Scheduling Flexible Flow Shops.- 8.2.1 Problem Formulation.- 8.2.2 Heuristics and their Performance.- 8.2.3 Branch and Bound Algorithm.- 8.3 Scheduling Dynamic Job Shops.- 8.3.1 Introductory Remarks.- 8.3.2 Heuristic Algorithm for the Static Problem.- 8.3.3 Computational Experiments.- 8.4 Simultaneous Scheduling and Routing in some FMS.- 8.4.1 Problem Formulation.- 8.4.2 Vehicle Scheduling for a Fixed Production Schedule.- 8.4.3 Simultaneous Job and Vehicle Scheduling.- References.- 9 Knowledge-Based Scheduling.- 9.1 Scheduling in Computer Integrated Manufacturing.- 9.2 Solution Approaches Based on Artificial Intelligence.- 9.2.1 Interactive Scheduling.- 9.2.2 Knowledge-Based Systems.- 9.3 Integration of Knowledge and Algorithms.- 9.3.1 Intelligent Production Scheduling.- 9.3.2 Integrated Problem Solving.- References.