Article ID: | iaor200686 |
Country: | Netherlands |
Volume: | 162 |
Issue: | 2 |
Start Page Number: | 291 |
End Page Number: | 309 |
Publication Date: | Apr 2005 |
Journal: | European Journal of Operational Research |
Authors: | Sriskandarajah Chelliah, Dawande Milind, Geismar H. Neil |
Keywords: | production: FMS, heuristics |
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.