Mathematical Aspects of Scheduling and Applications

Mathematical Aspects of Scheduling and Applications

Modern Applied Mathematics and Computer Science

1st Edition - January 1, 1982

Write a review

  • Authors: R. Bellman, A. O. Esogbue, I. Nabeshima
  • eBook ISBN: 9781483137445

Purchase options

Purchase options
DRM-free (PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order


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

Write a review

There are currently no reviews for "Mathematical Aspects of Scheduling and Applications"