Minimizing total weighted completion time approximately for the parallel machine problem with a single server

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