Linear time approximation scheme for the multiprocessor open shop problem

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$.


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