Bellman / Esogbue / Nabeshima Mathematical Aspects of Scheduling and Applications

Modern Applied Mathematics and Computer Science
1. Auflage 2014
ISBN: 978-1-4831-3744-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 344 Seiten, Web PDF

Mathematical Aspects of Scheduling and Applications addresses the perennial problem of optimal utilization of finite resources in the accomplishment of an assortment of tasks or objectives. The book provides ways to uncover the core of these problems, presents them in mathematical terms, and devises mathematical solutions for them. The book consists of 12 chapters. Chapter 1 deals with network problems, the shortest path problem, and applications to control theory. Chapter 2 stresses the role and use of computers based on the decision-making problems outlined in the preceding chapter. Chapter 3 classifies scheduling problems and their solution approaches. Chapters 4 to 6 discuss machine sequencing problems and techniques. Chapter 5 tackles capacity expansion problems and introduces the technique of embedded state space dynamic programming for reducing dimensionality so that larger problems can be solved. Chapter 6 then examines an important class of network problems with non-serial phase structures and exploits dimensionality reduction techniques, such as the pseudo-stage concept, branch compression, and optimal order elimination methods to solve large-scale, nonlinear network scheduling problems. Chapters 7 to 11 consider the flow-shop scheduling problem under different objectives and constraints. Chapter 12 discusses the job-shop-scheduling problem. The book will be useful to economists, planners, and graduate students in the fields of mathematics, operations research, management science, computer science, and engineering.

Autoren/Hrsg.

Bellman, R.

Esogbue, A. O.

Nabeshima, I.

Rodin, E. Y.

Inhaltsverzeichnis

