Online scheduling on m uniform machines to minimize total (weighted) completion time

We study two online problems on m uniform machines with speeds s1≤⋯≤sm. The problems are online in the sense that all jobs arrive over time. Each job’s characteristics, such as processing time and weight become known at its arrival time. For the first problem Q|rj,online|∑Cj, we prove that R-LIST algorithm is -competitive. For the second problem Q|rj,online,pmtn|∑wjCj, we show that WSPT-1 algorithm is 2-competitive if for i=1,…,m−1. Then we study a special case where s1=s2=⋯=sm−1≤sm. We obtain that algorithm WSPT-1 is 2-competitive if sm(m−2)≤s1(m−1).