@book{a2dd5681d2d444b39587920d6ddbd344,
title = "Online scheduling of parallel jobs on two machines is 2-competitive",
abstract = "We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, \$P2|online-list,m\_j|C\_\{max\}\$, we show that 2 is a lower bound on the competitive ratio of any online algorithm. Thereby we not only improve the existing lower bound of \$1+\textbackslash{}sqrt\{2/3\}\$, but also close the gap with the trivial upper bound of 2. For the problem with m machines, \$Pm|online-list,m\_j |C\_\{max\}\$, we derive lower bounds using an ILP formulation. Futhermore, we show that with the presented construction no lower bound greater than 2.5 can be obtained.",
keywords = "IR-67006, METIS-242069, EWI-9514",
author = "Hurink, \{Johann L.\} and J.J. Paulus",
year = "2007",
month = feb,
language = "Undefined",
series = "Beta working papers",
publisher = "BETA Research School for Operations Management and Logistics",
number = "2/WP-200",
}