Linear time approximation scheme for the multiprocessor open shop problem

S.V. Sevastianov (sevamath.nsc.ru)
G.J. Woeginger (gwoegiopt.math.tu-graz.ac.at)

Abstract: For the $r$-stage open shop problem with identical parallel machines at each stage and the minimum makespan criterion, an approximation scheme is constructed with running time $O(nrm + C(m,\eps))$ , where $n$ is the number of jobs, $m$ is the total number of machines, and $C(m,\eps)$ is a function independent of $n$.

Keywords: Scheduling; Open shop; Approximation scheme

Category 1: Applications -- OR and Management Sciences (Scheduling )

Citation: Discrete Appl. Math. 114 (2001), 273-288.

Download:

Entry Submitted: 02/23/2001
Entry Accepted: 02/23/2001
Entry Last Modified: 11/01/2001

Modify/Update this entry