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

Johann L. Hurink, J.J. Paulus

Research output: Book/ReportReportProfessional

65 Downloads (Pure)

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 languageUndefined
Place of PublicationEnschede
PublisherBETA Research School for Operations Management and Logistics
Number of pages13
Publication statusPublished - Feb 2007

Publication series

NameBeta working papers
PublisherBeta Research School for Operations Management and Logistics, University of Twente
No.2/WP-200
ISSN (Print)1386-9213

Keywords

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

Online scheduling of parallel jobs on two machines is 2-competitive. / Hurink, Johann L.; Paulus, J.J.

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