On a conjecture about robotic cells: New simplified proof for the three-machine case

We consider a robotic cell, consisting of a flow-shop in which the machines are served by a single central robot. We concentrate on the case where only one part type is produced and want to analyze the conjecture of Sethi, Sriskandarajah, Sorger, Blazewicz and Kubiak. This well-known conjecture claims that the repetition of the best one-unit production cycle will yield the maximum throughput rate in the set of all possible robot moves. The conjecture holds for two and three machines, but the existing proof by van de Klundert and Crama for the three-machine case is extremely tedious. We adopt the theoretical background developed by Crama and van de Klundert. Using a particular state graph, the k-unit production cycles are represented as special paths and cycles for which general properties and bounds for the m-machine robotic cell can be obtained. By means of these concepts, we shall give a concise proof for the validity of the conjecture for the three-machine case.