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. (C) 2000 Elsevier Science B.V. All rights reserved.