## RenĂ© van Bevern and Artem V. Pyatkin.
A fixed-parameter algorithm for a routing open shop problem: unit
processing times, few machines and locations.
2017.

The open shop problem is to find a minimum makespan
schedule to process each job Ji on each machine Mq
for piq time such that, at any time, each machine
processes at most one job and each job is processed
by at most one machine. We study a problem variant
in which the jobs are located in the vertices of an
edge-weighted graph. The weights determine the time
needed for the machines to travel between jobs in
different vertices. We show that the problem with m
machines and n unit-time jobs in g vertices is
solvable in 2O(gm2loggm)+O(mnlogn) time.

[ bib |
slides |
http ]
Back

*This file was generated by
bibtex2html 1.98.*