Online scheduling of multiprocessor jobs with preemption

Abstract. The thesis is devoted to the problem of online preemptive scheduling of mul- tiprocessor jobs. It gives a summary of previous work on this problem. For some special variants of the problem, especially if we restrict the sizes of jobs to one and two, new results are given, both in the terms of lower bounds and in the terms of competitive al- gorithms. A previously published lower bound is showed to be computed incorrectly and it is replaced by a correct lower bound in this thesis. An algorithm is presented for the special case of four processors and sizes of jobs one and two that is conjectured to achieve the best possible competitive ratio