Accession Number : AD0706021

Title :   SCHEDULING PROBLEMS WITH INTERVAL DISJUNCTIONS.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CALIF OPERATIONS RESEARCH HOUSE

Personal Author(s) : Sussmann,Bernard G.

Report Date : MAR 1970

Pagination or Media Count : 43

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)

Descriptors :   (*SCHEDULING, ALGORITHMS), OPTIMIZATION, INEQUALITIES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE