Deterministic Scheduling with Pipelined Processors
- 1 April 1980
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-29 (4) , 308-316
- https://doi.org/10.1109/tc.1980.1675569
Abstract
In this paper several results are proven showing a correspondence between problems involving task systems with single-stage processors and similar ones using pipelined processors. For example, an optimal schedule for a task system with arbitrary precedence constraints using a single pipelined processor with two stages is found by the familiar Coffman–Graham algorithm for a system with two single-stage processors. Precedence constraints in the form of inforests, out-forests, and directed acyclic graphs are examined. Task systems with release times and deadlines for each task are also considered.Keywords
This publication has 5 references indexed in Scilit:
- Two-Processor Scheduling with Start-Times and DeadlinesSIAM Journal on Computing, 1977
- Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum LatenessMathematics of Operations Research, 1977
- Scheduling Tasks with Nonuniform Deadlines on Two ProcessorsJournal of the ACM, 1976
- Optimal scheduling for two-processor systemsActa Informatica, 1972
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961