PERFORMANCE GUARANTEES FOR SCHEDULING ALGORITHMS

One approach to coping with the apparent difficulty of many schedule-optimization problems, such as occur in machine shops and computer processing, is to devise efficient algorithms that find schedules guaranteed to be ″near-optimal.″ An introduction to this approach is given by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible. A brief survey of what has been accomplished to date in the area of scheduling using this approach is presented.