Online Algorithms for Parallel Job Scheduling and Strip Packing

Johann L. Hurink, J.J. Paulus

Research output: Book/ReportReportProfessional

Abstract

We consider the online scheduling problem of parallel jobs on parallel machines, $P|online{−}list,m_j |C_{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 problem 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 these problems assume bounded job length, the presented algorithm is the first with a constant competitive ratio.
Original languageUndefined
Place of PublicationEindhoven
PublisherBETA Research School for Operations Management and Logistics
Number of pages9
Publication statusPublished - May 2007

Publication series

NameBeta working papers
PublisherBeta Research School for Operations Management and Logistics
No.LNCS4549/WP-215
ISSN (Print)1386-9213

Keywords

  • EWI-10775
  • METIS-241784
  • Online Scheduling
  • Strip Packing
  • Parallel Jobs
  • IR-61849

Cite this