SCHEDULING PROBLEMS WITH INTERVAL DISJUNCTIONS.

Abstract

Interval disjunctions arise in scheduling problems when the durations of some jobs are constrained not to overlap. Such situations are found in production scheduling, project scheduling, traffic light scheduling, etc. A general class of deterministic scheduling problems with interval disjunctions is defined in the paper. The structure of its solution set is studied in connection with the theory of potentials on a graph. A branch-and-bound algorithm is described for the case where the objective function is to minimize the total duration; optimal and heuristic variants of the algorithm are discussed. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1970
Accession Number
AD0706021

Entities

People

  • Bernard G. Sussmann

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Contract Administration
  • Contracts
  • Engineering
  • Intervals
  • Production
  • Scheduling (Production)

Readers

  • Operations Research