Automated Two-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 Ma and Mb 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(n 3) 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.