Online scheduling of parallel jobs on two machines is 2-competitive


Hurink, J.L. and Paulus, J.J. (2007) Online scheduling of parallel jobs on two machines is 2-competitive. [Report]

open access
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+\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.
Item Type:Report
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Publisher URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 242069