Online scheduling on unbounded parallel-batch machines to minimize the makespan

Ji Tian, Edwin Tai Chiu Cheng, Chi To Ng, Jinjiang Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

32 Citations (Scopus)

Abstract

We consider online scheduling on m parallel-batch machines to minimize the makespan where the batch capacity is unbounded. The processing time of a job becomes known only upon its arrival. We give an improved lower bound 1 + αmon the competitive ratio, where αmis the positive solution of the equation αm2+ m αm- 1 = 0, and establish a best possible online algorithm matching this lower bound. We also provide a new lower bound 3/2 on the competitive ratio for dense-algorithms, and present a best possible dense-algorithm matching this lower bound.
Original languageEnglish
Pages (from-to)1211-1215
Number of pages5
JournalInformation Processing Letters
Volume109
Issue number21-22
DOIs
Publication statusPublished - 31 Oct 2009

Keywords

  • Algorithms
  • Competitive ratio
  • Makespan
  • Online scheduling
  • Parallel-batch machines

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Signal Processing
  • Theoretical Computer Science

Cite this