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

DOI10.1287/OPRE.51.6.981.24912MaRDI QIDQ3637403zbMATH OpenOpenAlexFDO

Authors François Margot, Maurice Queyranne, Yaoguang Wang

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 network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Integer Programming and Combinatorial Optimization
• Single-Machine Scheduling with Precedence Constraints
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• scientific article; zbMATH DE number 871909

Cited in

(25)

• Single machine precedence constrained scheduling is a Vertex cover problem
• Approximation results for a bicriteria job scheduling problem on a single machine without preemption
• On the approximability of average completion time scheduling under precedence constraints.
• An integer programming approach to optimal basic block instruction scheduling for single-issue processors
• Dual decomposition of a single-machine scheduling problem
• A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
• Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
• Preemptive and non-preemptive generalized min sum set cover
• An exact algorithm for the precedence-constrained single-machine scheduling problem
• Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
• Asymptotically optimal schedules for single-server flow shop problems with setup costs and times
• Designing PTASs for MIN-SUM scheduling problems
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
• Online Linear Optimization for Job Scheduling Under Precedence Constraints
• Vertex cover in graphs with locally few colors
• Decomposition algorithm for the single machine scheduling polytope
• Approximating Single Machine Scheduling with Scenarios
• A General Framework for Approximating Min Sum Ordering Problems
• On Submodular Search and Machine Scheduling
• Decision diagrams for solving a job scheduling problem under precedence constraints
• Scheduling partially ordered jobs faster than \(2^n\)
• Hardness and approximation of submodular minimum linear ordering problems
• On min sum vertex cover and generalized min sum set cover
• Partially ordered knapsack and applications to scheduling
• A decomposition scheme for single stage scheduling problems

This page was built for publication: Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem

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