Scheduling unit-length jobs with precedence constraints of small height

DOI10.1016/j.orl.2014.01.008zbMath1408.90120OpenAlexW2151854691WikidataQ57338947 ScholiaQ57338947MaRDI QIDQ1667212

Pinar Heggernes, Ruben van der Zwaan, Alexander Grigoriev, André Berger

Publication date: 27 August 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2014.01.008

zbMATH Keywords

computational complexityschedulingprecedence constraintspolynomial-time algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Cites Work

• On a parallel machine scheduling problem with precedence constraints
• A linear-time recognition algorithm for interval dags
• NP-complete scheduling problems
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• Scheduling precedence graphs of bounded height
• Profile Scheduling of Opposing Forests and Level Orders
• Scheduling Flat Graphs
• Scheduling Interval-Ordered Tasks
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Scheduling Opposing Forests
• Optimal Sequencing of Two Equivalent Processors
• Unnamed Item

This page was built for publication: Scheduling unit-length jobs with precedence constraints of small height