A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
From MaRDI portal
Publication:1970412
DOI10.1016/S0167-6377(99)00056-5zbMATH Open0958.90042OpenAlexW1992370758WikidataQ127125105 ScholiaQ127125105MaRDI QIDQ1970412FDOQ1970412
Authors: F. Chudak, Dorit S. Hochbaum 
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
Recommendations
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- scientific article; zbMATH DE number 871909
- Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
Cites Work
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Matrix multiplication via arithmetic progressions
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- A new approach to the maximum-flow problem
- An algorithm for the single machine sequencing problem with precedence constraints
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- Structure of a simple scheduling polyhedron
- The permutahedron of series-parallel posets
- 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
- Title not available (Why is that?)
Cited In (24)
- Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
- Approximating Single Machine Scheduling with Scenarios
- A 2-approximation algorithm for the network substitution problem
- Decision diagrams for solving a job scheduling problem under precedence constraints
- Order acceptance and scheduling problems in two-machine flow shops: new mixed integer programming formulations
- 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
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
- A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
- Exact and heuristic algorithms for the parallel machine total completion time scheduling problem with dual resources, ready times, and sequence-dependent setup times
- A state-of-the-art survey on multi-scenario scheduling
- Classes of linear programs solvable by coordinate-wise minimization
- On the approximability of average completion time scheduling under precedence constraints.
- Scheduling and fixed-parameter tractability
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Online Linear Optimization for Job Scheduling Under Precedence Constraints
- Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints
- Single machine precedence constrained scheduling is a Vertex cover problem
- Partially ordered knapsack and applications to scheduling
- Vertex cover in graphs with locally few colors
- Parameterized multi-scenario single-machine scheduling problems
- On Submodular Search and Machine Scheduling
This page was built for publication: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1970412)
