An approximation algorithm for parallel machine scheduling with a common server

In this paper we study the scheduling of a given set of jobs on several ide ntical parallel machines tended by a common server. Each job must be proces sed on one of the machines. Prior to processing, the server has to set up t he relevant machine. The objective is to schedule the jobs so as to minimiz e the total weighted job completion times. We provide an approximation algo rithm to tackle this intractable problem and analyze the worst-case perform ance of the algorithm for the general, as well as a special, case of the pr oblem.