Title :
On the complexity of scheduling problems for parallel/pipelined machines
Author :
Bernstein, David ; Rodeh, Michael ; Gertner, Izidor
Author_Institution :
IBM T.J. Watson Res. Center, Yorktown Heights, NY, USA
fDate :
9/1/1989 12:00:00 AM
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 :
computational complexity; parallel machines; pipeline processing; scheduling; NP-completeness; complexity; dedicated processors; parallel machines; pipelined machines; polynomial-time algorithm; scheduling problems; Algorithm design and analysis; Cities and towns; Computer architecture; Optimal scheduling; Pipeline processing; Polynomials; Processor scheduling; Registers; Scheduling algorithm; System buses;
Journal_Title :
Computers, IEEE Transactions on
