Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem

DOI10.1287/opre.51.6.981.24912zbMath1165.90454OpenAlexW2127277545MaRDI QIDQ3637403

Margot, François, Yaoguang Wang, Maurice Queyranne

Publication date: 9 July 2009

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

Full work available at URL: https://doi.org/10.1287/opre.51.6.981.24912

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items

A General Framework for Approximating Min Sum Ordering Problems, An exact dynamic programming algorithm for the precedence-constrained class sequencing problem, Partially ordered knapsack and applications to scheduling, On Submodular Search and Machine Scheduling, On the approximability of average completion time scheduling under precedence constraints., Approximating Single Machine Scheduling with Scenarios, A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Approximation algorithms for scheduling problems with a modified total weighted tardiness objective, 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, Preemptive and non-preemptive generalized min sum set cover, Scheduling partially ordered jobs faster than \(2^n\), Asymptotically optimal schedules for single-server flow shop problems with setup costs and times, Designing PTASs for MIN-SUM scheduling problems, Single machine precedence constrained scheduling is a Vertex cover problem, Online Linear Optimization for Job Scheduling Under Precedence Constraints, Approximation results for a bicriteria job scheduling problem on a single machine without preemption, Decision diagrams for solving a job scheduling problem under precedence constraints, An exact algorithm for the precedence-constrained single-machine scheduling problem