Mathematical Aspects of Scheduling and Applications
Modern Applied Mathematics and Computer Science
Free Global Shipping
No minimum orderDescription
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.
Table of Contents
1. Network Flow, Shortest Path and Control Problems
1.1. Introduction
1.2. The Routing Problem
1.3. Dynamic Programming Approach
1.4. Upper and Lower Bounds
1.5. Existence and Uniqueness
1.6. Optimal Policy
1.7. Approximation in Policy Space
1.8. Computational Feasibility
1.9. Storage of Algorithms
1.10. Alternate Approaches
1.11. "Traveling-Salesman" Problem
1.12. Reducing Dimensionality via Bounding Strategies
1.13. Stochastic Traveling-Salesman Problem
1.14. Applications to Control Theory
1.15. Stratification
1.16. Routing and Control Processes
1.17. Computational Procedure
1.18. Feasibility
1.19. Perturbation Technique
1.20. Generalized Routing
1.21. Discussion
Bibliography and Comments
2. Applications to Artificial Intelligence and Games
2.1. Introduction
2.2. An Operational Point of View
2.3. Description of a Particular Problem
2.4. Embedding
2.5. A Fundamental Equation
2.6. Geometric Ideas
2.7. Conversion of a Decision Process into an Equation
2.8. The Concept of a Solution
2.9. Determination of the Solution
2.10. Determination of a Number
2.11. Decision-Making by Computers
2.12. Enumeration
2.13. Writing a Program
2.14. Storage
2.15. Dimensionality
2.16. Structure
2.17. Heuristics
2.18. Discussion
2.19. Application to Game Playing
2.20. Mathematical Abstractions
2.21. Intelligent Machines
2.22. The Wine-Pouring Problem
2.23. Formulation as a Multistage Decision Process
2.24. Cannibals and Missionaries
2.25. Formulation as a Multistage Decision Process
2.26. Chinese Fifteen Puzzle
2.27. The Puzzle Again
2.28. Feasibility
2.29. Doable Positions
2.30. Associated Questions
2.31. The Original Puzzle
2.32. Lewis Carroll's Game of Doublets
2.33. Chess and Checkers
2.34. Solving Puzzles by Computer
2.35. Discussion
Bibliography and Comments
3. Scheduling Problems and Combinatorial Programming
3.1. Introduction
3.2. Classification of Scheduling Problems
3.3. Sequencing Problem
3.4. Project Scheduling Problem
3.5. Assembly-Line Balancing Problem
3.6. Mutual Relations
3.7. Summary of Combinatorial Programming as a Solution Technique
3.8. State Transformation Process
3.9. Branch and Bound Method (BAB Method)
3.10. Relative Error of Approximate Value and Heuristic Algorithm for Deciding a Reliable Approximate Solution (Extended BAB Method)
3.11. Backtrack Programming and Lexicographical Search Method
Bibliography and Comments
4. The Nature of the Sequencing Problem
4.1. Introduction
4.2. Assumption and Objective Functions
4.3. Objective Function (Measure of Performance)
4.4. Objective Functions of the Other Type
4.5. Classification of Sequences and Non-Numerical Judgment
4.6. Judgment for Determination
4.7. Generation of Feasible Sequences
4.8. Potentially Optimal Sequence and Nonoptimal Sequence
4.9. Determination of Potentially Optimal Sequences and Nonoptimal Sequences
4.10. Classification and Generation of Schedules
4.11. Semiactive Schedule and Inadmissible Schedule
4.12. Start and Completion Times of Each Operation
4.13. Active Schedule and Nonactive Schedule
4.14. α-Optimal Schedule and Non-α-Optimal Schedule
4.15. Generation of Active Schedules
Bibliography and Comments
5. Sequencing Involving Capacity Expansion
5.1. Introduction
5.2. A Simple Expansion—Sequencing Problem—the One-Dimensional Version
5.3. Why Dynamic Programming?
5.4. Conventional Dynamic Program (DPI) for the One-Dimensional Sequencing Problem
5.5. The Embedded States Space Dynamic Program (DR2) for the One-Dimensional Sequencing Problem
5.6. Discussion
5.7. Formulation
5.8. An Illustrative Example
5.9. Reducing M&E Embedded State Space for Large-Capacity Expansion Problems
5.10. Discussion
5.11. Multi-Dimensional Sequencing Problem—Theory
5.12. A Graphical Illustration
5.13. Computational Experience on Real-World Problems
5.14. Variations and Extensions
5.15. Miscellaneous Exercises
Bibliography and Comments
6. Sequencing Problems with Nonserial Structures
6.1. Introduction
6.2. Serial Multistage Sequencing Processes
6.3. Nonserial Multistage Sequencing Processes
6.4. CPM-Cost Problem: the Basic Model
6.5. CPI-Cost Problems with Serial Structures
6.6. CPI-Cost Problems with Nonserial Phase Structure
6.7. Nonserial Networks: Project Cost Minimization Approach [PCM]
6.8. Project Time Minimization Approach [PTM]
6.9. A Dynamic Programming Model of the PTM Problem
6.10. Example 1. The Pseudo-Stage Concept and CPI-Cost Problem
6.11. Example 2. A CPI-Cost Problem with Many Paths Departing from Junction
6.12. Example 3. A Complex Nonserial System as in Fig. 6.10
6.13. Discussion
Bibliography and Comments
7. Analytical Results for the Flow-Shop Scheduling Problem
7.1. Introduction
7.2. Characteristics of Schedules
7.3. Calculation of Makespan
7.4. Determination of Machine Idle Time and Waiting Time of Job
7.5. Flow Time Tk(iq)
7.6. Recurrence Relation for Flow Time Tk(iq)
7.7. Expressions of Makespan
7.8. Calculation of Machine Idle Time
7.9. Flow Network Expression in Critical Path Method
7.10. Critical Path Length between Two Nodes and Makespan
7.11. Two-Machine Min-Makespan Problem
7.12. Solution by Using Machine Idle Time
7.13. Solution by Dynamic Programming
7.14. Solution by using Flow Time T2(i)
7.15. Working Rules
7.16. General Working Rule
7.17. Restricted Working Rule
Bibliography and Comments
8. Flow-Shop Scheduling Problems: Analytical Results II and Extensions
8.1. Introduction
8.2. Three-Machine Min-Makespan Problem
8.3. Limited Solution under Special Processing Times
8.4. Solution by Using Machine Idle Time
8.5. Formulation by Flow Times T2(i), T3(i)
8.6. Flow Times T2(i), T3(i) and Makespan
8.7. Recurrence Relation between T2(iq), T3(ig) (q = 1, 2, ... , n)
8.8. Dynamic Programming-Type Formulation
8.9. Values of T3(i), T3(ij), and T3(j), T3(ji)
8.10. Proof by Using Flow Times
8.11. Case (a)
8.12. Case (b)
8.13. Limited Solution under Other Special Processing Times
8.14. Sufficient Conditions for Two Adjacent Jobs to be in a Definite Order in the Optimal Sequence
8.15. Sufficient Inequalities not Including T2(l) and T3(l)
8.16. Sufficient Inequalities that Satisfy the Transitive Property
8.17. Two-Machine Min-Makespan Problem where Time Lags Exist
8.18. On the Generalizations to m Machine Permutation Scheduling
Bibliography and Comments
9. Flow-Shop Scheduling Problems: General Solutions
9.1. Introduction
9.2. m Machine Min-Makespan Problem (m≥3, no Passing is Allowed)
9.3. Concrete Procedures in BAB Algorithms
9.4. BAB Algorithms for Flow Shops
9.5. Standard Lower Bound
9.6. Efficiency of BAB Algorithm
9.7. Relations Between Machine Order, Processing Times, and Optimal Sequence
9.8. Revised Lower Bound and Composite Lower Bound
9.9. Backtrack Programming and Lexicographical Search Method
9.10. m Machine Min-Mean Completion Time Problem
9.11. A Lemma and Analytical Results
9.12. A BAB Algorithm
9.13. m Machine Min-Penalty Cost by Tardiness Problem
9.14. Backtrack Programming and Lexicographical Search Method
9.15. A BAB Algorithm and its Lower Bound
Bibliography and Comments
10. Flow-Shop Scheduling Problems: Unified Algorithms and Approximate Solutions
10.1. Introduction
10.2. Unified Multistage Combinatorial Algorithms for Setup-time Imbedded Processing Times
10.3. A Formulation by the State Transformation Process
10.4. Simple Function q(F, P(Sk)) for Each Objective Function F
10.5. Relation between Min-Makespan Problem and Min-Other Objective Problems
10.6. Unified Multistage Combinatorial Algorithm
10.7. Application to Parallel Scheduling
10.8. Numerical Examples of Min-Mean Intermediate Waiting-Time Problem and Related Parallel Scheduling
10.9. Unified Multistage Combinatorial Algorithm where Explicit Setup Times Exist
10.10. Setup Times
10.11. A Formulation by the State Transformation Process
10.12. Approximate Algorithms for Min-Makespan Problem
10.13. Application of a Specified Function to Construct an Approximate Sequence Bibliography and Comments
11. Flow-Shop Scheduling under Sequence Dependence Conditions
11.1. Sequence Dependent Setup Times
11.2. Problem Definition
11.3. Optimality of Permutation Schedules
11.4. Dynamic Programming Formulations for ID and DI
11.5. Forward DP Recursion for Problem Type ID
11.6. Computational Aspects
11.7. Backward DP Recursion for Problem Type DI
11.8. Implications of Theorem 3
11.9. Computational Aspects
11.10. Discussion of the Dynamic Programming Approach
11.11. Optimal Schedules for Problem Types DII, IDI and IID
11.12. Dominance Conditions for Problem Types DII, IDI, and IID
11.13. Backward Dynamic Programming Formulations
11.14. Reducing Dimensionality
11.15. Selection of Value for c1
11.16. Computational Requirements
11.17. Extensions
Bibliography and Comments
12. The Job-Shop Scheduling Problem
12.1. Introduction
12.2. The n x 2 Min-Makespan Problem
12.3. Graphical Solution of the 2 x m Min-Makespan Problem
12.4. Graphical Representation of the Schedule
12.5. Construction of the Path
12.6. Approaches by Integer Linear Programming
12.7. Standard Formulation by ILP
12.8. BAB Algorithms by following Active Schedule Generation Procedure
12.9. BAB Algorithm by Active Schedule Generation Procedure
12.10. BAB Algorithm I
12.11. Lower Bound in BAB Algorithm I
12.12. Graph G0 = (X, Z) Expressing Orderings
12.13. Disjunctive Graph Representation by Limited Machine Availability
12.14. BAB Algorithm on Disjunctive Graphs by following an Active Schedule Generation Procedure
12.15. BAB Algorithm by Resolving the Pairs of Disjunctive Arcs on a Disjunctive Graph
12.16. Representation by Graph G0 = (X, Z)
12.17. Conflict Set
12.18. Disjunctive Graph
12.19. Complete Selection of Disjunctive Arcs and Schedules
12.20. Formulation of Two Types
12.21. BAB Algorithm by Partial Selection of Disjunctive Arcs
12.22. Generalization of the Sequencing Problem: The Multiproject Scheduling Problem with Limited Resources
12.23. Solution Based on Disjunctive Graphs
12.24. Problem Statement
12.25. Conflict Set
12.26. Disjunctive Graphs Based on Conflict Sets of Activities
12.27. Formulation by Disjunctive Graph
12.28. BAB and EXTBAB Algorithms by Partial Selection of Disjunctive Arcs
12.29. BAB Algorithm
12.30. Justification of Proposed BAB Algorithm and Remarks
12.31. Numerical Examples by BAB Algorithm and Related EXTBAB Algorithm
Bibliography and Comments
Author Index
Subject Index
Product details
- No. of pages: 344
- Language: English
- Copyright: © Pergamon 2013
- Published: January 1, 1982
- Imprint: Pergamon
- eBook ISBN: 9781483137445
About the Authors
R. Bellman
A. O. Esogbue
I. Nabeshima
About the Editor
E. Y. Rodin
Ratings and Reviews
There are currently no reviews for "Mathematical Aspects of Scheduling and Applications"