Approximation algorithms for batch scheduling with processing set restrictions

Xing Chai, Wenhua Li, C. T. Ng, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review


We consider batch scheduling on m machines to minimize the makespan. Each job has a given set of machines to be assigned. Each machine can process several jobs simultaneously as a batch, and the machines may have different batch capacities. We study two models: (i) scheduling on equal-speed batch machines under a nested processing set restriction, where the machines have the same processing speed, and (ii) scheduling on uniform batch machines under a tree-hierarchical processing set restriction, where the machines have different processing speeds. For both models we design polynomial-time approximation algorithms to solve them. The algorithms have a worst-case ratio of 2 for non-identical batch capacities and a worst-case ratio of 2 - 1 / m for identical batch capacities.

Original languageEnglish
JournalJournal of Scheduling
Publication statusAccepted/In press - 2022


  • Batch
  • Makespan
  • Processing set restrictions
  • Scheduling
  • Uniform machines

ASJC Scopus subject areas

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

Cite this