MACHINE SEQUENCING VIA DISJUNCTIVE GRAPHS: AN IMPLICIT ENUMERATION ALGORITHM.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1968
- Accession Number
- AD0666810
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University