Abstract

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.” This paper presents an introduction to this approach by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible. The paper concludes with a brief survey of what has been accomplished to date in the area of scheduling using this approach.

Keywords

Computer scienceScheduling (production processes)Multiprocessor schedulingMultiprocessingScheduleAlgorithmDynamic priority schedulingTwo-level schedulingMathematical optimizationDistributed computingParallel computingMathematics

Related Publications

Publication Info

Year
1978
Type
article
Volume
26
Issue
1
Pages
3-21
Citations
129
Access
Closed

External Links

Social Impact

Social media, news, blog, policy document mentions

Citation Metrics

129
OpenAlex

Cite This

M. R. Garey, Ronald Graham, David S. Johnson (1978). Performance Guarantees for Scheduling Algorithms. Operations Research , 26 (1) , 3-21. https://doi.org/10.1287/opre.26.1.3

Identifiers

DOI
10.1287/opre.26.1.3