Deterministic Processor Scheduling

Publisher Website
Google Scholar
Abstract
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.