#### 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 two-machine 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.