Approximating the throughput of multiple machines under real-time scheduling

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber

Research output: Contribution to journalConference articlepeer-review

34 Scopus citations

Abstract

We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to find a schedule that maximizes the weight of jobs that meet their deadline. We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated), and the weight of the jobs (identical vs. arbitrary). All these variants are known to be NP-Hard, and we observe that the two variants involving unrelated machines are also MAX-SNP hard. To the best of our knowledge, these are the first approximation algorithms for such problems in the non-preemptive off-line setting.

Original languageEnglish (US)
Pages (from-to)622-631
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Approximating the throughput of multiple machines under real-time scheduling'. Together they form a unique fingerprint.

Cite this