Two Approximate Algorithms For Scheduling Jobs On Parallel Machines With A Single Server

In this paper, we consider the problem of scheduling jobs on parallel machines with a single server. It is a generalization of the classic parallel machines scheduling problem. In this problem, a job must be setup onto a machine by a server before it is processed by the machine. The server can only setup one job at one time. The objective is to minimize the maximal job completion time (makespan). We present an approximate algorithm with the worst case ratio 4/3 for the case of two parallel machines, where all the jobs' setup times are equal. When there are three parallel machines and all the jobs'setup time are equal to one, we also present an approximate algorithm with the worst case ratio 3/2.