A (10/7)-approximation algorithm for an optimum cyclic solution in additive travel-time robotic cells Academic Article

abstract

• 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.

authors

• Geismar, H.
• Sriskandarajah, Chelliah

published proceedings

• IIE Transactions

author list (cited authors)

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

citation count

• 6

complete list of authors

• Geismar, H Neil||Dawande, Milind||Sriskandarajah, Chelliah

publication date

• January 2007

publisher

• Taylor & Francis  Publisher

published in

• IIE Transactions  Journal

keywords

• Approximation Algorithms.
• Cyclic Solutions
• Robotic Cells

Digital Object Identifier (DOI)

• 10.1080/07408170600735587

start page

• 217

end page

• 227

volume

• 39

issue

• 2

URL

• http://dx.doi.org/10.1080/07408170600735587