IMADA - Department of Mathematics and Computer Science |

**Scheduling Jobs on Grid Processors***Joan Boyar and Lene M. Favrholdt*- SWAT 2006: 10th Scandinavian Workshop on Algorithm Theory
We study a new kind of on-line bin packing motivated by a problem arising when scheduling jobs on the Grid. In this bin packing problem, the set of items is given at the beginning, and variable-sized bins arrive one by one. A closely related problem was introduced by Zhang in 1997. Our main result answers a question posed in that paper in the affirmative: we give an algorithm with a competitive ratio strictly better than 2, for our problem as well as Zhang's problem. The publication is available at www.springerlink.com (subscription may be required). |

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