Fast approximation algorithms for uniform machine scheduling with processing set restrictions

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

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
Pages (from-to)507-513
Number of pages7
JournalEuropean Journal of Operational Research
Volume260
Issue number2
DOIs
Publication statusPublished - 16 Jul 2017

Keywords

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

ASJC Scopus subject areas

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

Cite this