
Accession Number : AD0666810
Title : MACHINE SEQUENCING VIA DISJUNCTIVE GRAPHS: AN IMPLICIT ENUMERATION ALGORITHM.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas,Egon
Report Date : FEB 1968
Pagination or Media Count : 20
Abstract : A disjunctive graph is a generalized graph some of whose arcs are disjunctive. Such graphs translate a variety of schedulingtype problems, like machine sequencing. The latter problem can be reduced to that of finding a minimaximal path (shortest critical path) in a disjunctive PERT network. The present paper describes an implicit enumeration algorithm for finding such a path by solving a sequence of PERT problems. The algorithm finds at an early stage a local optimum; thus one can stop at any moment with a reasonably 'good' feasible solution. The number of PERT problems whose data are to be stored at any given moment cannot exceed the number of disjunctive pairs of arcs. (Author)
Descriptors : (*OPERATIONS RESEARCH, SCHEDULING), (*PRODUCTION CONTROL, SCHEDULING), (*SCHEDULING, GRAPHICS), SET THEORY, ITERATIONS, MINIMAX TECHNIQUE, OPTIMIZATION, MANAGEMENT PLANNING AND CONTROL, ALGORITHMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE