An optimal algorithm for preemptive on-line scheduling

An optimal algorithm for preemptive on-line scheduling

0.00 Avg rating0 Votes
Article ID: iaor1997670
Country: Netherlands
Volume: 18
Issue: 3
Start Page Number: 127
End Page Number: 131
Publication Date: Oct 1995
Journal: Operations Research Letters
Authors: , ,
Keywords: scheduling
Abstract:

The authors investigate the problem of on-line scheduling jobs on m identical parallel machines where preemption is allowed. The goal is to minimize the makespan. They derive an approximation algorithm with worst-case guarantee mm/(mm-(m-1)m) for every m≥2, which increasingly tends to e/(e-1)≅1.58 as m⇒•. Moreover, the authors prove that for no m≥2 there does exist any approximation algorithm with a better worst-case guarantee.

Reviews

Required fields are marked *. Your email address will not be published.