A Geometric Model and a Graphical Algorithm for a Sequencing Problem

Abstract

A geometric model is given for the problem of scheduling N jobs on M machines so that the total time needed to complete the processing of all jobs is minimized. This model leads to a graphical algorithm, the essence of which is the determination of a shortest path between two nodes in a finite network. Particular attention is given to the case of 2 jobs for which the algorithm developed is simple and efficient. The theoretical analysis is then extended to the general case. Computational problems arise in the general case primarily because of the difficulty of constructing the network.