Profile Scheduling of Opposing Forests and Level Orders

DOI10.1137/0606066MaRDI QIDQ3698629zbMATH OpenOpenAlexFDO

Authors 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

level ordersopposing forestspolynomial algorithmsprecedence graphsprofile scheduling

Mathematics Subject Classification ID

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

Recommendations

• Scheduling Flat Graphs
• Scheduling precedence graphs of bounded height
• scientific article; zbMATH DE number 3900151
• Linear and quadratic algorithms for scheduling chains and opposite chains
• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints

Cites work

• A linear-time recognition algorithm for interval dags
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Complexity of Scheduling under Precedence Constraints
• Erratum “Optimal Sequencing of Two Equivalent Processors”
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3561065 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Interval-Ordered Tasks
• Scheduling Opposing Forests
• Scheduling precedence graphs of bounded height
• The Recognition of Series Parallel Digraphs

Cited in

(26)

• Preemptive scheduling and antichain polyhedra
• Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
• Applications of scheduling theory to formal language theory
• A pumping result for 2-context-free languages
• Optimal scheduling on parallel machines for a new order class
• Nearly on line scheduling of preemptive independent tasks
• Linear and quadratic algorithms for scheduling chains and opposite chains
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Scheduling unit-length jobs with precedence constraints of small height
• Preemptive scheduling with variable profile, precedence constraints and due dates
• Scheduling unitary task systems with zero--one communication delays for quasi-interval orders
• Manipulating derivation forests by scheduling techniques
• Scheduling with limited machine availability
• Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time
• Scheduling lower bounds via AND subset sum
• The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints
• Non-preemptive profile scheduling and quasi-interval orders
• Scheduling precedence graphs of bounded height
• Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
• scientific article; zbMATH DE number 3900151 (Why is no real title available?)
• Scheduling Flat Graphs
• Hierarchy of k-context-free languages part 1
• Hierarchy ofk-context-free languages
• Scheduling jobs in open shops with limited machine availability
• Scheduling lower bounds via and subset sum
• On the complexity of scheduling unit-time jobs with or-precedence constraints

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

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