Single-Machine Scheduling with Precedence Constraints
From MaRDI portal
Publication:5387960
DOI10.1287/moor.1050.0158zbMath1278.90148OpenAlexW2145075017WikidataQ65553925 ScholiaQ65553925MaRDI QIDQ5387960
Andreas S. Schulz, José R. Correa
Publication date: 27 May 2008
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/628cac0166232e2098640c0f033c371ffb06f611
schedulingapproximation algorithmpartial orderlinear programming relaxationvertex coverlinear orderinginteger programming formulation
Integer programming (90C10) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35)
Related Items (24)
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ Approximate Deadline-Scheduling with Precedence Constraints ⋮ Exact and Approximation Algorithms for the Expanding Search Problem ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Partially ordered knapsack and applications to scheduling ⋮ Equitable scheduling on a single machine ⋮ On Submodular Search and Machine Scheduling ⋮ Minimizing I/Os in Out-of-Core Task Tree Scheduling ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ The precedence constrained knapsack problem: separating maximally violated inequalities ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ An integer programming approach to optimal basic block instruction scheduling for single-issue processors ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem ⋮ Scheduling of tasks with effectiveness precedence constraints ⋮ A new heuristic and an exact approach for a production planning problem ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ Decision diagrams for solving a job scheduling problem under precedence constraints ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem
This page was built for publication: Single-Machine Scheduling with Precedence Constraints
