SCHEDULING PROBLEMS WITH INTERVAL DISJUNCTIONS.
STANFORD UNIV CALIF OPERATIONS RESEARCH HOUSE
Pagination or Media Count:
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
- Operations Research