A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

Abstract

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.

Keywords:

• robotic cell
• cyclic scheduling
• processing time windows
• method of prohibited intervals
• branch and bound algorithm

Acknowledgements

This work was partially supported by the National Natural Science Foundation of China under Grant No. 50605052 and the Program for New Century Excellent Talents in Universities of Ministry of Education, China, under Grant No. NCET-06-0875.