AUTOMATED 2-MACHINE FLOWSHOP SCHEDULING - A SOLVABLE CASE

This paper considers new flowshop scheduling problems related to automated manufacturing systems in which n jobs are processed on two machines M(a) and M(b) in this order. The job transportation between two machines is done by a single automated guided vehicle (AGV), and is crucial because no machine has buffer storage for work-in-process (WIP) and hence a machine cannot release a finished job until the empty AGV becomes available at that machine, while the AGV cannot transfer an unfinished job to a machine until the machine is empty. O(n3) algorithms are given in this paper to find optimal sequences of n jobs that minimize their maximum completion time (i.e., makespan). Some numerical results are also given to evaluate the effect of computing optimal sequences.