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 list. We minimize the makespan (the time when the last finished job is completed). But, as the problems are semi-online, we have a partial knowledge of the sequence, or we are allowed to change the schedule of the already assigned jobs a little bit. In the first model we know the sum of the sizes of the jobs in advance. In the second type of the models some reassignment is possible, that is, some already assigned jobs can be reassigned in some bounded way, or a (reordering) buffer of bounded size is available to temporarily store at most K jobs to improve the quality of the schedule.