Cyclic Scheduling of Identical Parts in a Robotic Cell

Yves Crama and Joris van de Klundert
Additional contact information
Yves Crama: Université de Liège, Liège, Belgium
Joris van de Klundert: Maastricht University, Maastricht, The Netherlands

Operations Research, 1997, vol. 45, issue 6, 952-965

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 (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.6.952 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:6:p:952-965

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().