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

15 Citations (Scopus)


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
Issue number4
Publication statusPublished - 1 Aug 2011


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

ASJC Scopus subject areas

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

Cite this