1;Front Cover
;1
2;Mathematical Aspects of Scheduling and Applications
;4
3;Copyright Page
;5
4;Table of Contents
;10
5;Preface;6
6;CHAPTER 1. Network Flow, Shortest Path and Control Problems
;16
6.1;1.1. Introduction;16
6.2;1.2. The Routing Problem;16
6.3;1.3. Dynamic Programming Approach;17
6.4;1.4. Upper and Lower Bounds;18
6.5;1.5. Existence and Uniqueness;20
6.6;1.6. Optimal Policy;23
6.7;1.8. Computational Feasibility;24
6.8;1.9. Storage of Algorithms;25
6.9;1.10. Alternate Approaches;25
6.10;1.11. "Traveling-salesman' Problem;25
6.11;1.12. Reducing Dimensionality via Bounding Strategies;27
6.12;1.13. Stochastic Traveling-salesman Problem;29
6.13;1.14. Applications to Control Theory;31
6.14;1.15. Stratification;31
6.15;1.16. Routing and Control Processes;32
6.16;1.17. Computational Procedure;33
6.17;1.18. Feasibility;34
6.18;1.19. Perturbation Technique;35
6.19;1.20. Generalized Routing;36
6.20;1.21. Discussion;37
6.21;Bibliography and Comments;37
7;CHAPTER 2. Applications to Artificial Intelligence and Games;41
7.1;2.1. Introduction;41
7.2;2.2. An Operational Point of View;41
7.3;2.3. Description of a Particular Problem;41
7.4;2.4. Imbedding;42
7.5;2.5. A Fundamental Equation;43
7.6;2.6. Geometric Ideas;44
7.7;2.7. Conversion of a Decision Process into an Equation;44
7.8;2.8. The Concept of a Solution;44
7.9;2.9. Determination of the Solution;45
7.10;2.10. Determination of a Number;46
7.11;2.11. Decision-making by Computers;46
7.12;2.12. Enumeration;47
7.13;2.13. Writing a Program;48
7.14;2.14. Storage;48
7.15;2.15. Dimensionality;49
7.16;2.16. Structure;49
7.17;2.17. Heuristics;50
7.18;2.18. Discussion;50
7.19;2.19. Application to Game Playing;51
7.20;2.20. Mathematical Abstractions;51
7.21;2.21. Intelligent Machines;51
7.22;2.22. The Wine-pouring Problem;51
7.23;2.23. Formulation as a Multistage Decision Process;52
7.24;2.24. Cannibals and Missionaries;54
7.25;2.25. Formulation as a Multistage Decision Process;55
7.26;2.26. Chinese Fifteen Puzzle;55
7.27;2.27. The Puzzle Again;56
7.28;2.28. Feasibility;56
7.29;2.29. Doable Positions;57
7.30;2.30. Associated Questions;57
7.31;2.31. The Original Puzzle;57
7.32;2.32. Lewis Carroll's Game of Doublets;58
7.33;2.33. Chess and Checkers;58
7.34;2.34. Solving Puzzles by Computer;58
7.35;2.35. Discussion;59
7.36;Bibliography and Comments;59
8;CHAPTER 3. Scheduling Problems and Combinatorial Programming
;63
8.1;3.1. Introduction;63
8.2;3.2. Classification of Scheduling Problems;63
8.3;3.3. Sequencing Problem;63
8.4;3.4. Project Scheduling Problem;65
8.5;3.5. Assembly-line Balancing Problem;66
8.6;3.6. Mutual Relations;66
8.7;3.7. Summary of Combinatorial Programming as a Solution Technique;67
8.8;3.8. State Transformation Process;67
8.9;3.9. Branch and Bound Method (BAB Method);69
8.10;3.10. Relative Error of Approximate Value and Heuristic Algorithm for Deciding a Reliable Approximate Solution (Extended BAB Method)
;71
8.11;3.11. Backtrack Programming and Lexicographical Search Method;73
8.12;Bibliography and Comments;73
9;CHAPTER 4. The Nature of the Sequencing Problem
;76
9.1;4.1. Introduction;76
9.2;4.2. Assumption and Objective Functions;78
9.3;4.3. Objective Function (Measure of Performance);79
9.4;4.4. Objective Functions of the other Type;81
9.5;4.5. Classification of Sequences and Non-numerical Judgement;83
9.6;4.6. Judgement for Determination;84
9.7;4.7. Generation of Feasible Sequences;89
9.8;4.8. Potentially Optimal Sequence and Nonoptimal Sequence;89
9.9;4.9. Determination of Potentially Optimal Sequencesand Nonoptimal Sequences;89
9.10;4.10. Classification and Generation of Schedules;91
9.11;4.11. Semiactive Schedule and Inadmissible Schedule;92
9.12;4.12. Start and Completion Times of Each Operation;93
9.13;4.13. Active Schedule and Nonactive Schedule;95
9.14;4.14. a-Optimal Schedule and Non-a-optimal Schedule;96
9.15;4.15. Generation of Active Schedules;97
9.16;Bibliography and Comments;100
10;CHAPTER 5. Sequencing Involving Capacity Expansion
;102
10.1;5.1. Introduction;102
10.2;5.2. A Simple Expansion—Sequencing Problem—the One-dimensional Version
;102
10.3;5.3. Why Dynamic Programming?;104
10.4;5.4. Conventional Dynamic Program (DPI) for the One-dimensional Sequencing Problem
;104
10.5;5.5. The Imbedded States Space Dynamic Program (DP2) for the One-dimensional Sequencing Problem
;105
10.6;5.6. Discussion;108
10.7;5.7. Formulation;109
10.8;5.8. An Illustrative Example;109
10.9;5.9. Reducing M&E Imbedded State Space for Large-capacity Expansion Problems;111
10.10;5.10. Discussion;113
10.11;5.11. Multi-dimensional Sequencing Problem---Theory;114
10.12;5.12. A Graphical Illustration;116
10.13;5.13. Computational Experience on Real-world Problems;117
10.14;5.14. Variations and Extensions;119
10.15;5.15. Miscellaneous Exercises;119
10.16;Bibliography and Comments;121
11;CHAPTER 6. Sequencing Problems with Nonserial Structures;124
11.1;6.1. Introduction;124
11.2;6.2. Serial Multistage Sequencing Processes;125
11.3;6.3. Nonserial Multistage Sequencing Processes;126
11.4;6.4. CPM-Cost Problem: the Basic Model;129
11.5;6.5. CPM-Cost Problems with Serial Structures;130
11.6;6.6. CPM-Cost Problems with Nonserial Phase Structure;132
11.7;6.7. Nonserial Networks: Project Cost Minimization Approach [PCM]
;132
11.8;6.8. Project Time Minimization Approach [PTM];135
11.9;6.9. A Dynamic Programming Model of the PTM Problem;135
11.10;6.10. EXAMPLE 1. The Pseudo-stage Concept and CPM-Cost Problem;136
11.11;6.11. EXAMPLE 2. A CPM-Cost Problem with Many Paths Departing from Junction;138
11.12;6.12. EXAMPLE 3. A Complex Nonserial System as in Fig. 6.10;140
11.13;6.13. Discussion;142
11.14;Bibliography and Comments;143
12;CHAPTER 7. Analytical Results for the Flow-shop Scheduling Problem
;147
12.1;7.1. Introduction;147
12.2;7.2. Characteristics of Schedules;147
12.3;7.3. Calculation of Makespan;148
12.4;7.4. Determination of Machine Idle Time and Waiting Time of Job;150
12.5;7.5. Flow Time Tk (iq );151
12.6;7.6. Recurrence Relation for Flow Time Tk (~q );152
12.7;7.7. Expressions of Makespan;153
12.8;7.8. Calculation of Machine Idle Time;154
12.9;7.9. Flow Network Expression in Critical Path Method;156
12.10;7.10. Critical Path Length between Two Nodes and Makespan;157
12.11;7.11. Two-Machine Min-Makespan Problem;161
12.12;7.12. Solution by Using Machine Idle Time;162
12.13;7.13. Solution by Dynamic Programming;164
12.14;7.14. Solution by Using Flow Time T2R (i)
;167
12.15;7.15. Working Rules;169
12.16;7.16. General Working Rule;169
12.17;7.17. Restricted Working Rule;173
12.18;Bibliography and Comments;175
13;CHAPTER 8. Flow-shop Scheduling Problems: Analytical Results II and Extensions
;177
13.1;8.1. Introduction;177
13.2;8.2. Three-machine Min-Makespan Problem;177
13.3;8.3. Limited Solution under Special Processing Times;178
13.4;8.4. Solution by Using Machine Idle Time;178
13.5;8.5. Formulation by Flow Times T2 (i), T3 (i)
;182
13.6;8.6. Flow times T2 (i ), T3 (i) and Makespan;182
13.7;8.7. Recurrence Relation between T2 (iq), T3 (iq ) (q = 1, 2, ... , n)
;182
13.8;8.8. Dynamic Programming-type Formulation;183
13.9;8.9. Values of T3(i), T3(ij ), and T3 (j ), T3( ji );184
13.10;8.10. Proof by Using Flow Times;185
13.11;8.11. Case (a);185
13.12;8.12. Case (b);186
13.13;8.13. Limited Solution under Other Special Processing Times;188
13.14;8.14. Sufficient Conditions for Two Adjacent Jobs to be in a Definite Order in the Optimal Sequence;190
13.15;8.15. Sufficient Inequalities not including T2 (1) and T3 (l);191
13.16;8.16. Sufficient Inequalities that Satisfy the Transitive Property;193
13.17;8.17. Two-machine Min-Makespan Problem where Time Lags Exist;197
13.18;8.18. On the Generalizations to m Machine Permutation Scheduling
;200
13.19;Bibliography and Comments;212
14;CHAPTER 9. Flow-shop Scheduling Problems: General Solutions
;215
14.1;9.1. Introduction;215
14.2;9.2. m Machine Min-Makespan Problem(m >_ 3, no Passing is Allowed);215
14.3;9.3. Concrete Procedures in BAB Algorithms;216
14.4;9.4. BAB Algorithms for Flow Shops;219
14.5;9.5. Standard Lower Bound;220
14.6;9.6. Efficiency of BAB Algorithm;222
14.7;9.7. Relations between Machine Order, Processing Times, and Optimal Sequence
;223
14.8;9.8. Revised Lower Bound and Composite Lower Bound;225
14.9;9.9. Backtrack Programming and Lexicographical Search Method
;231
14.10;9.10. m Machine Min-Mean Completion Time Problem;234
14.11;9.11. A Lemma and Analytical Results;235
14.12;9.12. A BAB Algorithm;237
14.13;9.13. m-Machine Min-Penalty Cost by Tardiness Problem;240
14.14;9.14. Backtrack Programming and Lexicographical Search Method;241
14.15;9.15. A BAB Algorithm and its Lower Bound;245
14.16;Bibliography and Comments;248
15;CHAPTER 10. Flow-shop Scheduling Problems: Unified Algorithms and Approximate Solutions
;250
15.1;10.1. Introduction;250
15.2;10.2. Unified Multistage Combinatorial Algorithms for Setup-time Imbedded Processing Times;250
15.3;10.3. A Formulation by the State Transformation Process;251
15.4;10.4. Simple Function q(F,P(Sj )) for each Objective Function F;253
15.5;10.5. Relation between Min-Makespan Problem and Min-Other Objective Problems;256
15.6;10.6. Unified Multistage Combinatorial Algorithm;257
15.7;10.7. Application to Parallel Scheduling;258
15.8;10.8. Numerical Examples of Min-Mean Intermediate Waiting-time Problem and Related Parallel Scheduling
;258
15.9;10.9. Unified Multistage Combinatorial Algorithm where Explicit Setup Times Exist;259
15.10;10.10. Setup Times;260
15.11;10.11. A Formulation by the State Transformation Process;260
15.12;10.12. Approximate Algorithms for Min-Makespan Problem;266
15.13;10.13. Application of a Specified Function to Construct an Approximate Sequence;266
15.14;Bibliography and Comments;271
16;CHAPTER 11. Flow-shop Scheduling under Sequence Dependence Conditions
;273
16.1;11.1. Sequence Dependent Setup Times;273
16.2;11.2. Problem Definition;274
16.3;11.3. Optimality of Permutation Schedules;275
16.4;11.4. Dynamic Programming Formulations for ID and DI;276
16.5;11.5. Forward DP Recursion for Problem Type ID;276
16.6;11.6. Computational Aspects;278
16.7;11.7. Backward DP Recursion for Problem Type DI;278
16.8;11.8. Implications of Theorem 3;281
16.9;11.9. Computational Aspects;282
16.10;11.10. Discussion of the Dynamic Programming Approach;282
16.11;11.11. Optimal Schedules for Problem Types DII, IDl and IID;284
16.12;11.12. Dominance Conditions for Problem Types DII, IDI, and IID;285
16.13;11.13. Backward Dynamic Programming Formulations;286
16.14;11.14. Reducing Dimensionality;289
16.15;11.15. Selection of Value for c1;290
16.16;11.16. Computational Requirements;291
16.17;11.17. Extensions
;292
16.18;Bibliography and Comments;294
17;CHAPTER 12. The Job-shop Scheduling Problem
;296
17.1;12.1. Introduction;296
17.2;12.2. The n x 2 Min-Makespan Problem;297
17.3;12.3. Graphical Solution of the 2 x m Min-Makespan Problem;298
17.4;12.4. Graphical Representation of the Schedule;298
17.5;12.5. Construction of the Path;301
17.6;12.6. Approaches by Integer Linear Programming;304
17.7;12.7. Standard Formulation by ILP;305
17.8;12.8. BAB Algorithms by Following Active Schedule Generation Procedure;306
17.9;12.9. BAB Algorithm by Active Schedule Generation Procedure;306
17.10;12.10. BAB Algorithm I;307
17.11;12.11. Lower Bound in BAB Algorithm I;308
17.12;12.12. Graph G0 = (X, Z) Expressing Orderings
;311
17.13;12.13. Disjunctive Graph Representation by LimitedMachine Availability;312
17.14;12.14. BAB Algorithm on Disjunctive Graphs by following an Active Schedule Generation Procedure;313
17.15;12.15. BAB Algorithm by Resolving the Pairs of Disjunctive Arcs on a Disjunctive Graph;316
17.16;12.16. Representation by Graph G0 = (X, Z);316
17.17;12.17. Conflict Set;317
17.18;12.18. Disjunctive Graph;317
17.19;12.19. Complete Selection of Disjunctive Arcs and Schedules;317
17.20;12.20. Formulations of Two Types;318
17.21;12.21. BAB Algorithm by Partial Selection of Disjunctive Arcs;319
17.22;12.22. Generalization of the Sequencing Problem: The Multiproject Scheduling Problem with Limited Resources
;322
17.23;12.23. Solution Based on Disjunctive Graphs;322
17.24;12.24. Problem Statement;323
17.25;12.25. Conflict Set;323
17.26;12.26. Disjunctive Graphs Based on Conflict Sets of Activities;324
17.27;12.27. Formulation by Disjunctive Graph;324
17.28;12.28. BAB and EXTBAB Algorithms by Partial Selection of Disjunctive Arcs;326
17.29;12.29. BAB Algorithm;326
17.30;12.30. Justification of Proposed BAB Algorithm and Remarks;328
17.31;12.31. Numerical Examples by BAB Algorithm and Related EXTBAB Algorithm;330
17.32;Bibliography and Comments;333
18;Author Index;338
19;Subject Index;342