Cyclic scheduling of identical parts in a robotic cell

Research output: Contribution to journalArticlepeer-review

150 Scopus citations

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. (1992) 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(m3) time. Our analysis relies heavily on the concept of pyramidal permutation, a concept previously investigated in connection with the traveling salesman problem.

Original languageEnglish
Pages (from-to)952-965
Number of pages14
JournalOperations Research
Volume45
Issue number6
DOIs
StatePublished - 1997
Externally publishedYes

Fingerprint

Dive into the research topics of 'Cyclic scheduling of identical parts in a robotic cell'. Together they form a unique fingerprint.

Cite this