Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors

DOI10.1016/j.disopt.2008.09.001zbMath1158.68346OpenAlexW1986491739MaRDI QIDQ1013298

Djamal Rebaine, Wiesław X. Kubiak, Chris N. Potts

Publication date: 17 April 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2008.09.001

zbMATH Keywords

complexitymakespanidentical parallel processorsdivide-and-conquer graphHLF

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Linear time algorithms to solve the linear ordering problem for oriented tree based graphs ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time ⋮ Linear time algorithms on mirror trees

Cites Work

• Optimal scheduling on parallel machines for a new order class
• Optimal scheduling for two-processor systems
• Scheduling precedence graphs of bounded height
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling Flat Graphs
• The Recognition of Series Parallel Digraphs
• Scheduling Opposing Forests
• The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders
• Unnamed Item
• Unnamed Item