Improved online algorithms for parallel job scheduling and strip packing

Johann L. Hurink, J.J. Paulus

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

In this paper we consider the online scheduling of jobs which require processing on a number of machines simultaneously. These jobs are presented to a decision maker one by one, where the next job becomes known as soon as the current job is scheduled. The objective is to minimize the makespan (P|online - list,m_j|C_max). We present a 6.6623-competitive algorithm for this online problem, improving the best known algorithm, which is 7-competitive. The presented algorithm also applies to the online orthogonal strip packing problem. Since the previous results for this problem assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio for the general online orthogonal strip packing problem. Furthermore, for the special case with 3 machines we give a 2.8-competitive algorithm, improving upon the 3-competitive greedy algorithm.
Original languageUndefined
Pages (from-to)583-593
Number of pages11
JournalTheoretical computer science
Volume412
Issue number7
DOIs
Publication statusPublished - 25 Feb 2011

Keywords

  • Parallel Jobs
  • Strip Packing
  • Online Scheduling
  • EWI-19622
  • METIS-277548
  • IR-76016
  • Competitive Analysis

Cite this