Approximation algorithms for k-unit cyclic solutions in robotic cells Academic Article uri icon


  • This paper considers the problem of scheduling operations in bufferless robotic cells that produce identical parts. Finding a multi-unit cyclic solution which minimizes the long-run average time to produce a part is an open problem. Most research has been focused on finding an optimal 1-unit cyclic solution. However, it is known that an optimal multi-unit cyclic solution can be better than an optimal 1-unit cyclic solution for cells with four or more machines. We present polynomial algorithms that produce multi-unit cyclic solutions whose per unit cycle times are within a constant factor of the optimum for the three most common classes of robotic cells viz., additive, constant, and Euclidean travel-time. The approximation guarantees obtained for these three classes of cells are 1.5, 1.5, and 4, respectively. As a by-product, we obtain upper bounds on the difference in the per unit cycle times between an optimal multi-unit cycle and an optimal 1-unit cycle for each of these three classes of cells. 2003 Elsevier B.V. All rights reserved.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Geismar, H. N., Dawande, M., & Sriskandarajah, C.

citation count

  • 35

complete list of authors

  • Geismar, H Neil||Dawande, Milind||Sriskandarajah, Chelliah

publication date

  • April 2005