Premium
Approximation of a batch consolidation problem
Author(s) -
Chang Junho,
Chang Soo Y.,
Hong SungPil,
Min YunHong,
Park MyoungJu
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20409
Subject(s) - consolidation (business) , matching (statistics) , computer science , mathematical optimization , premise , batch production , set (abstract data type) , graph , mathematics , combinatorics , operations management , statistics , engineering , linguistics , philosophy , accounting , programming language , business
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 N P ‐hard and cannot be approximated within 1.0021 of the optimum under the premise, P ≠ N P . However, the problem admits a ${{3}\over{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. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 12–19 2011