A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine

DOI10.1016/S0167-6377(99)00056-5zbMath0958.90042OpenAlexW1992370758WikidataQ127125105 ScholiaQ127125105MaRDI QIDQ1970412

Dorit S. Hochbaum, Fabián A. Chudak

Publication date: 19 April 2001

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(99)00056-5

zbMATH Keywords

precedence constraintslinear programming relaxationnonpreemptive scheduling problem

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35)

Related Items (22)

Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times ⋮ Order acceptance and scheduling problems in two-machine flow shops: new mixed integer programming formulations ⋮ Classes of linear programs solvable by coordinate-wise minimization ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Partially ordered knapsack and applications to scheduling ⋮ Scheduling and fixed-parameter tractability ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ On Submodular Search and Machine Scheduling ⋮ Parameterized multi-scenario single-machine scheduling problems ⋮ On the approximability of average completion time scheduling under precedence constraints. ⋮ A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ Vertex Cover in Graphs with Locally Few Colors ⋮ An integer programming approach to optimal basic block instruction scheduling for single-issue processors ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ 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 ⋮ A 2-approximation algorithm for the network substitution problem ⋮ Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations ⋮ Decision diagrams for solving a job scheduling problem under precedence constraints

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Structure of a simple scheduling polyhedron
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
• Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
• A new approach to the maximum-flow problem
• An algorithm for the single machine sequencing problem with precedence constraints
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• The permutahedron of series-parallel posets

This page was built for publication: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine