Scheduling Opposing Forests

DOI10.1137/0604011zbMath0507.68021OpenAlexW2018342998MaRDI QIDQ4745255

Mihalis Yannakakis, Michael R. Garey, David S. Johnson, Robert Endre Tarjan

Publication date: 1983

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

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

zbMATH Keywords

NP-completeprecedence constraintscommon deadlineunit-time tasks

Mathematics Subject Classification ID

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

Related Items (21)

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 ⋮ A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations ⋮ A backward approach in list scheduling algorithms for multi-machine tardiness problems ⋮ Scheduling jobs in open shops with limited machine availability ⋮ Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints ⋮ Scheduling unit-length jobs with precedence constraints of small height ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ An EPTAS for scheduling fork-join graphs with communication delay ⋮ Optimal parallel processing of random task graphs ⋮ On-line scheduling of parallel jobs with runtime restrictions ⋮ The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints ⋮ A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time ⋮ 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 ⋮ Minimizing the number of machines for minimum length schedules ⋮ Dynamic scheduling of parallel computations ⋮ On the complexity of scheduling unit-time jobs with or-precedence constraints

Cites Work

• Unnamed Item
• Unnamed Item
• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Scheduling Interval-Ordered Tasks
• The Two-Machine Maximum Flow Time Problem with Series Parallel Precedence Relations
• Sequencing with Series-Parallel Precedence Constraints
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Scheduling Graphs on Two Processors
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Two-Processor Scheduling with Start-Times and Deadlines
• `` Strong NP-Completeness Results
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• Optimal Sequencing of Two Equivalent Processors

This page was built for publication: Scheduling Opposing Forests