Scheduling jobs with equal processing times subject to machine eligibility constraints

Kangbok Lee, Joseph Y.T. Leung, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

Abstract

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.

Original languageEnglish (US)
Pages (from-to)27-38
Number of pages12
JournalJournal of Scheduling
Volume14
Issue number1
DOIs
StatePublished - Feb 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Competitive ratio
  • Eligibility constraint
  • Equal-processing-time jobs
  • Makespan
  • Nested and inclusive eligible sets
  • Online and offline scheduling
  • Parallel machine scheduling
  • Worst-case ratio

Fingerprint

Dive into the research topics of 'Scheduling jobs with equal processing times subject to machine eligibility constraints'. Together they form a unique fingerprint.

Cite this