Mathematical Aspects of Scheduling and Applications

Modern Applied Mathematics and Computer Science

1st Edition - January 1, 1982
Authors: R. Bellman, A. O. Esogbue, I. Nabeshima
Editor: E. Y. Rodin
Language: English
eBook ISBN:
9 7 8 - 1 - 4 8 3 1 - 3 7 4 4 - 5

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… Read more

Purchase options

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Institutional subscription on ScienceDirect

Request a sales quote

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.

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