On the approximability of average completion time scheduling under precedence constraints.
From MaRDI portal
Publication:1408829
DOI10.1016/S0166-218X(02)00427-4zbMath1073.68021MaRDI QIDQ1408829
Publication date: 25 September 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Scheduling; Approximation algorithms; Precedence constraints; Interval order; Approximability threshold; Bipartite order
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
68W25: Approximation algorithms
Related Items
Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems, Precedence-constrained covering problems with multiplicity constraints, Hardness of flow time minimization in a crossdock with a single door and asymmetric handover relations, Single machine precedence constrained scheduling is a Vertex cover problem, LAD models, trees, and an analog of the fundamental theorem of arithmetic, Precedence-constrained covering problems with multiplicity constraints, The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective, Preemptive and non-preemptive generalized min sum set cover, An exact algorithm for the precedence-constrained single-machine scheduling problem, Primal-dual algorithms for precedence constrained covering problems, Approximating Weighted Completion Time for Order Scheduling with Setup Times, Integrality Property in Preemptive Parallel Machine Scheduling, Primal-Dual Algorithms for Precedence Constrained Covering Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- Bipartite permutation graphs
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Precedence constrained scheduling to minimize sum of weighted completion times on a single machine
- A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine
- Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem
- An algorithm for the single machine sequencing problem with precedence constraints
- Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
- Complexity of Scheduling under 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
- Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler