Lower bounds on precedence-constrained scheduling for parallel processors.

DOI10.1016/S0020-0190(01)00303-9MaRDI QIDQ1853033zbMATH OpenOpenAlexFDO

Authors Ivan D. Baev, Waleed M. Meleis, Alexandre Eichenberger

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(01)00303-9

zbMATH Keywords

Parallel processingSchedulingLower bounds

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• scientific article; zbMATH DE number 1187165
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
• An experimental study of algorithms for weighted completion time scheduling
• Improved lower bounds on time and processors for scheduling precedence graphs on multicomputer systems
• Lower bounds for parallel machine scheduling problems

Cites work

• scientific article; zbMATH DE number 1305485 (Why is no real title available?)
• Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Scheduling independent tasks to reduce mean finishing time
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms

Cited in

(4)

• The feasibility of general task systems with precedence constraints on multiprocessor platforms
• On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems
• scientific article; zbMATH DE number 2080870 (Why is no real title available?)
• Towards tight lower bounds for scheduling problems

This page was built for publication: Lower bounds on precedence-constrained scheduling for parallel processors.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853033)