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.