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

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.