direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

A fixed-parameter algorithm for a routing open shop problem: unit processing times, few machines and locations

René van Bevern (Novosibirsk State University and Sobolev Institute of Mathematics)

The open shop problem is to find a minimum makespan schedule to process each job \(J_i\) on each machine \(M_q\) for \(p_{iq}\) 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 \(2^{O(gm^2\log gm)}+O(mn\log n)\) time.

René van Bevern
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras