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

Original language | English |
---|---|

Pages (from-to) | 952-965 |

Number of pages | 14 |

Journal | Operations Research |

Volume | 45 |

Issue number | 6 |

DOIs | |

State | Published - 1997 |

Externally published | Yes |