A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

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

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that Mj = {Maj, Maj + 1, ..., Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.

Original languageEnglish (US)
Pages (from-to)292-298
Number of pages7
JournalDiscrete Optimization
Volume6
Issue number3
DOIs
StatePublished - Aug 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

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

Fingerprint

Dive into the research topics of 'A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions'. Together they form a unique fingerprint.

Cite this