# Online algorithm for parallel job scheduling and strip packing

Johann L. Hurink, J.J. Paulus

• 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 language Undefined 5th International Workshop on Approximation and Online Algorithms, WAOA 2007 Berlin Springer Verlag 67-74 8 978-3-540-77917-9 http://dx.doi.org/10.1007/978-3-540-77918-6_6 Published - Feb 2008 5th International Workshop on Approximation and Online Algorithms 2007 - Eilat, Israel

### Publication series

Name Lecture Notes in Computer Science Springer Verlag 4927 0302-9743 1611-3349

### Conference

Conference 5th International Workshop on Approximation and Online Algorithms 2007 WAOA 2007 Israel Eilat 11/10/07 → 12/10/07

Scheduling

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

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