Cyclic Scheduling of Identical Parts in a Robotic Cell

Operations Research · 1997 · Volume 45 · Issue 6

Abstract

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 a 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 infinitely repeated and that has minimum cycle time. This problem has been solved by Sethi et al. (Sethi, S. P., C. Sriskandarajah, G. Sorger, J. Blazewicz, W. Kubiak. 1992. Sequencing of parts and robot moves in a robotic cell. Internat. J. Flexible Manufacturing Systems 4 331–358.) when m ≤ 3. In this paper, we 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 us to solve the problem in O ( m 3 ) time. Our analysis relies heavily on the concept of pyramidal permutation, a concept previously investigated in connection with the traveling salesman problem.

Keywords

manufacturing, automated systems, materials handling in robotic cells, production/scheduling, sequencing, flow shop, cycle time minimization, dynamic programming, deterministic, traveling salesman, pyramidal permutations

Enable JavaScript for citation tools and additional paper interactions.