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 m processors when speed si=1 for i=k+1,…,m and 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 [Formula presented](1+s+5−2s+s2) for all s>1 when the ratio m/k tends to infinity.