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

DOI10.1287/OPRE.51.6.981.24912zbMATH Open1165.90454OpenAlexW2127277545MaRDI QIDQ3637403FDOQ3637403

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

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

Mathematics Subject Classification ID

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

Cited In (25)

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

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)