On the approximability of average completion time scheduling under precedence constraints.

DOI10.1016/S0166-218X(02)00427-4zbMath1073.68021MaRDI QIDQ1408829

Gerhard J. Woeginger

Publication date: 25 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

SchedulingApproximation algorithmsPrecedence constraintsInterval orderApproximability thresholdBipartite order

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items

Primal-Dual Algorithms for Precedence Constrained Covering Problems, The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective, Primal-dual algorithms for precedence constrained covering problems, Hardness of flow time minimization in a crossdock with a single door and asymmetric handover relations, LAD models, trees, and an analog of the fundamental theorem of arithmetic, Approximating Weighted Completion Time for Order Scheduling with Setup Times, Preemptive and non-preemptive generalized min sum set cover, Precedence-constrained covering problems with multiplicity constraints, Single machine precedence constrained scheduling is a Vertex cover problem, Integrality Property in Preemptive Parallel Machine Scheduling, Precedence-constrained covering problems with multiplicity constraints, Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems, An exact algorithm for the precedence-constrained single-machine scheduling problem

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