Cyclic scheduling of processes in robotic cells characterized by directed acyclic graphs

Resumen

We consider a multiple-product, multiple-robot, 1-cyclic scheduling problem in a robotic assembly/disassembly system. The durations of the processing, setup, and transportation operations are controllable decision variables lying in given time intervals ("time windows"). The precedence relations between assembly/disassembly operations of any job are given in the form of a general directed acyclic graph, rather than a chain. The objective is to maximize the cell performance, or, equivalently, to minimize the cyclic time. The problem generalizes several known polynomial-solvable cyclic scheduling problems. The cyclic problem considered is equivalent to the parametric critical path problem on a network which is a further development of the network constructed by Alcaide et al. (EJOR, vol. 177, pp. 147-162, 2007). In spite of the above generalizations, the problem complexity, even though not as good as that for a single-product case, still remains polynomial.