Cyclic scheduling of identical parts in a robotic cell
成果类型：
Article
署名作者：
Crama, Y; Van de Klundert, J
署名单位：
University of Liege; Maastricht University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.6.952
发表日期：
1997
页码：
952-965
关键词：
摘要：
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 less than or equal to 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.