A 10/7-Approximation Algorithm for an Optimum Cyclic Solution in Additive Travel-time Robotic Cells

February 2015 | Geismar, Neil

This paper considers the problem of scheduling operations in
bufferless robotic cells that produce identical parts. Finding a
cyclic solution that minimizes the long-run average time to
produce a part has long been a fundamental 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. For additive travel-time cells,
we present a linear-time algorithm that produces a cyclic solution
whose per unit cycle time is within a factor of 10/7 of
the optimum. This result improves the current best
3/2-approximation guarantee.



  • Dawande, Milind
  • Sriskandarajah, Chelliah


IIE Transactions