Approximations to optimal k-unit cycles for single-gripper and dual-gripper robotic cells Academic Article uri icon


  • We consider the problem of scheduling operations in bufferless robotic cells that produce identical parts using either single-gripper or dual-gripper robots. The objective is to find a cyclic sequence of robot moves that minimizes the long-run average time to produce a part or, equivalently, maximizes the throughput. Obtaining an efficient algorithm for an optimum k-unit cyclic solution (k 1) has been a longstanding open problem. For both single-gripper and dual-gripper cells, the approximation algorithms in this paper provide the best-known performance guarantees (obtainable in polynomial time) for an optimal cyclic solution. We provide two algorithms that have a running time linear in the number of machines: for single-gripper cells (respectively, dual-gripper cells), the performance guarantee is 9/7 (respectively, 3/2). The domain considered is free-pickup cells with constant intermachine travel time. Our structural analysis is an important step toward resolving the complexity status of finding an optimal cyclic solution in either a single-gripper or a dual-gripper cell. We also identify optimal cyclic solutions for a variety of special cases. Our analysis provides production managers valuable insights into the schedules that maximize productivity for both single-gripper and dual-gripper cells for any combination of processing requirements and physical parameters. 2008 Production and Operations Management Society.

published proceedings


author list (cited authors)

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

citation count

  • 20

complete list of authors

  • Geismar, H Neil||Chan, Lap Mui Ann||Dawande, Milind||Sriskandarajah, Chelliah

publication date

  • September 2008