Approximations to optimal k-unit cycles for single-gripper and dual-gripper robotic cells

• 成果类型: Article
• 署名作者: Geismar, H. Neil; Chan, Lap Mui Ann; Dawande, Milind; Sriskandarajah, Chelliah
• 署名单位: Texas A&M University System; Texas A&M University College Station; Mays Business School; Virginia Polytechnic Institute & State University; University of Texas System; University of Texas Dallas
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.3401/poms.1080.0053
• 发表日期: 2008
• 页码: 551-563
• 关键词: robotic cells; dual-gripper robots; Manufacturing; cyclic solutions; Approximation algorithms

摘要

W e 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.