Cover image for Handbook on scheduling : from theory to applications
Title:
Handbook on scheduling : from theory to applications
Series:
International handbooks on information systems
Publication Information:
Berlin : Springer, 2007
ISBN:
9783540280460
General Note:
Also available online version
Added Author:
Electronic Access:
Full Text
DSP_RESTRICTION_NOTE:
Accessible within UTM campus

Available:*

Library
Item Barcode
Call Number
Material Type
Item Category 1
Status
Searching...
30000010163677 TS157.5 H364 2007 Open Access Book Book
Searching...

On Order

Summary

Summary

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.


Table of Contents

1 Introductionp. 1
Referencesp. 7
2 Basicsp. 9
2.1 Sets and Relationsp. 9
2.2 Problems, Algorithms, Complexityp. 11
2.2.1 Problems and Their Encodingp. 11
2.2.2 Algorithmsp. 13
2.2.3 Complexityp. 16
2.3 Graphs and Networksp. 21
2.3.1 Basic Notionsp. 21
2.3.2 Special Classes of Digraphsp. 22
2.3.3 Networksp. 25
2.4 Enumerative Methodsp. 32
2.4.1 Dynamic Programmingp. 33
2.4.2 Branch and Boundp. 33
2.5 Heuristic and Approximation Algorithmsp. 35
2.5.1 Approximation Algorithmsp. 35
2.5.2 Local Search Heuristicsp. 37
Referencesp. 52
3 Definition, Analysis and Classification of Scheduling Problemsp. 57
3.1 Definition of Scheduling Problemsp. 57
3.2 Analysis of Scheduling Problems and Algorithmsp. 62
3.3 Motivations for Deterministic Scheduling Problemsp. 65
3.4 Classification of Deterministic Scheduling Problemsp. 68
Referencesp. 71
4 Scheduling on One Processorp. 73
4.1 Minimizing Schedule Lengthp. 73
4.1.1 Scheduling with Release Times and Deadlinesp. 74
4.1.2 Scheduling with Release Times and Delivery Timesp. 81
4.2 Minimizing Mean Weighted Flow Timep. 83
4.3 Minimizing Due Date Involving Criteriap. 95
4.3.1 Maximum Latenessp. 96
4.3.2 Number of Tardy Tasksp. 104
4.3.3 Mean Tardinessp. 109
4.3.4 Mean Earlinessp. 113
4.4 Minimizing Change-Over Costp. 114
4.4.1 Setup Schedulingp. 114
4.4.2 Lot Size Schedulingp. 117
4.5 Other Criteriap. 122
4.5.1 Maximum Costp. 122
4.5.2 Total Costp. 127
Referencesp. 130
5 Scheduling on Parallel Processorsp. 137
5.1 Minimizing Schedule Lengthp. 137
5.1.1 Identical Processorsp. 137
5.1.2 Uniform and Unrelated Processorsp. 158
5.2 Minimizing Mean Flow Timep. 168
5.2.1 Identical Processorsp. 168
5.2.2 Uniform and Unrelated Processorsp. 169
5.3 Minimizing Due Date Involving Criteriap. 173
5.3.1 Identical Processorsp. 173
5.3.2 Uniform and Unrelated Processorsp. 179
5.4 Other Modelsp. 182
5.4.1 Scheduling Imprecise Computationsp. 182
5.4.2 Lot Size Schedulingp. 185
Referencesp. 190
6 Communication Delays and Multiprocessor Tasksp. 199
6.1 Introductory Remarksp. 199
6.2 Scheduling Multiprocessor Tasksp. 205
6.2.1 Parallel Processorsp. 205
6.2.2 Dedicated Processorsp. 213
6.2.3 Refinement Schedulingp. 219
6.3 Scheduling Uniprocessor Tasks with Communication Delaysp. 221
6.3.1 Scheduling without Task Duplicationp. 222
6.3.2 Scheduling with Task Duplicationp. 225
6.3.3 Scheduling in Processor Networksp. 226
6.4 Scheduling Divisible Tasksp. 228
Referencesp. 236
7 Scheduling in Hard Real-Time Systemsp. 243
7.1 Introductionp. 243
7.1.1 What is a Real-Time System?p. 244
7.1.2 Examples of Real-Time Systemsp. 245
7.1.3 Characteristics of Real-Time Systemsp. 246
7.1.4 Functional Requirements for Real-Time Systemsp. 247
7.2 Basic Notationsp. 248
7.2.1 Structure of a Real-Time Systemp. 248
7.2.2 The Task Modelp. 249
7.2.3 Schedulesp. 250
7.3 Single Processor Schedulingp. 252
7.3.1 Static Priority Rulesp. 253
7.3.2 Dynamic Priority Schedulingp. 262
7.4 Scheduling Periodic Tasks on Parallel Processorsp. 264
7.5 Resourcesp. 265
7.6 Variations of the Periodic Task Modelp. 266
Referencesp. 267
8 Flow Shop Schedulingp. 271
8.1 Introductionp. 271
8.1.1 The Flow Shop Scheduling Problemp. 271
8.1.2 Complexityp. 273
8.2 Exact Methodsp. 274
8.2.1 The Algorithms of Johnson and Akersp. 274
8.2.2 Dominance and Branching Rulesp. 277
8.2.3 Lower Boundsp. 278
8.3 Approximation Algorithmsp. 282
8.3.1 Priority Rule and Local Search Based Heuristicsp. 282
8.3.2 Worst-Case Analysisp. 285
8.3.3 No Wait in Processp. 289
8.4 Scheduling Flexible Flow Shopsp. 291
8.4.1 Problem Formulationp. 291
8.4.2 Heuristics and Their Performancep. 294
8.4.3 A Modelp. 296
8.4.4 The Makespan Minimization Problemp. 297
8.4.5 The Mean Flow Time Problemp. 311
Referencesp. 316
9 Open Shop Schedulingp. 321
9.1 Complexity Resultsp. 321
9.2 A Branch and Bound Algorithm for Open Shop Schedulingp. 323
9.2.1 The Disjunctive Model of the OSPp. 323
9.2.2 Constraint Propagation and the OSPp. 326
9.2.3 The Algorithm and Its Performancep. 332
Referencesp. 341
10 Scheduling in Job Shopsp. 345
10.1 Introductionp. 345
10.1.1 The Problemp. 345
10.1.2 Modelingp. 345
10.1.3 Complexityp. 348
10.1.4 The Historyp. 349
10.2 Exact Methodsp. 352
10.2.1 Branch and Boundp. 353
10.2.2 Lower Boundsp. 353
10.2.3 Branchingp. 355
10.2.4 Valid Inequalitiesp. 358
10.3 Approximation Algorithmsp. 360
10.3.1 Priority Rulesp. 360
10.3.2 The Shifting Bottleneck Heuristicp. 362
10.3.3 Opportunistic Schedulingp. 365
10.3.4 Local Searchp. 367
10.4 Conclusionsp. 387
Referencesp. 388
11 Scheduling with Limited Processor Availabilityp. 397
11.1 Problem Definitionp. 398
11.2 One Machine Problemsp. 401
11.3 Parallel Machine Problemsp. 403
11.3.1 Minimizing the Sum of Completion Timesp. 403
11.3.2 Minimizing the Makespanp. 404
11.3.3 Dealing with Due Date Involving Criteriap. 412
11.4 Shop Problemsp. 414
11.4.1 Flow Shop Problemsp. 414
11.4.2 Open Shop Problemsp. 417
11.5 Conclusionsp. 417
Referencesp. 419
12 Scheduling under Resource Constraintsp. 425
12.1 Classical Modelp. 425
12.2 Scheduling Multiprocessor Tasksp. 436
12.3 Scheduling with Continuous Resourcesp. 450
12.3.1 Introductory Remarksp. 451
12.3.2 Processing Speed vs. Resource Amount Modelp. 452
12.3.3 Processing Time vs. Resource Amount Modelp. 461
12.3.4 Ready Time vs. Resource Amount Modelp. 466
Referencesp. 471
13 Constraint Programming and Disjunctive Schedulingp. 477
13.1 Introductionp. 477
13.2 Constraint Satisfactionp. 479
13.2.1 The Constraint Satisfaction and Optimization Problemp. 479
13.2.2 Constraint Propagationp. 481
13.3 The Disjunctive Scheduling Problemp. 493
13.3.1 The Disjunctive Modelp. 494
13.3.2 Solution Methods for the DSPp. 497
13.4 Constraint Propagation and the DSPp. 497
13.4.1 Some Basic Definitionsp. 498
13.4.2 Precedence Consistency Testsp. 500
13.4.3 Lower-Level Bound-Consistencyp. 500
13.4.4 Input/Output Consistency Testsp. 509
13.4.5 Input/Output Negation Consistency Testsp. 516
13.4.6 Input-or-Output Consistency Testsp. 522
13.4.7 Energetic Reasoningp. 523
13.4.8 Shavingp. 527
13.4.9 A Comparison of Disjunctive Consistency Testsp. 528
13.4.10 Precedence vs. Disjunctive Consistency Testsp. 530
13.5 Conclusionsp. 530
13.6 Appendix: Bound Consistency Revisitedp. 531
Referencesp. 535
14 Scheduling in Flexible Manufacturing Systemsp. 539
14.1 Introductory Remarksp. 539
14.2 Scheduling Dynamic Job Shopsp. 542
14.2.1 Introductory Remarksp. 542
14.2.2 Heuristic Algorithm for the Static Problemp. 543
14.2.3 Computational Experimentsp. 549
14.3 Simultaneous Scheduling and Routing in some FMSp. 550
14.3.1 Problem Formulationp. 550
14.3.2 Vehicle Scheduling for a Fixed Production Schedulep. 552
14.3.3 Simultaneous Job and Vehicle Schedulingp. 557
14.4 Batch Scheduling in Flexible Flow Shops under Resource Constraintsp. 559
14.4.1 Introduction - Statement of the Problemp. 559
14.4.2 Mathematical Formulationp. 560
14.4.3 Heuristic Solution Approachp. 570
14.4.4 Implementation and Computational Experimentp. 577
Referencesp. 579
15 Computer Integrated Production Schedulingp. 583
15.1 Scheduling in Computer Integrated Manufacturingp. 584
15.2 A Reference Model for Production Schedulingp. 589
15.3 IPS: An Intelligent Production Scheduling Systemp. 597
15.3.1 Interactive Schedulingp. 604
15.3.2 Knowledge-based Schedulingp. 619
15.3.3 Integrated Problem Solvingp. 624
Referencesp. 628
Indexp. 631