Scheduling computer and manufacturing processes

Title:

Edition:

2nd ed.

Publication Information:

Berlin : New York : Springer, 2001

ISBN:

9783540419310

Subject Term:

Scheduling management

Computer capacity -- Management

Added Author:

Bazewicz, Jacek

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000004888842	TS157.5 S35 2001	Open Access Book	Book	Searching... Unknown

Written in a clear and concise manner this book provides a theoretical and application oriented analysis of deterministic scheduling problems arising in computer and manufacturing environments. 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 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. An excellent analysis based on real-world applications with plenty of examples.

1 Introduction	p. 1
References	p. 6
2 Basics	p. 9
2.1 Sets and Relations	p. 9
2.2 Problems, Algorithms, Complexity	p. 11
2.2.1 Problems and Their Encoding	p. 11
2.2.2 Algorithms	p. 13
2.2.3 Complexity	p. 16
2.3 Graphs and Networks	p. 21
2.3.1 Basic Notions	p. 21
2.3.2 Special Classes of Digraphs	p. 22
2.3.3 Networks	p. 25
2.4 Enumerative Methods	p. 32
2.4.1 Dynamic Programming	p. 32
2.4.2 Branch and Bound	p. 33
2.5 Heuristic and Approximation Algorithms	p. 35
2.5.1 Approximation Algorithms	p. 35
2.5.2 Local Search Heuristics	p. 37
References	p. 51
3 Definition, Analysis and Classification of Scheduling Problems	p. 57
3.1 Definition of Scheduling Problems	p. 57
3.2 Analysis of Scheduling Problems and Algorithms	p. 62
3.3 Motivations for Deterministic Scheduling Problems	p. 65
3.4 Classification of Deterministic Scheduling Problems	p. 68
References	p. 71
4 Scheduling on One Processor	p. 73
4.1 Minimizing Schedule Length	p. 73
4.1.1 Scheduling with Release Times and Deadlines	p. 74
4.1.2 Scheduling with Release Times and Delivery Times	p. 81
4.2 Minimizing Mean Weighted Flow Time	p. 83
4.3 Minimizing Due Date Involving Criteria	p. 95
4.3.1 Maximum Lateness	p. 95
4.3.2 Number of Tardy Tasks	p. 104
4.3.3 Mean Tardiness	p. 109
4.3.4 Mean Earliness	p. 112
4.4 Minimizing Change-Over Cost	p. 113
4.4.1 Setup Scheduling	p. 113
4.4.2 Lot Size Scheduling	p. 116
4.5 Other Criteria	p. 121
4.5.1 Maximum Cost	p. 121
4.5.2 Total Cost	p. 126
References	p. 129
5 Scheduling on Parallel Processors	p. 137
5.1 Minimizing Schedule Length	p. 137
5.1.1 Identical Processors	p. 137
5.1.2 Uniform and Unrelated Processors	p. 157
5.2 Minimizing Mean Flow Time	p. 166
5.2.1 Identical Processors	p. 166
5.2.2 Uniform and Unrelated Processors	p. 168
5.3 Minimizing Due Date Involving Criteria	p. 171
5.3.1 Identical Processors	p. 171
5.3.2 Uniform and Unrelated Processors	p. 178
5.4 Other Models	p. 180
5.4.1 Semi-Identical Processors	p. 181
5.4.2 Scheduling Imprecise Computations	p. 189
5.4.3 Lot Size Scheduling	p. 192
References	p. 196
6 Communication Delays and Multiprocessor Tasks	p. 205
6.1 Introductory Remarks	p. 205
6.2 Scheduling Multiprocessor Tasks	p. 210
6.2.1 Parallel Processors	p. 210
6.2.2 Dedicated Processors	p. 218
6.2.3 Refinment scheduling	p. 224
6.3 Scheduling Uniprocessor Tasks with Communication Delays	p. 226
6.3.1 Scheduling without Task Duplication	p. 228
6.3.2 Scheduling with Task Duplication	p. 230
6.3.3 Scheduling in Processor Networks	p. 231
6.4 Scheduling Divisible Tasks	p. 233
References	p. 240
7 Scheduling in Flow and Open Shops	p. 247
7.1 Introduction	p. 247
7.1.1 The Flow Shop Scheduling Problem	p. 247
7.1.2 Complexity	p. 249
7.2 Exact Methods	p. 250
7.2.1 The algorithms of Johnson and Akers	p. 250
7.2.2 Dominance and Branching Rules	p. 253
7.2.3 Lower Bounds	p. 254
7.3 Approximation Algorithms	p. 259
7.3.1 Priority Rule and Local Search Based Heuristics	p. 259
7.3.2 Worst-Case Analysis	p. 262
7.3.3 No Wait in Process	p. 266
7.4 Open Shop Scheduling	p. 267
References	p. 269
8 Scheduling in Job Shops	p. 273
8.1 Introduction	p. 273
8.1.1 The Problem	p. 273
8.1.2 Modelling	p. 273
8.1.3 Complexity	p. 276
8.1.4 The History	p. 277
8.2 Exact Methods	p. 280
8.2.1 Branch and Bound	p. 280
8.2.2 Lower Bounds	p. 281
8.2.3 Branching	p. 282
8.2.4 Valid Inequalities	p. 286
8.3 Approximation Algorithms	p. 288
8.3.1 Priority Rules	p. 288
8.3.3 Opportunistic Scheduling	p. 293
8.3.4 Local Search	p. 294
8.4 Conclusions	p. 308
References	p. 308
9 Scheduling under Resource Constraints	p. 317
9.1 Classical Model	p. 317
9.2 Scheduling Multiprocessor Tasks	p. 328
9.3 Scheduling with Continuous Resources	p. 342
9.3.1 Introductory Remarks	p. 342
9.3.2 Processing Speed vs. Resource Amount Model	p. 344
9.3.3 Processing Time vs. Resource Amount Model	p. 353
9.3.4 Ready Time vs. Resource Amount Model	p. 358
References	p. 362
10 Scheduling in Flexible Manufacturing Systems	p. 367
10.1 Introductory Remarks	p. 367
10.2 Scheduling Flexible Flow Shops	p. 370
10.2.1 Problem Formulation	p. 370
10.2.2 Heuristics and their Performance	p. 371
10.2.3 Branch and Bound Algorithm	p. 373
10.3 Scheduling Dynamic Job Shops	p. 379
10.3.1 Introductory Remarks	p. 379
10.3.2 Heuristic Algorithm for the Static Problem	p. 380
10.3.3 Computational Experiments	p. 386
10.4 Simultaneous Scheduling and Routing in some FMS	p. 387
10.4.1 Problem Formulation	p. 387
10.4.2 Vehicle Scheduling for a Fixed Production Schedule	p. 389
10.4.3 Simultaneous Job and Vehicle Scheduling	p. 394
10.5 Batch Scheduling in Flexible Flow Shops under Resource Constraints	p. 396
10.5.1 Introduction - Statement of the Problem	p. 396
10.5.2 Mathematical Formulation	p. 398
10.5.3 Heuristic Solution Approach	p. 407
10.5.4 Implementation and Computational Experiment	p. 414
References	p. 415
11 Computer Integrated Production Scheduling	p. 421
11.1 Scheduling in Computer Integrated Manufacturing	p. 422
11.2 A Reference Model for Production Scheduling	p. 427
11.3 IPS: An Intelligent Production Scheduling System	p. 435
11.3.1 Interactive Scheduling	p. 442
11.3.2 Knowledge-Based Systems	p. 456
11.3.3 Integrated Problem Solving	p. 462
References	p. 466
Index	p. 469

Available:*

On Order

Summary

Summary

Table of Contents