A faster polynomial algorithm for 2-cyclic robotic scheduling

摘要

This paper addresses the 2-cyclic identical part scheduling in a no-wait robotic flowshop where exactly two parts enter and two parts leave the production line during each cycle. This problem was previously proved to be polynomially solvable in O(N~8 log N) time, where iV is the number of tanks in the production line. This paper proposes an improved algorithm with reduced complexity O(N~5 log N).