Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428530 | Information Processing Letters | 2014 | 4 Pages |
Abstract
•A parallel machine problem with a single server and minimization of total weighted completion time is considered.•A (3−1m)-approximation algorithm is presented with m being the number of machines.•Our result improves an existing (5−1m)-algorithm by Wang and Cheng.
In this paper, we consider the scheduling problem of minimizing total weighted job completion time when a set of jobs has to be processed on a set of m parallel identical machines with a single server. We propose an approximation algorithm with a worst-case ratio 3−1m. This result improves an existing (5−1m)-approximation algorithm given by Wang and Cheng (2001).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Keramat Hasani, Svetlana A. Kravchenko, Frank Werner,