|
|||||
|
|
An optimal rounding gives a better approximation for scheduling unrelated machines |
|
| Authors: | Evgeny V. Shchepin Nodari Vakhania |
| Affiliation: | a Steklov Mathematical Institute 117966, Gubkina 8, Moscow, Russia b Science Faculty, State University of Morelos, Av. Universidad 1001, Cuernavaca 62210, Morelos, Mexico c Institute of Computational Mathematics, Akuri 8, Tbilisi 93, GA, USA |
| 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. |
| Keywords: | Scheduling Unrelated machines Approximation algorithm Rounding |
| 本文献已被 ScienceDirect 等数据库收录！ | |