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

AbstractWe 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 4m−3+32-competitive. For the second problem Q|rj,online,pmtn|∑wjCj, we show that WSPT-1 algorithm is 2-competitive if si/sm≥∑h=1ish/∑h=1msh 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)