Multidegree cyclic scheduling of a nowait robotic cell with multiple robots
This paper addresses cyclic scheduling of a nowait robotic cell with multiple robots. In contrast to many previous studies, we consider rdegree cyclic (rÂ >Â 1) schedules, in which r identical parts with constant processing times enter and leave the cell in each cycle. We propose an algorithm to find the minimal number of robots for all feasible rdegree cycle times for a given r (rÂ >Â 1). Consequently, the optimal rdegree cycle time for any given number of robots for this given r can be obtained with the algorithm. To develop the algorithm, we first show that if the entering times of r parts, relative to the start of a cycle, and the cycle time are fixed, minimizing the number of robots for the corresponding rdegree schedule can be transformed into an assignment problem. We then demonstrate that the cost matrix for the assignment problem changes only at some special values of the cycle time and the part entering times, and identify all special values for them. We solve our problem by enumerating all possible cost matrices for the assignment problem, which is subsequently accomplished by enumerating intervals for the cycle time and linear functions of the part entering times due to the identification of the special values. The algorithm developed is shown to be polynomial in the number of machines for a fixed r, but exponential if r is arbitrary.
Year of publication: 
2009


Authors:  Che, Ada ; Chu, Chengbin 
Published in: 
European Journal of Operational Research.  Elsevier, ISSN 03772217.  Vol. 199.2009, 1, p. 7788

Publisher: 
Elsevier 
Keywords:  Cyclic scheduling Nowait Robotic cells Cycle time 
Saved in favorites
Similar items by person

A polynomial algorithm for 2degree cyclic robot scheduling
Che, Ada, (2003)

Lei, Weidong, (2014)

Robust optimization for the cyclic hoist scheduling problem
Che, Ada, (2015)
 More ...