A linear time approximation scheme for makespan minimization in an open shop with release dates

The existence of a linear time approximation scheme for makespan minimization was demonstrated in the multiprocessor open shop problem with release dates. The approximation scheme was linear and didn't require solving linear program.