# 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.
Hurink, Johann L. ; Paulus, J.J. / Online scheduling of parallel jobs on two machines is 2-competitive. Enschede : BETA Research School for Operations Management and Logistics, 2007. 13 p. (Beta working papers; 2/WP-200).
@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+\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 = "2",
language = "Undefined",
series = "Beta working papers",
publisher = "BETA Research School for Operations Management and Logistics",
number = "2/WP-200",

}

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

Research output: Book/ReportReportProfessional

TY - BOOK

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

AU - Hurink, Johann L.

AU - Paulus, J.J.

PY - 2007/2

Y1 - 2007/2

N2 - 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.

AB - 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.

KW - IR-67006

KW - METIS-242069

KW - EWI-9514

M3 - Report

T3 - Beta working papers

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

PB - BETA Research School for Operations Management and Logistics

CY - Enschede

ER -

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