• 10 Citations

Abstract

We consider the online scheduling problem of parallel jobs on parallel machines, $P|\mathrm{online − list},m_j |C_{\mathrm{max}}$. For this problem we present a 6.6623-competitive algorithm. This improves the best known 7- competitive algorithm for this problem. The presented algorithm also applies to the special case where machines are ordered on a line and only adjacent machines can be assigned to a job and, therefore, also to online orthogonal strip packing. Since previous results for online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.
Original languageUndefined
Title of host publication5th International Workshop on Approximation and Online Algorithms, WAOA 2007
Place of PublicationBerlin
PublisherSpringer Verlag
Pages67-74
Number of pages8
ISBN (Print)978-3-540-77917-9
DOIs
StatePublished - Feb 2008
Event5th International Workshop on Approximation and Online Algorithms 2007 - Eilat, Israel

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume4927
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Workshop on Approximation and Online Algorithms 2007
Abbreviated titleWAOA 2007
CountryIsrael
CityEilat
Period11/10/0712/10/07

Fingerprint

Scheduling

Keywords

  • METIS-250883
  • EWI-12000
  • IR-62190

Cite this

Hurink, J. L., & Paulus, J. J. (2008). Online algorithm for parallel job scheduling and strip packing. In 5th International Workshop on Approximation and Online Algorithms, WAOA 2007 (pp. 67-74). [10.1007/978-3-540-77918-6_6] (Lecture Notes in Computer Science; Vol. 4927). Berlin: Springer Verlag. DOI: 10.1007/978-3-540-77918-6_6

Hurink, Johann L.; Paulus, J.J. / Online algorithm for parallel job scheduling and strip packing.

5th International Workshop on Approximation and Online Algorithms, WAOA 2007. Berlin : Springer Verlag, 2008. p. 67-74 10.1007/978-3-540-77918-6_6 (Lecture Notes in Computer Science; Vol. 4927).

Research output: Scientific - peer-reviewConference contribution

@inbook{42df28972dca4dafad010c88e798883f,
title = "Online algorithm for parallel job scheduling and strip packing",
abstract = "We consider the online scheduling problem of parallel jobs on parallel machines, $P|\mathrm{online − list},m_j |C_{\mathrm{max}}$. For this problem we present a 6.6623-competitive algorithm. This improves the best known 7- competitive algorithm for this problem. The presented algorithm also applies to the special case where machines are ordered on a line and only adjacent machines can be assigned to a job and, therefore, also to online orthogonal strip packing. Since previous results for online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.",
keywords = "METIS-250883, EWI-12000, IR-62190",
author = "Hurink, {Johann L.} and J.J. Paulus",
note = "10.1007/978-3-540-77918-6_6",
year = "2008",
month = "2",
doi = "10.1007/978-3-540-77918-6_6",
isbn = "978-3-540-77917-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "67--74",
booktitle = "5th International Workshop on Approximation and Online Algorithms, WAOA 2007",

}

Hurink, JL & Paulus, JJ 2008, Online algorithm for parallel job scheduling and strip packing. in 5th International Workshop on Approximation and Online Algorithms, WAOA 2007., 10.1007/978-3-540-77918-6_6, Lecture Notes in Computer Science, vol. 4927, Springer Verlag, Berlin, pp. 67-74, 5th International Workshop on Approximation and Online Algorithms 2007, Eilat, Israel, 11-12 October. DOI: 10.1007/978-3-540-77918-6_6

Online algorithm for parallel job scheduling and strip packing. / Hurink, Johann L.; Paulus, J.J.

5th International Workshop on Approximation and Online Algorithms, WAOA 2007. Berlin : Springer Verlag, 2008. p. 67-74 10.1007/978-3-540-77918-6_6 (Lecture Notes in Computer Science; Vol. 4927).

Research output: Scientific - peer-reviewConference contribution

TY - CHAP

T1 - Online algorithm for parallel job scheduling and strip packing

AU - Hurink,Johann L.

AU - Paulus,J.J.

N1 - 10.1007/978-3-540-77918-6_6

PY - 2008/2

Y1 - 2008/2

N2 - We consider the online scheduling problem of parallel jobs on parallel machines, $P|\mathrm{online − list},m_j |C_{\mathrm{max}}$. For this problem we present a 6.6623-competitive algorithm. This improves the best known 7- competitive algorithm for this problem. The presented algorithm also applies to the special case where machines are ordered on a line and only adjacent machines can be assigned to a job and, therefore, also to online orthogonal strip packing. Since previous results for online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.

AB - We consider the online scheduling problem of parallel jobs on parallel machines, $P|\mathrm{online − list},m_j |C_{\mathrm{max}}$. For this problem we present a 6.6623-competitive algorithm. This improves the best known 7- competitive algorithm for this problem. The presented algorithm also applies to the special case where machines are ordered on a line and only adjacent machines can be assigned to a job and, therefore, also to online orthogonal strip packing. Since previous results for online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.

KW - METIS-250883

KW - EWI-12000

KW - IR-62190

U2 - 10.1007/978-3-540-77918-6_6

DO - 10.1007/978-3-540-77918-6_6

M3 - Conference contribution

SN - 978-3-540-77917-9

T3 - Lecture Notes in Computer Science

SP - 67

EP - 74

BT - 5th International Workshop on Approximation and Online Algorithms, WAOA 2007

PB - Springer Verlag

ER -

Hurink JL, Paulus JJ. Online algorithm for parallel job scheduling and strip packing. In 5th International Workshop on Approximation and Online Algorithms, WAOA 2007. Berlin: Springer Verlag. 2008. p. 67-74. 10.1007/978-3-540-77918-6_6. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-540-77918-6_6