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

Share/Save/Bookmark

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

[img]
Preview
PDF
126Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/67006
Publisher URL:http://beta.ieis.tue.nl/node/1220
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 242069