On-line restricted assignment of temporary tasks with unknown durations. (Q1853182)

We consider load balancing of temporary tasks on \(m\) machines in the restricted assignment model. It is known that the best competitive ratio for this problem is \(\Theta(m)\). This bound is not achieved by the greedy algorithm whose competitive ratio is known to be \(\Omega(m^{2/3})\). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of \(m.\) We also show that for a small number of machines, namely \(m<5,\) the greedy algorithm is optimal.