Utilization of nonclairvoyant online schedules

This paper addresses the analysis of nondelay, nonpreemptive, nonclairvoyant online schedules for independent jobs on m identical machines. In our online model, all jobs are submitted over time. We show that the commonly used makespan criterion is not well suited to describe utilization for this online problem. Therefore, we directly address utilization and determine the maximum deviation from the optimal utilization for the given scheduling problem.