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

Johann L. Hurink, J.J. Paulus

Research output: Book/ReportReportProfessional

### 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.
Original language Undefined Enschede BETA Research School for Operations Management and Logistics 13 Published - Feb 2007

### Publication series

Name Beta working papers Beta Research School for Operations Management and Logistics, University of Twente 2/WP-200 1386-9213

• IR-67006
• METIS-242069
• EWI-9514

## Cite this

Hurink, J. L., & Paulus, J. J. (2007). Online scheduling of parallel jobs on two machines is 2-competitive. (Beta working papers; No. 2/WP-200). Enschede: BETA Research School for Operations Management and Logistics.