Scheduling no-wait robotic cells with two and three machines

A no-wait robotic cell is an automated m -machine flow shop in which one robot is used to move the parts from a machine to the next, as well as between the machines and the input/output devices. Parts are not allowed to wait, either on a machine or on the robot. The problem is to sequence the parts and, concurrently, schedule the robot moves in order to maximize productivity. In the two-machine case, we show that the problem is solvable in time O( n log n ) by reducing it to the classical two-machines no-wait flow shop. For the three-machine case and identical parts, it is shown that it is sufficient to consider robot move cycles in which all the machines are visited once or twice.