Computing near-optimal schedules

We survey a number ofresults on computing near-optimal solutions for .N'P'-hard scheduling problems. For many .N'P'-hard optimization problems there are polynomial-time approximation algorithms for finding solutions that are provably quite close to the optimum, whereas for others no such algorithm is known. We concentrate on results that state that certain performance guarantees are unlikely to be attained, in the sense that if there is such a good algorithm, then P'= N P. In particular, we survey results for multiprocessor scheduling and shop scheduling problems