Ordinal on-line scheduling on parallel machines with machine release times

This paper investigates ordinal on-line scheduling on parallel machines with machine release times. Two objectives, of minimizing the last machine completion time and minimizing the last job completion time are considered. For the first object, we present an algorithm with worst-case ratio of 2m1/m. For the second object, we show that the best possible algorithm has a worst-case ratio of m. We also consider three special cases.