Scheduling Multiple Parts in Two-Machine Dual-Gripper Robot Cells: Heuristic Algorithm and Performance Guarantee

Abstract

A robotic cell is a manufacturing system that is widely used in industry. Our research concerns scheduling of multiple products in a robotic cell served by a dual-gripper robot. The cell contains two robot-served machines repetitively producing a set of multiple parts in a steady state. The processing constraints specify the cell to be a flow shop. The purpose is to find simultaneously a robot move sequence and a part sequence that minimize the production cycle time or, equivalently, maximize the throughput rate. It is known that the problem of finding an optimal part sequence is strongly NP-hard, even when the robot move sequence is given. The intractable problem of part sequencing in a twomachine dual-gripper robot cell is the main subject of our investigation. We provide a unified notational and modeling framework to study the family of all those NP-hard problems that are associated with the potentially optimal robot move sequences. The main result is the development of an approximation algorithm with a worst-case performance ratio guarantee of 3/2. A linear program is used to establish the performance ratio without actually calculating a lower bound. This approach is original in the literature of scheduling robotic cells.