On the approximability of average completion time scheduling under precedence constraints

DOI10.1007/3-540-48224-5_72MaRDI QIDQ4535070zbMATH OpenFDO

Authors Gerhard J. Woeginger

Publication date 12 June 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2076/20760887

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• On the approximability of average completion time scheduling under precedence constraints.
• Scheduling with Precedence Constraints of Low Fractional Dimension
• A fully combinatorial 2-approximation algorithm for precedence-constrained scheduling a single machine to minimize average weighted completion time
• On the approximability of single-machine scheduling with precedence constraints
• Precedence constrained scheduling to minimize sum of weighted completion times on a single machine

Cited in

(17)

• Approximation results for a bicriteria job scheduling problem on a single machine without preemption
• 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
• A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• Preemptive scheduling with availability constraints to minimize total weighted completion times
• A strengthened formulation and cutting planes for the open pit mine production scheduling problem
• Designing PTASs for MIN-SUM scheduling problems
• Online Linear Optimization for Job Scheduling Under Precedence Constraints
• Near-optimal solutions and large integrality gaps for almost all instances of single-machine precedence-constrained scheduling
• Approximate Deadline-Scheduling with Precedence Constraints
• Ordering problems approximated: Single-processor scheduling and interval graph completion
• Min-sum scheduling under precedence constraints
• Approximability of average completion time scheduling on unrelated machines
• scientific article; zbMATH DE number 3894817 (Why is no real title available?)
• Lift and project algorithms for precedence constrained scheduling to minimize completion time
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Partially ordered knapsack and applications to scheduling

This page was built for publication: On the approximability of average completion time scheduling under precedence constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4535070)