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.
