A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
From MaRDI portal
Publication:1970412
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
- scientific article; zbMATH DE number 4181112 (Why is no real title available?)
- A new approach to the maximum-flow problem
- An algorithm for the single machine sequencing problem with precedence constraints
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- Matrix multiplication via arithmetic progressions
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- 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
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Cited in
(24)- On Submodular Search and Machine Scheduling
- 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
- 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
- Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
- Classes of linear programs solvable by coordinate-wise minimization
- A state-of-the-art survey on multi-scenario scheduling
- 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
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)
