Deterministic Processor Scheduling
Mario J. Gonzalez · ACM Computing Surveys · 1977
This paper surveys the deterministic scheduling of jobs m uniprocessor, multiprocessor, and job-shop environments.The survey begins with a brief introduction to the representation of task or job sets, followed by a discussion of classification categories.These categories include number of processors, task interruptlbility, job periodicity, deadlines, and number of resources.Results are given for single-processor schedules in job-shop and multIprogramming environments, flow-shop schedules, and multiprocessor schedules.They are stated in terms of optimal constructive algorithms and suboptimal heuristics.In most cases the latter are stated in terms of performance bounds related to optimal results.Annotations for most of the references are provided in the form of a table classifying the referenced studies m terms of various parameters.
Cited by 216 works. doi:10.1145/356698.356700 Open-access PDF
Authors
References
- The complexity of theorem-proving procedures
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
- Optimal two‐ and three‐stage production schedules with setup times included
- Bounds for Certain Multiprocessing Anomalies
- Production and Stabilization of Real-Time Task Schedules
- Scheduling with Deadlines and Loss Functions
- Bounds on Multiprocessing Timing Anomalies
- Operating System Principles
- Parallel Sequencing and Assembly Line Problems
- Operating Systems Theory