Best semi-online algorithms for unbounded parallel batch scheduling

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J*(t) denotes the first longest job arriving after t, and p*(t) and r*(t) denote the processing time and arrival time of J*(t), respectively. Given information p*(t), we present an online algorithm with a competitive ratio (5-5)2≈1.382, and show that the algorithm is the best possible; furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J*(t). Given information r*(t), we present an online algorithm with a competitive ratio 32, and show that any online algorithm cannot have a competitive ratio less than 33≈1.442; furthermore, this algorithm generates at most three batches. Given information r*(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (5+1)2≈1.618, and show that the algorithm is the best possible.
Original languageEnglish
Pages (from-to)838-847
Number of pages10
JournalDiscrete Applied Mathematics
Volume159
Issue number8
DOIs
Publication statusPublished - 28 Apr 2011

Keywords

  • Competitive ratio
  • Information in advance
  • Online algorithm
  • Parallel batch scheduling

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this