Scheduling, Sequencing and Networks,
Abstract
An optimal scheduling problem type of some generality is examined and found to possess an essential structure very similar to that of jobshop sequencing. It is also found to be, in essence, a simple but not quite ordinary network flow programming problem in which link capacities must be discovered during a solution process. This fact is exploited in the development of an optimal scheduling algorithm that minimizes total operation duration and takes advantage of the forward-backward symmetry inherent in scheduling (or sequencing) of the kind considered. No significant departure from the usual enumeration character of optimal sequencing algorithms is attained, though abbreviated enumeration is sought with some success. Indeed, one effect of the network analogy is to suggest that improvement over carefully managed enumeration in scheduling and sequencing will be very difficult to accomplish since the network structure is really present and is rather thoroughly exploited in the algorithm considered. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 11, 1971
- Accession Number
- AD0717943
Entities
People
- Fred D. Rigby
Organizations
- George Washington University