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

12 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 languageUndefined
Title of host publication5th International Workshop on Approximation and Online Algorithms, WAOA 2007
Place of PublicationBerlin
PublisherSpringer
Pages67-74
Number of pages8
ISBN (Print)978-3-540-77917-9
DOIs
Publication statusPublished - Feb 2008
Event5th International Workshop on Approximation and Online Algorithms 2007 - Eilat, Israel
Duration: 11 Oct 200712 Oct 2007

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

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. https://doi.org/10.1007/978-3-540-77918-6_6