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.