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

作者：Hasani Keramat^*; Kravchenko Svetlana A; Werner Frank

来源：Information Processing Letters, 2014, 114(9): 500-503.

DOI：10.1016/j.ipl.2014.04.005

• Parallel machine scheduling
• Single server
• Approximation algorithm
• Worst-case analysis

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 -1/m. This result improves an existing (5 - 1/m)-approximation algorithm given by Wang and Cheng (2001). C) 2014 Elsevier B.V.

• 出版日期2014-9