IMADA - Department of Mathematics and Computer Science |

**Optimal Non-Preemptive Semi-Online Scheduling to Minimize Makespan on Two Related Machines***Lene M. Favrholdt, Leah Epstein*- Journal of Algorithms 57(1): 49-73, 2005
We consider the following non-preemptive semi-online scheduling problem.
Jobs with non-increasing sizes arrive one by one to be scheduled on two
uniformly related machines, with the goal of minimizing the makespan. We
analyze both the optimal overall competitive ratio, and the optimal competitive ratio as a
function of the speed ratio ( The publication is available from ScienceDirect (subscription may be required). |

IMADA HOME | SDU HOME | Previous page Last modified: 2017-06-10 by Lene Monrad Favrholdt <lenem@imada.sdu.dk> |