Fast approximation algorithms for uniform machine scheduling with processing set restrictions

Joseph Y.T. Leung, C. T. Ng

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We consider the problem of nonpreemptively scheduling a set of independent jobs on a set of uniform machines, where each job has a set of machines to which it can be assigned. This kind of restriction is called the processing set restriction. In the literature there are many kinds of processing set restrictions that have been studied. In this paper we consider two kinds: the “inclusive processing set” and the “tree-hierarchical processing set”. Epstein and Levin (2011) have given Polynomial Time Approximation Schemes (PTAS) to solve both classes. However, the running times of their PTAS are rather high. In this paper, we give fast approximation algorithms for both cases and show that they both have a worst-case performance bound of 4/3. Moreover, we show that the bounds are achievable.

Original languageEnglish (US)
Pages (from-to)507-513
Number of pages7
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Jul 16 2017

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Inclusive processing set
  • Makespan
  • Scheduling
  • Tree-hierarchical processing set
  • Uniform machines
  • Worst-case bound


Dive into the research topics of 'Fast approximation algorithms for uniform machine scheduling with processing set restrictions'. Together they form a unique fingerprint.

Cite this