Throughput maximization of real-time scheduling with batching

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.

REFERENCES

• 1: Sudhanshu Aggarwal , Juan A. Garay , Amir Herzberg, Adaptive Video on Demand, Proceedings of the Third Annual European Symposium on Algorithms, p.538-553, September 25-27, 1995
• 2: Meral Azizoglu , Scott Webster, Scheduling a batch processing machine with incompatible job families, Computers and Industrial Engineering, v.39 n.3-4, p.325-335, April 1 2001 [doi>10.1016/S0360-8352(01)00009-2]
• 3: Vineet Bafna , Piotr Berman , Toshihiro Fujito, A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem, SIAM Journal on Discrete Mathematics, v.12 n.3, p.289-297, Sept. 1999 [doi>10.1137/S0895480196305124]
• 4: {B-00} P. Baptiste. "Batching Identical Jobs." In Mathematical Methods of Operations Res.,53: 355-367, 2000.
• 5: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.735-744, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335410]
• 6: Amotz Bar-Noy , Sudipto Guha, Approximating the Throughput of Multiple Machines in Real-Time Scheduling, SIAM Journal on Computing, v.31 n.2, p.331-352, 2001 [doi>10.1137/S0097539799354138]
• 7: {BE-85} R. Bar-Yehuda and S. Even. "A Local Ratio Theorem for Approximating the Weighted Vertex Cover Problem." Annals of Discrete Math.,25:27-46, 1985.
• 8: {BD-00} P. Berman and B. DasGupta. "Multi-Phase Algorithms for Throughput Maximization for Real-Time Scheduling." Journal of Combinatorial Optimization,4:307-323, 2000.
• 9: {BG+00} P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. Potts, T. Tautenhahn, and S. L. Van de Velde. "Scheduling a Batching Machine." Journal of Scheduling,1:31-54, 1998.
• 10: J. Chuzhoy, Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.348, October 14-17, 2001
• 11: Chandra Chekuri , Sanjeev Khanna, A PTAS for the multiple knapsack problem, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 09-11, 2000, San Francisco, California, United States
• 12: Asit Dan , Dinkar Sitaram , Perwez Shahabuddin, Dynamic batching policies for an on-demand video server, Multimedia Systems, v.4 n.3, p.112-121, June 1996 [doi>10.1007/s005300050016]
• 13: {DF+99} A. Devpura, J. W. Fowler, M. W. Carlyle, and I. Perez. "Minimizing Total Weighted Tardiness on Single Batch Process Machine with Incompatible Job Families". MS Thesis, 1999.
• 14: {DN-99} D. Dobson and G. Nambimadom. "The Batch Loading and Scheduling Problem." Working Paper QM 92-03, University of Rochester, Rochester, NY.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: {MU-98} S. 'V. Mehta and R. Uzsoy. "Minimizing Total Tardiness on a Batch Processing Machine with Incompatible Jobs Types." IIE Transactions,32:165-175, 1998.
• 17: {ST-01} H. Shachnai and T. Tamir. " On Two Class-Constrained Versions of the Multiple Knapsack Problem." Algorithmica,29:442-467, 2001.
• 18: {S-99} F. C. R. Spieksma. "On the Approximability of an Interval Scheduling Problem." Journal of Scheduling,2:215-227, 1999.
• 19: {U-95} R. Uzsoy. "Scheduling Batch Processing Machines with Incompatible Job Families." Int. J. of Prod. Res.,33:2685-2708, 1995.