Cyclic scheduling of processes in robotic cells characterized by directed acyclic graphs
- Alcaide López de Pablo, David
- Levner, Eugene
- Kats, Vladimir
Éditorial: Comité organizador del XXX Congreso Nacional de Estadística e Investigación Operativa y IV Jornadas de Estadística Pública
ISBN: 978-84-690-7249-3
Année de publication: 2007
Congreso: Congreso Nacional de Estadística e Investigación Operativa (30. 2007. Valladolid)
Type: Communication dans un congrès
Résumé
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.