Fast approximation algorithms for uniform machine scheduling with processing set restrictions

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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
Volume260
Issue number2
DOIs
StatePublished - Jul 16 2017

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

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

Fingerprint

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