Scheduling precedence graphs of bounded height

DOI10.1016/0196-6774(84)90039-7zbMath0547.68037OpenAlexW2005751233MaRDI QIDQ3339283

Danny Dolev, Manfred K. Warmuth

Publication date: 1984

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(84)90039-7

zbMATH Keywords

schedulingNP-completenesspolynomial algorithmprecedence graphidentical processorspartially ordered set of unit length tasks

Mathematics Subject Classification ID

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

Related Items

Profile Scheduling of Opposing Forests and Level Orders ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Applications of scheduling theory to formal language theory ⋮ A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows ⋮ Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints ⋮ Unnamed Item ⋮ Scheduling unit-length jobs with precedence constraints of small height ⋮ A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile ⋮ Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search ⋮ Polyhedral Reformulation of a Scheduling Problem And Related Theoretical Results ⋮ Preemptive scheduling and antichain polyhedra ⋮ Preemptive scheduling with variable profile, precedence constraints and due dates ⋮ Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors ⋮ Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time ⋮ Optimal scheduling on parallel machines for a new order class