Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
473939 | Computers & Operations Research | 2009 | 6 Pages |
A set of jobs has to be scheduled on parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement, and each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. We want to find a schedule that minimizes the sum of completion times, i.e., we consider problem Q|rj,pj=p,pmtn|∑CjQ|rj,pj=p,pmtn|∑Cj whose complexity status was open. In this paper, we give a polynomial algorithm for the above problem. The algorithm is based on a reduction of the scheduling problem to a linear program. The crucial condition for implementing the proposed reduction is the known order of job completion times.