Fast approximation algorithms for job scheduling with processing set restrictions

Yumei Huo, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4/3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5/3, which is better than the best known algorithm whose worst-case bound is 7/4. In both cases, we will give examples achieving the worst-case bounds.

Original languageEnglish (US)
Pages (from-to)3947-3955
Number of pages9
JournalTheoretical Computer Science
Volume411
Issue number44-46
DOIs
StatePublished - Oct 25 2010

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Inclusive processing set
  • Makespan minimization
  • NP-hard
  • Nested processing set
  • Nonpreemptive scheduling
  • Polynomial-time approximation algorithm
  • Tree-hierarchical processing set

Fingerprint

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

Cite this