Throughput maximization of real-time scheduling with batching

ABSTRACT

We consider the following scheduling with batching problem that has many applications, for example, 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 nonexplicitly), 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 nonpreemptive 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 give approximation algorithms for two special cases when all release times are the same.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Nikhil Bansal , Don Coppersmith , Maxim Sviridenko, Improved approximation algorithms for broadcast scheduling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.344-353, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109596]
• 4: Baptiste, P. 2000. Batching identical jobs. Math. Meth. Oper. Res. 53, 355--367.
• 5: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 6: Amotz Bar-Noy , Sudipto Guha , Yoav Katz , Joseph (Seffi) Naor , Baruch Schieber , Hadas Shachnai, Throughput maximization of real-time scheduling with batching, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.742-751, January 06-08, 2002, San Francisco, California
• 7: 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]
• 8: Bar-Yehuda, R., and Even, S. 1985. Local ratio theorem for approximating the weighted vertex cover problem. Ann. Disc. Math. 25, 27--46.
• 9: Berman, P., and DasGupta, B. 2000. Multi-phase algorithms for throughput maximization for real-time scheduling. J. Combinat. Optimizat. 4, 307--323.
• 10: Boggia, G., Camarda, P., Mazzeo, L., and Mongiello, M. 2005. Performance of batching schemes for multimedia-on-demand services. IEEE Trans. Multimed. 7, 920--931.
• 11: Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C., Tautenhahn, T., and Van de Velde, S. L. 1998. Scheduling a batching machine. J. Sched. 1, 31--54.
• 12: Chandra Chekuri , Sanjeev Khanna, A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem, SIAM Journal on Computing, v.35 n.3, p.713-728, 2005 [doi>10.1137/S0097539700382820]
• 13: Julia Chuzhoy , Rafail Ostrovsky , Yuval Rabani, Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems, Mathematics of Operations Research, v.31 n.4, p.730-738, November 2006 [doi>10.1287/moor.1060.0218]
• 14: 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]
• 15: Gregory Dobson , Ramakrishnan S. Nambimadom, The Batch Loading and Scheduling Problem, Operations Research, v.49 n.1, p.52-65, January 2001 [doi>10.1287/opre.49.1.52.11189]
• 16: Gailis, R., and Khuller, S. 2003. Broadcast scheduling with deadlines. Unpublished mansucript. (www.cs.umd.edu/users/samir/grant/renars.ps)
• 17: Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy , Aravind Srinivasan, Dependent rounding and its applications to approximation algorithms, Journal of the ACM (JACM), v.53 n.3, p.324-360, May 2006 [doi>10.1145/1147954.1147956]
• 18: Hochbaum, D. S., and Landy, D. 1997. Scheduling semiconductor burn-in operations to minimize total flowtime. Oper. Res. 45, 874--885.
• 19: Katz, Y. 2001. Scheduling with batching and incompatible job families. M.S. dissertation, Computer Science Dept., Technion, Haifa, Israel.
• 20: Lee, V. W. H., Wong, E. W. M., Ko, K.-T., and Tang, K.-S. 2005. Multimedia-on-demand systems with broadcast, batch and interactive services. IEICE Trans. Commun. E88-B, 3097--3100.
• 21: Mehta, S. V., and Uzsoy, R. 1998. Minimizing total tardiness on a batch processing machine with incompatible jobs types. IIE Trans. Sched. Log. 30, 165--175.
• 22: Imelda C. Perez , John W. Fowler , W. Matthew Carlyle, Minimizing total weighted tardiness on a single batch process machine with incompatible job families, Computers and Operations Research, v.32 n.2, p.327-341, February 2005 [doi>10.1016/S0305-0548(03)00239-9]
• 23: Shachnai, H., and Tamir, T. 2001. On two class-constrained versions of the multiple knapsack problem. Algorithmica 29, 442--467.
• 24: Spieksma, F. C. R. 1999. On the approximability of an interval scheduling problem. J. Sched. 29, 442--467.
• 25: Uzsoy, R. 1995. Scheduling batch processing machines with incompatible job families. Int. J. Prod. Res. 33, 2685--2708.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory

Keywords:
Scheduling, batching, local ratio technique