Scheduling Opposing Forests

DOI10.1137/0604011zbMATH Open0507.68021OpenAlexW2018342998MaRDI QIDQ4745255FDOQ4745255

Authors: M. R. Garey, Mihalis Yannakakis, D. S. Johnson, Robert E. 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)

Cites Work

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

Cited In (21)

• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
• A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
• On-line scheduling of parallel jobs with runtime restrictions
• An EPTAS for scheduling fork-join graphs with communication delay
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• A state-of-the-art review of parallel-machine scheduling research
• The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints
• A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations
• `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders
• Scheduling jobs in open shops with limited machine availability
• Applications of scheduling theory to formal language theory
• Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling unit-length jobs with precedence constraints of small height
• Dynamic scheduling of parallel computations
• 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
• A backward approach in list scheduling algorithms for multi-machine tardiness problems
• Optimal parallel processing of random task graphs
• Minimizing the number of machines for minimum length schedules
• On the complexity of scheduling unit-time jobs with or-precedence constraints

This page was built for publication: Scheduling Opposing Forests

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