Cyclic scheduling of identical parts in a robotic cell

We consider a robotic flowshop in which one type of product is to be repeatedly produced and where transportation of the parts between the machines is performed by the robot. The identical parts cyclic scheduling problem is then to find a shortest cyclic schedule for the robot, i.e., a sequence of robot moves that can be repeated infinitely many times and has minimum cycle time. This problem has been solved by Sethi et al. (1992) when m <= 3. In this paper, we considerably generalize their results by proving that the identical parts cyclic scheduling problem can be solved in time polynomial in m, where m denotes the number of machines in the shop. In particular, we present a dynamic programming approach that allows to solve the problem in O(m^3) time. Our analysis heavily relies on the concept of pyramidal permutation, a concept previously investigated in connection with the traveling salesman problem.