ITLApplied  Computational Mathematics Division
ACMD Seminar Series
Attractive Image NIST

Scheduling Jobs on Grid Processors

Joan Boyar
University of Southern Denmark, Department of Mathematics and Computer Science

Tuesday, January 10, 2006 15:00-16:00,
NIST North (820), Room 145
Tuesday, January 10, 2006 13:00-14:00,
Room 4550

Abstract: 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. We analyze the problem using both the competitive ratio and the relative worst order ratio, observing that the two measures sometimes lead to different conclusions. 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. This is joint work with Lene M. Favrholdt.

Speaker Bio: Joan Boyar has been an Associate Professor at the University of Southern Denmark since 1992. She earned her PhD in Computer Science from the University of California, Berkeley in 1983. Her research is in algorithmics, with a concentration on cryptology earlier and on-line algorithms more recently. She served as a member of the Danish Natural Sciences Research Council from 1997 to 2001.

Presentation Slides: PDF

Contact: P. M. Ketcham

Note: Visitors from outside NIST must contact Robin Bickel; (301) 975-3668; at least 24 hours in advance.

Privacy Policy | Disclaimer | FOIA
NIST is an agency of the U.S. Commerce Department.
Last updated: 2011-01-12.