Optimal on-line algorithms to minimize makespan on two machines with resource augmentation
We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem, preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as functions of the machine speeds.
resource augmentation scheduling online algorithms load balancing