Lower bounds for online makespan minimization on a small number of related machines

Łukasz Jeż, Jarett Schwartz, József Békési

Journal of Scheduling · 2012 · 11 citations · 16 references

DOIFull text

Open access

Concepts

Abstract

In online makespan minimization, the jobs characterized by their processing time arrive one-by-one and each has to be assigned to one of the m uniformly related machines. The goal is to minimize the length of the schedule. We prove new combinatorial lower bounds for m=4 and m=5, and computer-assisted lower bounds for m≤11.

References

16