## René van Bevern and Artem V. Pyatkin.
Completing partial schedules for open shop with unit processing times
and routing.
In *Proceedings of the 11th International Computer Science
Symposium in Russia (CSR'16), St. Petersburg, Russian Federation*, volume
9691 of *Lecture Notes in Computer Science*, pages 73–87. Springer,
2016.

Open Shop is a classical scheduling problem: given a
set J of jobs and a set M of machines, find a
minimum-makespan schedule to process each job J_i∈J on
each machine M_q∈M for a given amount p_iq of time
such that each machine processes only one job at a
time and each job is processed by only one machine at
a time. In Routing Open Shop, the jobs are located in
the vertices of an edge-weighted graph G=(V,E) whose
edge weights determine the time needed for the
machines to travel between jobs. Routing Open Shop is
NP-hard for |V|=|M|=2. For the special case of unit
processing times p_iq=1, we exploit Galvin's theorem
about list-coloring edges of bipartite graphs to prove
a theorem that gives a sufficient condition for the
completability of partial schedules. Exploiting this
schedule completion theorem and integer linear
programming, we show that Routing Open Shop with unit
processing times is solvable in 2^O(|V||M|^2 log
|V||M|) poly(|J|)) time, that is, fixed-parameter
tractable parameterized by |V|+|M|. Various upper
bounds shown using the schedule completion theorem
suggest it to be likewise beneficial for the
development of approximation algorithms.

[ bib |
DOI |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*