An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)


We consider the online scheduling of incompatible job families on an unbounded parallel-batch machine to minimize the makespan, where jobs arrive over time and the number of job families, f, is known in advance. We provide an optimal online algorithm for the problem with a competitive ratio of 1+4f2+1-12f.
Original languageEnglish
Pages (from-to)216-219
Number of pages4
JournalOperations Research Letters
Issue number3
Publication statusPublished - 1 May 2013


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

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Applied Mathematics
  • Industrial and Manufacturing Engineering
  • Software

Cite this