Approximation schemes for minimizing average weighted completion time with release dates

2003/01/20 by Foto Afrati, Evripidis Bampis, Chandra Chekuri +8 · 1 voice · 3 citations
Computer Science · Engineering · #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms

paper · doi:10.1109/sffcs.1999.814574

openalex publication_date 2003/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We consider the problem of scheduling n jobs with release dates on m machines so as to minimize their average weighted completion time. We present the first known polynomial time approximation schemes for several variants of this problem. Our results include PTASs for the case of identical parallel machines and a constant number of unrelated machines with and without preemption allowed. Our schemes are efficient: for all variants the running time for /spl alpha/(1+/spl epsiv/) approximation is of the form f(1//spl epsiv/, m)poly(n).

Cited by

• Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
• Competitive-Ratio Approximation Schemes for Minimizing the Makespan in\n the Online-List Model
• Scheduling Bidirectional Traffic on a Path

Discussions

• Here is the one from FOCS 1999: doi.org/10.1109/SFFC... [bsky, 1 points, 1 comments]

Related

• Minimum total weighted completion time: Faster approximation schemes
• A (2 + ε)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
• A 2.542-Approximation for Precedence Constrained Single Machine\n Scheduling with Release Dates and Total Weighted Completion Time Objective
• Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
• Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates