Scheduling Opposing Forests

DOI10.1137/0604011MaRDI QIDQ4745255zbMATH OpenOpenAlexFDO

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

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

Cited in

(21)

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

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)