کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
473939 | 698825 | 2009 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Preemptive scheduling on uniform machines to minimize mean flow time Preemptive scheduling on uniform machines to minimize mean flow time](/preview/png/473939.png)
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.
Journal: Computers & Operations Research - Volume 36, Issue 10, October 2009, Pages 2816–2821