by Hasani, K.; Kravchenko, S.; Werner, F..

**Series:** 2013-13, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

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).

**Keywords:**

Parallel machines, Single server, Approximation algorithm, Worst-case analysis