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

DOI10.1137/S0895480101394999zbMath1087.90028OpenAlexW2063966770MaRDI QIDQ5317601

Aziz Moukrim, Marc Chardon

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

zbMATH Keywords

list schedulingmakespanquasi-interval ordernonpreemptive profile scheduling

Mathematics Subject Classification ID

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

Related Items (3)

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 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