Publications
Detailed Information
Approximation of a Batch Consolidation Problem
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chang, Junho | - |
dc.contributor.author | Chang, Soo Y. | - |
dc.contributor.author | Hong, Sung Pil | - |
dc.contributor.author | Min, Yun-Hong | - |
dc.contributor.author | Park, Myoung-Ju | - |
dc.date.accessioned | 2011-12-01T01:44:40Z | - |
dc.date.available | 2011-12-01T01:44:40Z | - |
dc.date.issued | 2011-08-01 | - |
dc.identifier.citation | NETWORKS; Vol.58 1; 12-19 | - |
dc.identifier.issn | 0028-3045 | - |
dc.identifier.uri | https://hdl.handle.net/10371/74914 | - |
dc.description.abstract | In batch production systems, multiple items can be processed in the same batch if they share sufficiently similar production parameters. We consider the batch consolidation problem of minimizing the number of batches of a finite set of items. This article focuses on the case in which only one or two items can be processed in a single batch. The problem is NP-hard and cannot be approximated within 1.0021 of the optimum under the premise, P not equal NP. However, the problem admits a 3/2-approximation. The idea is to decompose the demands of items so that a maximum matching in the graph on the vertices of the decomposed demands provides a well-consolidated batch set. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 12-19 2011 | - |
dc.language.iso | en | - |
dc.publisher | WILEY-BLACKWELL | - |
dc.subject | batch production | - |
dc.subject | approximation algorithm | - |
dc.subject | minimization of batch number inapproximability | - |
dc.title | Approximation of a Batch Consolidation Problem | - |
dc.type | Article | - |
dc.contributor.AlternativeAuthor | 장준호 | - |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.contributor.AlternativeAuthor | 민윤홍 | - |
dc.contributor.AlternativeAuthor | 박명주 | - |
dc.identifier.doi | 10.1002/net.20409 | - |
dc.citation.journaltitle | NETWORKS | - |
dc.description.citedreference | Hong SP, 2009, THEOR COMPUT SCI, V410, P963, DOI 10.1016/j.tcs.2008.11.007 | - |
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, P 4 WORKSH APPR ONL, P160 | - |
dc.description.citedreference | Lee K, 2004, PROD PLAN CONTROL, V15, P495, DOI 10.1080/09537280410001714279 | - |
dc.description.citedreference | SCHRIJVER A, 2003, COMBINATORIAL OPTIMI | - |
dc.description.citedreference | Tang LX, 2001, EUR J OPER RES, V133, P1 | - |
dc.description.citedreference | Chang SY, 2000, PROD PLAN CONTROL, V11, P363 | - |
dc.description.citedreference | Jansen K, 1999, J COMB OPTIM, V3, P363 | - |
dc.description.citedreference | Jansen K, 1997, INFORM COMPUT, V132, P85 | - |
dc.description.citedreference | ARORA S, 1997, APPROXIMATION ALGORI, P399 | - |
dc.description.citedreference | LUND C, 1994, J ACM, V41, P960 | - |
dc.description.citedreference | PAPADIMITRIOU CH, 1991, J COMPUT SYST SCI, V43, P425 | - |
dc.description.citedreference | MICALI S, 1980, P 21 ANN S FDN COMP, P17 | - |
dc.description.tc | 0 | - |
dc.identifier.wosid | 000293234100002 | - |
- 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.