SHERP

Approximation of k-batch consolidation problem

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Hong, Sung-Pil; Park, Myoung-Ju; Chang, Soo Y.
Issue Date
2008-11-24
Publisher
Elsevier
Citation
Theoretical Computer Science 410 (2009) 963-967
Keywords
k-batch consolidation problem; Inapproximability; Approximation algorithm; k-set cover problem
Abstract
We consider a problem of minimizing the number of batches of a fixed capacity processing the orders of various sizes on a finite set of items. This batch consolidation problem is motivated by the production system typical in raw material industries in which multiple items can be processed in the same batch if they share sufficiently close production parameters. If the number of items processed in a batch is restricted to being up to some fixed integer k, the problem is referred to as the k-batch consolidation problem. We will show that the k-batch consolidation problem admits an approximation whose factor is twice that of the k-set cover problem. In particular, this implies an upper bound on the approximation factor, 2Hk−1, where...
ISSN
0304-3975
Language
English
URI
http://hdl.handle.net/10371/5331
DOI
https://doi.org/10.1016/j.tcs.2008.11.007
https://doi.org/10.1016/j.tcs.2008.11.007
Files in This Item:
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse