Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan

Ruyan Fu, Edwin Tai Chiu Cheng, Chi To Ng, Jinjiang Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio ?3+12 ≈ 1.366. For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366.
Original languageEnglish
Pages (from-to)444-450
Number of pages7
JournalInformation Processing Letters
Volume110
Issue number11
DOIs
Publication statusPublished - 16 May 2010

Keywords

  • Analysis of algorithm
  • Competitive ratio
  • Limited restart
  • Online scheduling
  • Parallel-batching machines

ASJC Scopus subject areas

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

Cite this