Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142039 | Operations Research Letters | 2016 | 4 Pages |
Abstract
We present a e/(eâ1)-approximation algorithm for the nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on a single machine subject to release dates and precedence constraints. The previously best known approximation algorithm dates back to 1997; its performance guarantee can be made arbitrarily close to the Euler constant e  (Schulz and Skutella, 1997).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Martin Skutella,