# Online algorithm for parallel job scheduling and strip packing

Johann L. Hurink, J.J. Paulus

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

15 Citations (Scopus)

## 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 67-74 8 978-3-540-77917-9 https://doi.org/10.1007/978-3-540-77918-6_6 Published - Feb 2008 5th International Workshop on Approximation and Online Algorithms 2007 - Eilat, IsraelDuration: 11 Oct 2007 → 12 Oct 2007

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

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