Approximations to optimal sequences in single-gripper and dual-gripper robotic cells with circular layouts

Kyung Sung Jung, H. Neil Geismar, Michael Pinedo and Chelliah Sriskandarajah

IISE Transactions, 2015, vol. 47, issue 6, 634-652

Abstract: This article considers the problems of scheduling operations in single-gripper and dual-gripper bufferless robotic cells in which the arrangement of machines is circular. The cells are designed to produce identical parts under the free-pickup criterion with additive intermachine travel time. The objective is to find a cyclic sequence of robot moves that minimizes the long-run average time required to produce a part or, equivalently, that maximizes the throughput. Obtaining an efficient algorithm for an approximation to an optimal k-unit cyclic solution (over all k ≥ 1) is the focus of this article. The proposed algorithms introduce a new class of schedules, which are refered to as epi-cyclic cycles. A polynomial algorithm with a 5/3-approximation to an optimal k-unit cycle over all cells is developed. The performed structural analysis for dual-gripper cells leads to a polynomial-time algorithm that provides at worst a 3/2-approximation for the practically relevant case in which the dual-gripper switch time is less than twice the intermachine robot movement time. A computational study demonstrates that the algorithm performs much better on average than this worst-case bound suggests. The performed theoretical studies are a stepping stone for researching the complexity status of the corresponding domain. They also provide theoretical as well as practical insights that are useful in maximizing productivity of any cell configuration with either type of robot.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2014.937019 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:47:y:2015:i:6:p:634-652

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2014.937019

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().