Browse

Approximation of a Batch Consolidation Problem

Cited 0 time in Web of Science Cited 1 time in Scopus
Authors
Chang, Junho; Chang, Soo Y.; Hong, Sung Pil; Min, Yun-Hong; Park, Myoung-Ju
Issue Date
2011-08-01
Publisher
WILEY-BLACKWELL
Citation
NETWORKS; Vol.58 1; 12-19
Keywords
batch productionapproximation algorithmminimization of batch number inapproximability
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
ISSN
0028-3045
Language
English
URI
https://hdl.handle.net/10371/74914
DOI
https://doi.org/10.1002/net.20409
Files in This Item:
There are no files associated with 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