Premium
Approximations to Optimal k ‐Unit Cycles for Single‐Gripper and Dual‐Gripper Robotic Cells
Author(s) -
Geismar H. Neil,
Chan Lap Mui Ann,
Dawande Milind,
Sriskandarajah Chelliah
Publication year - 2008
Publication title -
production and operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.279
H-Index - 110
eISSN - 1937-5956
pISSN - 1059-1478
DOI - 10.3401/poms.1080.0053
Subject(s) - dual (grammatical number) , scheduling (production processes) , computer science , robot , mathematical optimization , job shop scheduling , sequence (biology) , time complexity , algorithm , mathematics , artificial intelligence , routing (electronic design automation) , embedded system , art , literature , biology , genetics
We consider the problem of scheduling operations in bufferless robotic cells that produce identical parts using either single‐gripper or dual‐gripper robots. The objective is to find a cyclic sequence of robot moves that minimizes the long‐run average time to produce a part or, equivalently, maximizes the throughput. Obtaining an efficient algorithm for an optimum k ‐unit cyclic solution ( k ≥ 1) has been a longstanding open problem. For both single‐gripper and dual‐gripper cells, the approximation algorithms in this paper provide the best‐known performance guarantees (obtainable in polynomial time) for an optimal cyclic solution. We provide two algorithms that have a running time linear in the number of machines: for single‐gripper cells (respectively, dual‐gripper cells), the performance guarantee is 9/7 (respectively, 3/2). The domain considered is free‐pickup cells with constant intermachine travel time. Our structural analysis is an important step toward resolving the complexity status of finding an optimal cyclic solution in either a single‐gripper or a dual‐gripper cell. We also identify optimal cyclic solutions for a variety of special cases. Our analysis provides production managers valuable insights into the schedules that maximize productivity for both single‐gripper and dual‐gripper cells for any combination of processing requirements and physical parameters.