CYCLIC SCHEDULING OF IDENTICAL PARTS IN A ROBOTIC CELL

We consider a robotic flowshop in which one type of product is to be r epeatedly produced, and where transportation of the parts between the machines is performed by a robot. The identical parts cyclic schedulin g problem is then to find a shortest cyclic schedule for the robot; i. e., a sequence of robot moves that can be infinitely repeated and that has minimum cycle time. This problem has been solved by Sethi et al. (1992) when m less than or equal to 3. In this paper, we generalize th eir results by proving that the identical parts cyclic scheduling prob lem can be solved in time polynomial in m, where m denotes the number of machines in the shop. In particular, we present a dynamic programmi ng approach that allows us to solve the problem in O(m(3)) time. Our a nalysis relies heavily on the concept of pyramidal permutation, a conc ept previously investigated in connection with the traveling salesman problem.