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

Johann L. Hurink; J.J. Paulus

doi:10.1016/j.orl.2007.06.001

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

Johann L. Hurink
, J.J. Paulus

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

24 Citations (Scopus)

14 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, we show that 2 is a tight lower bound on the competitive ratio. For the problem with $m$ machines, we derive lower bounds using an ILP formulation.

Original language	Undefined
Article number	10.1016/j.orl.2007.06.001
Pages (from-to)	51-56
Number of pages	6
Journal	Operations research letters
Volume	36
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2007.06.001
Publication status	Published - Jan 2008

Keywords

EWI-11663
IR-62089
METIS-250858

Access to Document

10.1016/j.orl.2007.06.001

http://eprints.eemcs.utwente.nl/secure2/11663/01/Online_scheduling_of_parallel_jobs_on_two_machines_is_2_competitive.pdf

Cite this

@article{696afb26318f408d89696fce4f3200f6,

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, we show that 2 is a tight lower bound on the competitive ratio. For the problem with \$m\$ machines, we derive lower bounds using an ILP formulation.",

keywords = "EWI-11663, IR-62089, METIS-250858",

author = "Hurink, \{Johann L.\} and J.J. Paulus",

note = "10.1016/j.orl.2007.06.001 ",

year = "2008",

month = jan,

doi = "10.1016/j.orl.2007.06.001",

language = "Undefined",

volume = "36",

pages = "51--56",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

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

AU - Hurink, Johann L.

AU - Paulus, J.J.

N1 - 10.1016/j.orl.2007.06.001

PY - 2008/1

Y1 - 2008/1

N2 - We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with $m$ machines, we derive lower bounds using an ILP formulation.

AB - We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with $m$ machines, we derive lower bounds using an ILP formulation.

KW - EWI-11663

KW - IR-62089

KW - METIS-250858

U2 - 10.1016/j.orl.2007.06.001

DO - 10.1016/j.orl.2007.06.001

M3 - Article

SN - 0167-6377

VL - 36

SP - 51

EP - 56

JO - Operations research letters

JF - Operations research letters

IS - 1

M1 - 10.1016/j.orl.2007.06.001

ER -