by Hasani, K.; Kravchenko, S.; Werner, F..
Series: 2013-13, Preprints
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 common server. We propose an approximation algorithm with a worst-case ratio of 3 - 1/m. This result improves an existing
(5 - 1/m) - approximation algorithm given by Wang and Cheng (2001).
Parallel machines, Single server, Approximation algorithm, Worst-case analysis