A faster polynomial algorithm for 2-cyclic robotic scheduling

作者：Chu CB^*

来源：Journal of Scheduling, 2006, 9(5): 453-468.

DOI：10.1007/s10951-006-8501-1

• cyclic scheduling
• hoist scheduling
• no-wait flowshop
• polynomial algorithm
• complexity

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 N is the number of tanks in the production line. This paper proposes an improved algorithm with reduced complexity O(N-5 log N).

• 出版日期2006-10
• 单位合肥工业大学