Online scheduling on unbounded parallel-batch machines with incompatible job families

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

We consider online scheduling on m parallel-batch machines where the batch capacity is unbounded and the jobs belong to m incompatible job families. By incompatible job families, we mean that jobs from different families cannot be processed together in the same batch. The processing time of a job becomes known only upon its arrival. The objective is to minimize the makespan. The problem is difficult to solve so we consider the case where the number of families is equal to the number of machines. We give a lower bound 5+12≈1.618 on the competitive ratio of any online algorithm for this restricted problem. We also provide an online algorithmHm(θ), where θ∈(0,1) is a parameter, and show that its competitive ratio is no less than 1+105≈1.632. When m=2 or under the condition that jobs belonging to the same family have identical processing times, we show thatHm(α), where α=5-12, is a best possible online algorithm. When m<3, we prove thatHm(β), where β=2-1, has a competitive ratio no greater than 1+1β+1≈1.707.
Original languageEnglish
Pages (from-to)2380-2386
Number of pages7
JournalTheoretical Computer Science
Volume412
Issue number22
DOIs
Publication statusPublished - 13 May 2011

Keywords

  • Competitive ratio
  • Incompatible job families
  • Online scheduling
  • Parallel-batch machines

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this