Randomized on-line scheduling on three processors. (Q1417594): Difference between revisions

The problem of scheduling independent jobs on \(m\) identical parallel machines such that the makespan is minimized is considered. There was a conjecture that the lower bound \[ \sigma_m=1+\frac{1}{(m/(m-1))^m-1} \] on the competitive ration for randomized on-line scheduling algorithms is the optimal competitive ratio for every \(m\geq 2\). This conjecture holds for \(m=2\). An example is presented which shows that this conjecture is wrong for \(m=3\). Similar examples for \(m\geq 4\) are still not known.