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.