On several scheduling problems
In this talk I present some recent results in the areas of scheduling and bin packing, both offline and online. I first discuss preemptive scheduling on uniformly related machines to minimize a given goal function. For goal functions which are symmetric, monotone, and convex, it is possible to show that there exist optimal solutions with no idle time. Next I survey results on several versions of multidimensional bin packing, and discuss the unique properties of each model. Finally I concentrate on the multidimensional, bounded space, online model and describe the results in more detail. For this model I present an algorithm of tight asymptotic performance ratio both for the general case of hyperbox packing, and the more special case of hypercube packing. This ratio is exponential in the dimension for hyperboxes, but sub-linear for hypercubes. Parts of the talk are based on a joint work with Tamir Tassa and on a joint work with Rob van Stee.