Scheduling of parts and robot activities in a two machine robotic cell

We consider a scheduling problem arising in a two machine flexible robotic cell that repetitively produces parts of different types. We consider the two decisions that need to be made simultaneously: finding the robot move cycle, and finding the input part sequence. The objective is to maximize the throughput rate of the cell subject to the condition that parts are to be produced in proportion to their demand. The problem can be formulated as a special kind of traveling salesman problem. An O(n⁴) time algorithm which solves this problem optimally has been provided in Hall et al. In this paper, we extend their work and provide an algorithm of complexity O(n log n).