Scheduling Computer and Manufacturing Processes

by Bazewicz, Jacek; Ecker, Klaus H.; Pesch, Erwin; Schmidt, Gunter; Weglarz, Jan

• ISBN13: 9783540419310
• ISBN10: 3540419314
• Edition: 2nd
• Format: Hardcover
• Copyright: 2001-07-01
• Publisher: Springer Verlag

Summary

This book provides a theoretical and application oriented analysis of deterministic scheduling problems arising in computer and manufacturing environments. In such systems processors (machines) and possibly 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 factor are involved. Polynomial and exponential time optimization algorithms as well as approximation and heuristic approaches (including tabu search, simulated annealing, genetic algorithms, and ejection chains) are presented and discussed. Moreover, resource-constrained, imprecise computation, flexible flow shop and dynamic job shop scheduling, as well as flexible manufacturing systems, are considered.

Table of Contents

Introduction	1	(8)
References	6	(3)
Basics	9	(48)
Sets and Relations	9	(2)
Problems, Algorithms, Complexity	11	(10)
Problems and Their Encoding	11	(2)
Algorithms	13	(3)
Complexity	16	(5)
Graphs and Networks	21	(11)
Basic Notions	21	(1)
Special Classes of Digraphs	22	(3)
Networks	25	(7)
Enumerative Methods	32	(3)
Dynamic Programming	32	(1)
Branch and Bound	33	(2)
Heuristic and Approximation Algorithms	35	(22)
Approximation Algorithms	35	(2)
Local Search Heuristics	37	(14)
References	51	(6)
Definition, Analysis and Classification of Scheduling Problems	57	(16)
Definition of Scheduling Problems	57	(5)
Analysis of Scheduling Problems and Algorithms	62	(3)
Motivations for Deterministic Scheduling Problems	65	(3)
Classification of Deterministic Scheduling Problems	68	(5)
References	71	(2)
Scheduling on One Processor	73	(64)
Minimizing Schedule Length	73	(10)
Scheduling with Release Times and Deadlines	74	(7)
Scheduling with Release Times and Delivery Times	81	(2)
Minimizing Mean Weighted Flow Time	83	(12)
Minimizing Due Date Involving Criteria	95	(18)
Maximum Lateness	95	(9)
Number of Tardy Tasks	104	(5)
Mean Tardiness	109	(3)
Mean Earliness	112	(1)
Minimizing Change-Over Cost	113	(8)
Setup Scheduling	113	(3)
Lot Size Scheduling	116	(5)
Other Criteria	121	(16)
Maximum Cost	121	(5)
Total Cost	126	(3)
References	129	(8)
Scheduling on Parallel Processors	137	(68)
Minimizing Schedule Length	137	(29)
Identical Processors	137	(20)
Uniform and Unrelated Processors	157	(9)
Minimizing Mean Flow Time	166	(5)
Identical Processors	166	(2)
Uniform and Unrelated Processors	168	(3)
Minimizing Due Date Involving Criteria	171	(9)
Identical Processors	171	(7)
Uniform and Unrelated Processors	178	(2)
Other Models	180	(25)
Semi-Identical Processors	181	(8)
Scheduling Imprecise Computations	189	(3)
Lot Size Scheduling	192	(4)
References	196	(9)
Communication Delays and Multiprocessor Tasks	205	(42)
Introductory Remarks	205	(5)
Scheduling Multiprocessor Tasks	210	(16)
Parallel Processors	210	(8)
Dedicated Processors	218	(6)
Refinment scheduling	224	(2)
Scheduling Uniprocessor Tasks with Communication Delays	226	(7)
Scheduling without Task Duplication	228	(2)
Scheduling with Task Duplication	230	(1)
Scheduling in Processor Networks	231	(2)
Scheduling Divisible Tasks	233	(14)
References	240	(7)
Scheduling in Flow and Open Shops	247	(26)
Introduction	247	(3)
The Flow Shop Scheduling Problem	247	(2)
Complexity	249	(1)
Exact Methods	250	(9)
The algorithms of Johnson and Akers	250	(3)
Dominance and Branching Rules	253	(1)
Lower Bounds	254	(5)
Approximation Algorithms	259	(8)
Priority Rule and Local Search Based Heuristics	259	(3)
Worst-Case Analysis	262	(4)
No Wait in Process	266	(1)
Open Shop Scheduling	267	(6)
References	269	(4)
Scheduling in Job Shops	273	(44)
Introduction	273	(7)
The Problem	273	(1)
Modeling	273	(3)
Complexity	276	(1)
The History	277	(3)
Exact Methods	280	(8)
Branch and Bound	280	(1)
Lower Bounds	281	(1)
Branching	282	(4)
Valid Inequalities	286	(2)
Approximation Algorithms	288	(20)
Priority Rules	288	(5)
Opportunistic Scheduling	293	(1)
Local Search	294	(14)
Conclusions	308	(9)
References	308	(9)
Scheduling under Resource Constraints	317	(50)
Classical Model	317	(11)
Scheduling Multiprocessor Tasks	328	(14)
Scheduling with Continuous Resources	342	(25)
Introductory Remarks	342	(2)
Processing Speed vs. Resource Amount Model	344	(9)
Processing Time vs. Resource Amount Model	353	(5)
Ready Time vs. Resource Amount Model	358	(4)
References	362	(5)
Scheduling in Flexible Manufacturing Systems	367	(54)
Introductory Remarks	367	(3)
Scheduling Flexible Flow Shops	370	(9)
Problem Formulation	370	(1)
Heuristics and their Performance	371	(2)
Branch and Bound Algorithm	373	(6)
Scheduling Dynamic Job Shops	379	(8)
Introductory Remarks	379	(1)
Heuristic Algorithm for the Static Problem	380	(6)
Computational Experiments	386	(1)
Simultaneous Scheduling and Routing in some FMS	387	(9)
Problem Formulation	387	(2)
Vehicle Scheduling for a Fixed Production Schedule	389	(5)
Simultaneous Job and Vehicle Scheduling	394	(2)
Batch Scheduling in Flexible Flow Shops under Resource Constraints	396	(25)
Introduction - Statement of the Problem	396	(2)
Mathematical Formulation	398	(9)
Heuristic Solution Approach	407	(7)
Implementation and Computational Experiment	414	(1)
References	415	(6)
Computer Integrated Production Scheduling	421	(48)
Scheduling in Computer Integrated Manufacturing	422	(5)
A Reference Model for Production Scheduling	427	(8)
IPS: An Intelligent Production Scheduling System	435	(34)
Interactive Scheduling	442	(14)
Knowledge-based Scheduling	456	(6)
Integrated Problem Solving	462	(4)
References	466	(3)
Index	469