Throughput maximization of real-time scheduling with batching

Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

Abstract

We consider the following scheduling with batching problem that has many applications, e.g., in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or non-explicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a non-preemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ϵ) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ϵ, respectively. We also show exact algorithms for several special cases.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages742-751
Number of pages10
ISBN (Electronic)089871513X
StatePublished - 2002
Externally publishedYes
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Conference

Conference13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/TerritoryUnited States
CitySan Francisco
Period1/6/021/8/02

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Throughput maximization of real-time scheduling with batching'. Together they form a unique fingerprint.

Cite this