Publications
Detailed Information
Approximation of the k-batch consolidation problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hong, Sung-Pil | - |
dc.contributor.author | Park, Myoung-Ju | - |
dc.contributor.author | Chang, Soo Y. | - |
dc.date.accessioned | 2012-03-05T02:29:56Z | - |
dc.date.available | 2012-03-05T02:29:56Z | - |
dc.date.issued | 2009-03-01 | - |
dc.identifier.citation | THEORETICAL COMPUTER SCIENCE; Vol.410 8-10; 963-967 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | https://hdl.handle.net/10371/75327 | - |
dc.description.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, 2H(k) - 1, where H(k) = 1 + 1/2 + ... + 1/k (C) 2008 Elsevier B.V. All rights reserved. | - |
dc.language.iso | en | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject | k-batch consolidation problem | - |
dc.subject | Inapproximability | - |
dc.subject | k-set cover problem | - |
dc.subject | Approximation algorithm | - |
dc.title | Approximation of the k-batch consolidation problem | - |
dc.type | Article | - |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.contributor.AlternativeAuthor | 박명주 | - |
dc.identifier.doi | 10.1016/j.tcs.2008.11.007 | - |
dc.citation.journaltitle | THEORETICAL COMPUTER SCIENCE | - |
dc.description.citedreference | CHANG J, 2008, APPROXIMATION UNPUB | - |
dc.description.citedreference | EPSTEIN L, 2007, LECT NOTES COMPUTER, V4927, P232 | - |
dc.description.citedreference | Chlebik M, 2006, THEOR COMPUT SCI, V354, P320, DOI 10.1016/j.tcs.2005.11.029 | - |
dc.description.citedreference | EPSTEIN L, 2006, LECT NOTES COMPUT SC, V4368, P160 | - |
dc.description.citedreference | LEVIN A, 2006, LECT NOTES COMPUT SC, V4368, P290 | - |
dc.description.citedreference | Lee K, 2004, PROD PLAN CONTROL, V15, P495, DOI 10.1080/09537280410001714279 | - |
dc.description.citedreference | Jansen K, 1998, LECT NOTES COMPUT SC, V1432, P35 | - |
dc.description.citedreference | DUH R, 1997, P 29 ANN ACM S THEOR, P256 | - |
dc.description.citedreference | LUND C, 1994, J ACM, V41, P960 | - |
dc.description.tc | 1 | - |
dc.identifier.wosid | 000263945000031 | - |
- Appears in Collections:
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.