Profile Scheduling of Opposing Forests and Level Orders

DOI10.1137/0606066zbMath0577.90038OpenAlexW2065698702MaRDI QIDQ3698629

Danny Dolev, Manfred K. Warmuth

Publication date: 1985

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

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

zbMATH Keywords

polynomial algorithmsprecedence graphslevel ordersopposing forestsprofile scheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (21)

Scheduling lower bounds via AND subset sum ⋮ 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 ⋮ Nearly on line scheduling of preemptive independent tasks ⋮ Scheduling jobs in open shops with limited machine availability ⋮ Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints ⋮ A pumping result for 2-context-free languages ⋮ Unnamed Item ⋮ Scheduling unit-length jobs with precedence constraints of small height ⋮ Scheduling with limited machine availability ⋮ Hierarchy of k-context-free languages part 1 ⋮ Hierarchy ofk-context-free languages ⋮ The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints ⋮ 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 ⋮ Scheduling unitary task systems with zero--one communication delays for quasi-interval orders ⋮ Manipulating derivation forests by scheduling techniques ⋮ 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 ⋮ On the complexity of scheduling unit-time jobs with or-precedence constraints

Cites Work

• A linear-time recognition algorithm for interval dags
• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Scheduling precedence graphs of bounded height
• Scheduling Interval-Ordered Tasks
• The Recognition of Series Parallel Digraphs
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Complexity of Scheduling under Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Opposing Forests
• Erratum “Optimal Sequencing of Two Equivalent Processors”
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Profile Scheduling of Opposing Forests and Level Orders