Throughput Optimization in Circular Dual†Gripper Robotic Cells

Many automated manufacturing systems use robotic cells, which consist of a set of machines served by a robot. Robotic cells with a single†gripper robot have been extensively studied in the literature. By contrast, cells with a dual†gripper robot, although more productive, have received less attention, perhaps because of their inherent complexity. We consider the problem of scheduling operations in dual†gripper robotic cells that have the machines configured in a circular layout and that produce identical parts repetitively. A typical objective in practice is to find a 1†unit cyclic sequence of robot moves that maximizes the throughput. We show that dual†gripper cycles are not optimal in all cases. We establish conditions in which the problem of finding an optimal 1†unit cycle in dual†gripper cells is NP†hard. We show that the remaining cases are solvable by polynomial†time algorithms either optimally or within a guaranteed bound of the optimum. These results are extended to linear cells. A computational study demonstrates that the algorithm performs much better on average than this worst†case bound suggests. Our theoretical studies facilitate research into the complexity status of the corresponding domain. They also provide practical insights that are useful in maximizing productivity for any combination of cell parameters and either type of robot.