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

摘要

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.