Parallel machine scheduling with nested processing set restrictions

Yumei Huo, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


We consider the problem of scheduling a set of n independent jobs on m parallel machines, where each job can only be scheduled on a subset of machines called its processing set. The machines are linearly ordered, and the processing set of job j is given by two machine indexes aj and bj; i.e., job j can only be scheduled on machines aj, aj + 1, ..., bj. Two distinct processing sets are either nested or disjoint. Preemption is not allowed. Our goal is to minimize the makespan. It is known that the problem is strongly NP-hard and that there is a list-type algorithm with a worst-case bound of 2 - 1 / m. In this paper we give an improved algorithm with a worst-case bound of 7/4. For two and three machines, the algorithm gives a better worst-case bound of 5/4 and 3/2, respectively.

Original languageEnglish (US)
Pages (from-to)229-236
Number of pages8
JournalEuropean Journal of Operational Research
Issue number2
StatePublished - Jul 16 2010

All Science Journal Classification (ASJC) codes

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


  • Approximation algorithm
  • Makespan
  • NP-hard
  • Nested processing set restrictions
  • Nonpreemptive scheduling
  • Worst-case bound


Dive into the research topics of 'Parallel machine scheduling with nested processing set restrictions'. Together they form a unique fingerprint.

Cite this