Zurück zu den Preprints des Jahres 2013


2013-13

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

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