The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders

DOI10.1137/S0895480101394999zbMATH Open1087.90028OpenAlexW2063966770MaRDI QIDQ5317601FDOQ5317601

Authors: Marc Chardon, A. Moukrim 

Publication date: 16 September 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480101394999

Recommendations

• Optimal scheduling for UET/UET-UCT generalized \(n\)-dimensional grid task graphs
• Improved analysis of an algorithm for the coupled task problem with UET jobs
• Approximation algorithms for UET scheduling problems with exact delays
• Scheduling UET-UCT tasks: Branch-and-bound search in the priority space
• Bounds and algorithms for a practical task allocation model (extended abstract)
• A New Insight into the Coffman–Graham Algorithm
• Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
• Minimizing total completion time for UET tasks with release time and outtree precedence constraints
• UET-scheduling with constrained processor allocations

zbMATH Keywords

makespanlist schedulingquasi-interval ordernonpreemptive profile scheduling

Mathematics Subject Classification ID

Partial orders, general (06A06) Deterministic scheduling theory in operations research (90B35)

Cited In (5)

• Non-preemptive profile scheduling and quasi-interval orders
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
• A New Insight into the Coffman–Graham Algorithm
• A polynomial algorithm for recognizing the \(\mathcal A\)-order class

This page was built for publication: The Coffman--Graham Algorithm Optimally Solves UET Task Systems with Overinterval Orders

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