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