Preemptive scheduling algorithms with nested processing set restriction

Yumei Huo, Joseph Y.T. Leung, Xin Wang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We consider the problem of preemptively scheduling n independent jobs {J1, J2, ..., Jn} on m parallel machines {M1, M2, ..., Mm}, where each job Jj can only be processed on a prespecified subset Mj of machines called its processing set. The machines are linearly ordered, and the processing set of Jj is specified by two machine indexes aj and b j; i.e., Mj = { Maj, Maj + 1, ... Mb j}. The processing sets are nested; i.e., for i ≠ j, we have Mi⊆Mj, or Mj ⊆Mi, or Mj ∩ Mi = 0. Our goal is to minimize the makespan. We first give an O(n log n)-time algorithm to find an optimal schedule. We then give an O(mn + n log n)-time algorithm to find a maximal schedule, where a schedule is said to be maximal if it processes as much work as any other schedule in any time interval [0, t], t > 0.

Original languageEnglish (US)
Pages (from-to)1147-1160
Number of pages14
JournalInternational Journal of Foundations of Computer Science
Issue number6
StatePublished - Dec 2009

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


  • Inclusive processing set
  • Makespan minimization
  • Nested processing set
  • Polynomial-time algorithms
  • Preemptive scheduling


Dive into the research topics of 'Preemptive scheduling algorithms with nested processing set restriction'. Together they form a unique fingerprint.

Cite this