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. ? 2001 Elsevier Science B.V. All rights reserved.
['Sergey V. Sevastianov', 'Gerhard J. Woeginger']
Linear time approximation scheme for the multiprocessor open shop problem