Abstract
Given a set @@@@ = { T 1 , T 2 ,···, T n } of tasks, with each T i having execution time 1 and a deadline d i > 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.
Keywords
Computer scienceScheduleScheduling (production processes)Set (abstract data type)Task (project management)Parallel computingNP-completeExecution timeMathematical optimizationAlgorithmComputational complexity theoryMathematicsProgramming language
Related Publications
Production and Stabilization of Real-Time Task Schedules
A model for multiprocessor control is considered in which jobs are broken into various pieces, called tasks . Tasks are executed by single processing units. In this paper the st...
Multiprogram scheduling
In order to exploit fully a fast computer which possesses simultaneous processing abilities, it should to a large extent schedule its own workload. The scheduling routine must b...
Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service....
An evolutionary approach to system-level synthesis
Considers system-level synthesis as the problem of optimally mapping a task-level specification onto a heterogeneous hardware/software architecture. This problem requires: (1) t...
Direct Search Methods on Parallel Machines
This paper describes an approach to constructing derivative-free algorithms for unconstrained optimization that are easy to implement on parallel machines. A special feature of ...
Publication Info
- Year
- 1976
- Type
- article
- Volume
- 23
- Issue
- 3
- Pages
- 461-467
- Citations
- 150
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
150
OpenAlex
Cite This
M. R. Garey,
David S. Johnson
(1976).
Scheduling Tasks with Nonuniform Deadlines on Two Processors.
Journal of the ACM
, 23
(3)
, 461-467.
https://doi.org/10.1145/321958.321967
Identifiers
- DOI
- 10.1145/321958.321967