An optimal rounding gives a better approximation for scheduling unrelated machines

An optimal rounding gives a better approximation for scheduling unrelated machines

0.00 Avg rating—0 Votes
Article ID: iaor20052161
Country: Netherlands
Volume: 33
Issue: 2
Start Page Number: 127
End Page Number: 133
Publication Date: Mar 2005
Journal: Operations Research Letters
Authors: ,
Keywords: combinatorial analysis
Abstract:

A polynomial-time algorithm is suggested for non-preemptive scheduling of n-independent jobs on m-unrelated machines to minimize the makespan. The algorithm has a worst-case performance ratio of 2- 1/m. This is better than the earlier known best performance bound 2. Our approach gives the best possible approximation ratio that can be achieved using the rounding approach.

Reviews

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