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

Abstract

In this paper, we consider the online uniform machine scheduling problem on mprocessors when speed si=1 for i =k +1, ..., mand si=s, s >1, for i =1, ..., k. The objective is to minimize makespan. We propose a parametric scheme with the worst-case performance 2.618 when 1 <s ≤2, and with the asymptotic worst-case performance 1/2(1 +s +√5−2s+s2) for all s >1 when the ratio m/k tends to infinity.