TY - GEN
T1 - Throughput maximization of real-time scheduling with batching
AU - Bar-Noy, Amotz
AU - Guha, Sudipto
AU - Katz, Yoav
AU - Naor, Joseph
AU - Schieber, Baruch
AU - Shachnai, Hadas
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84968799934&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84968799934&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84968799934
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 742
EP - 751
BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PB - Association for Computing Machinery
T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Y2 - 6 January 2002 through 8 January 2002
ER -