It's only scheduling and bin packing (but we like it).

György Dósa

University of Pannonia, Veszprém

Abstract

In our talk we first give a very short overview on some popular topics of scheduling and bin packing, about the investigated models, algorithms and worst case analysis.

Then we discuss the following themes: What is the tight additive constant of the well-known FFD algorithm (which turns out to be FFD(I)<=11/9 OPT(I)+6/9)? This is a fairly new result, and getting the tight value of the additive constant needed almost 40 years from the classical PhD work of the "father" of bin packing, David S. Johnson.

In the remaining time we talk about some semi-online scheduling models on two uniformly related machines. This means that the second machine is faster than the first machine, the jobs come according to a list L, which we do not know this list in advance, and we must make our decision regarding the assignment of the actual job without knowing the remaining part of the