Approximation algorithms for k-unit cyclic solutions in robotic cells

Approximation algorithms for k-unit cyclic solutions in robotic cells

0.00 Avg rating0 Votes
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: , ,
Keywords: production: FMS, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.