Linear time approximation scheme for the multiprocessor open shop problem Original Research Article

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,ε)), where n is the number of jobs, m is the total number of machines, and C(m,ε) is a function independent of n.