General parametric scheme for the uniform scheduling problem with two different speeds

Abstract

We consider the Online Uniform Machine Scheduling problem on m machines in the case when speed si = 1 for i = m – k + 1, …, m and si = s, s > 1, for i = 1, 2, …, k. We propose a parametric scheme with worst-case behavior 2,618 when 1 < s ≤ 2 and with asymptotic worst case behavior (1 + s + 5 - 2s - s -s )/2 for all s when ratio m/k tends to infinity. Moreover, some computation approaches are studied.