Zurück zu den Preprints des Jahres 2013


Minimizing Total Weighted Completion Time Approximately for the Parallel Machine Problem with a Single Server

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

Series: 2013-13, Preprints

90B35 Scheduling theory, deterministic

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