On an automated two-machine flowshop scheduling problem with infinite buffer

This paper discusses a new flowshop scheduling problem related to automated manufacturing systems such as FMS’s and FMC’s. An AGV (Automated Guided Vehicle) or a robot hand sends jobs one by one between infinite buffers attached to machines. The problem is shown to be located between the traditional two-machine and the three-machine flowshop scheduling problems. It is shown that the present problem is NP-hard. This means that the three-machine flowshop scheduling problem is NP-hard, even if all jobs have the same processing time on the second machine that is the AGV in the problem, and on the contrary the present problem enjoys many solvable cases which have been found so far for the three-machine flowshop scheduling problem.