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.
Inhalt
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. a-Optimal Schedule and Non-a-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. …