Scheduling, Sequencing and Networks,

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