On the complexity of scheduling problems for parallel/pipelined machines

1 January 1989

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. 38 (9) , 1308-1313
https://doi.org/10.1109/12.29469

Abstract

The problem of optimal scheduling of a job system for two dedicated processors is presented. A machine model with two functional units which can be either sequential or pipelined is considered. The complexity of optimal scheduling for a set of expressions on such machines is investigated. Some previous NP-completeness results are reviewed and several new ones are presented. For one restricted case, a polynomial-time algorithm is described and analyzed.

Keywords

This publication has 8 references indexed in Scilit:

Scheduling arithmetic and load operations in parallel with no spilling
Published by Association for Computing Machinery (ACM) ,1987
Postpass Code Optimization of Pipeline Constraints
ACM Transactions on Programming Languages and Systems, 1983
Scheduling subject to resource constraints: classification and complexity
Discrete Applied Mathematics, 1983
Sequencing to Minimize the Maximum Job Cost
Operations Research, 1980
Bounds on the Scheduling of Typed Task Systems
SIAM Journal on Computing, 1980
Deterministic Scheduling with Pipelined Processors
IEEE Transactions on Computers, 1980
The CRAY-1 computer system
Communications of the ACM, 1978
Scheduling Trees in Parallel/Pipelined Processing Environments
IEEE Transactions on Computers, 1977