A polynomial algorithm for 2-degree cyclic robot scheduling

This paper studies the 2-degree cyclic scheduling of identical parts in a no-wait robotic flow shop where exactly two parts enter and leave the production line in a cycle. The objective is to minimize the cycle time. We propose a polynomial algorithm to find an optimal 2-degree cyclic schedule of robot moves. The algorithm can be implemented in O(N⁸ log N) where N is the number of machines in the considered robotic cell. The proposed algorithm is also extended to problems where the two parts are not identical. Computational results is presented to test and evaluate the proposed algorithm.