Approximation for Batching via Priorities – Facultatea de Informatică

Published in Volume XVII, 2007, pages 1-18

Authors: W. Bein, J. Noga and J. Wiegley

Abstract

We consider here the one-machine serial batching problem under weighted average completion. This problem is known to be $cal Ncal P$-hard and no good approximation algorithms are known. Batching has wide application in manufacturing, decision management, and scheduling in information technology.

We give an approximation algorithm with approximation ratio of 2; the algorithm is a priority algorithm, which batches jobs in decreasing order of priority. We also give a lower bound of (2+√‾6)/4 ≈ 1.1124 on the approximation ratio of any priority algorithm and conjecture that there is a priority algorithm which matches this bound. Adaptive algorithm experiments are used to support the conjecture. An easier problem is the list version of the problem where the order of the jobs is given. We give a new linear time algorithm for the list batching problem.

Full Text (PDF)

References

[1] S. Albers and P. Brucker. The complexity of one-machine batching problems. Discrete Applied Mathematics, 47:87-10, 1993.

[2] P. Baptiste. Batching identical jobs. Mathematical Methods of Operation Research, 52:355-367, 2000.

[3] P. Baptiste and A. Jouglet. On minimizing total tardiness in a serial batching problem. Operations Research, 35:107-115, 2001.

[4] W. Bein, L. Epstein, L. Larmore, and J. Noga. Optimally competitive list batching. In Algorithm Theory – SWAT 2004, volume 3111 of LNCS, pages 77-89. Springer, 2004.

[5] W. Bein, M. Golin, L. Larmore, and Y. Zhang. The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity. Transactions on Algorithms. to appear.

[6] P. Brucker. Scheduling Algorithms. Springer Verlag, 2004.

[7] P. Brucker, A. Gladky, H. Hoogeveen, M. Kovalyov, C. Potts, T. Tautenhahn, and S. van de Velde. Scheduling a batch processing machine. Journal of Scheduling, 1(1):31-54, 1998.

[8] P. Brucker and J. Hurink. Solving a chemical batch scheduling problem by local search. Annals of Operations Research, 96:17-38, 2000.

[9] P. Brucker, M. Y. Kovalyov, Y. M. Shafransky, and F. Werner. Batch scheduling with deadline on parallel machines. Annals of Operations Research, 83:23-40, 1998.

[10] A. Dan, D. Sitaram, and P. Shahabuddin. Scheduling policies for an ondemand video server with batching. In Proceedings of the second ACM international conference on Multimedia, pages 15-23. ACM, 1994.

[11] D. R. Dooly, S. A. Goldman, and S. D. Scott. On-line analysis of the TCP acknowledgment delay problem. Journal of the ACM, 48(2):243-273, 2001.

[12] J. A. Hoogeveen and A. P. A. Vestjens. Optimal on-line algorithms for single-machine scheduling. In Proc. 5th Conf. Integer Programming and Combinatorial Optimization (IPCO), pages 404-414, 1996.

[13] A. R. Karlin, C. Kenyon, and D. Randall. Dynamic TCP acknowledgment and other stories about e/(e-1). Algorithmica, 36(3):209-224, 2003.

[14] R. Kuik, M. Salomon, and L. N. van Wassenhove. Batching decisions: structure and models. European journal of operational research, 75:243-263, 1994.

[15] L. Larmore and B. Schieber. On-line dynamic programming with applications to the prediction of rna secondary structure. Journal of Algorithms, 12:490-515, 1991.

[16] C. N. Potts and L. N. Van Wassenhove. Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. The Journal of the Operational Research Society, 43:395-406, 1992.

[17] C. Prins. Competitive genetic algorithms for the open-shop scheduling problem. Technical report, Ecole des Mines de Nantes, 1999.

[18] L. Raymond. Heuristics for batching jobs under weighted average completion time. Master’s Thesis, University of Nevada, Las Vegas, 2006.

[19] M. Wall. GAlib: A C++ Library of Genetic Algorithm Components. Cambridge, Massachusetts, version 2.4 edition, 1996. http://lancet.mit.edu/ga/.

[20] G. Zhang, X. Cai, C. Y. Lee, and F. Wong. Minimizing makespan on a single batch processing machine with nonidentical job sizes. Naval Research Logistics, 48:226-240, 2001.

Bibtex

@article{sacscuza:bein2007afbvp,
  title={Approximation for Batching via Priorities},
  author={W. Bein and J. Noga and J. Wiegley},
  journal={Scientific Annals of Computer Science},
  volume={17},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2007},
  pages={1--18},
  publisher={``A.I. Cuza'' University Press}
}