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

What is it about?

This paper considers the single machine scheduling problem of minimizing total weighted job completion time when a set of jobs has to be processed on m identical parallel machines with a single server. An approximation algorithm with a worst case ratio of 3 - 1/m is proposed.

Featured Image

Why is it important?

The result of this paper improves an existing approximation algorithm given by Wang and Cheng in 2001.