Scheduling in robotic cells: Complexity and steady state analysis

This paper considers the scheduling of operations in a manufacturing cell that repetitively produces a family of similar parts on several machines served by a robot. The decisions to be made include finding the robot move cycle and the part sequence that jointly minimize the production cycle time, or equivalently maximize the throughput rate. We focus on complexity issues and steady state performance. In a three machine cell producing multiple part-types, we prove that in two out of the six potentially optimal robot move cycles for producing one unit, the recognition version of the part sequencing problem is unary NP-complete. The other four cycles have earlier been shown to define efficiently solvable part sequencing problems. The general part sequencing problem not restricted to any robot move cycle in a three machine cell is shown to be unary NP-complete. Finally, we discuss the ways in which a robotic cell converges to a steady state.