A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

14 Citations (Scopus)

Abstract

We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5-√5)/2.We give an online algorithm for the considered problem with a competitive ratio (5 -√5)/2 ≈ 1.382.
Original languageEnglish
Pages (from-to)361-369
Number of pages9
JournalJournal of Scheduling
Volume14
Issue number4
DOIs
Publication statusPublished - 1 Aug 2011

Keywords

  • Competitive ratio
  • Online algorithm
  • Parallel-batch scheduling
  • Restart

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Engineering(all)
  • Management Science and Operations Research

Cite this