Approximation algorithms for k-unit cyclic solutions in robotic cells
- Additional Document Info
- View All
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.
author list (cited authors)
Geismar, H. N., Dawande, M., & Sriskandarajah, C.
complete list of authors
Neil Geismar, H||Dawande, Milind||Sriskandarajah, Chelliah