Accession Number : AD0666810

Title :   MACHINE SEQUENCING VIA DISJUNCTIVE GRAPHS: AN IMPLICIT ENUMERATION ALGORITHM.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON 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 scheduling-type 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