Solution of the Flowshop-Scheduling Problem with No Intermediate Queues

This paper presents an algorithm that will minimize the total processing time for a particular case of the n-job, m-machine scheduling problem. In many industrial processes, jobs are processed by a given sequence of machines. Often, once the processing of a job commences, the job must proceed immediately from one machine to the next without encountering any delays en route. The machine sequence need not be the same for an jobs. Because of this processing constraint that prohibits intermediate queues, most normal scheduling techniques are not applicable. This paper obtains a solution to this constrained scheduling problem by modeling it as a traveling-salesman problem; known solution techniques can then be employed. The paper solves a sample problem and discusses computational considerations.