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

  1. Alcaide López de Pablo, David
  2. Levner, Eugene
  3. Kats, Vladimir
Livre:
XXX Congreso Nacional de Estadística e Investigación Operativa y de las IV Jornadas de Estadística Pública: actas

É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.