Order consolidation for batch processing
SCIE
SCOPUS
- Title
- Order consolidation for batch processing
- Authors
- Hwang, HC; Chang, SY
- Date Issued
- 2005-02
- Publisher
- SPRINGER
- Abstract
- We consider the batch processing of orders where either whole or part of a single order or a specific pair of different orders may be grouped in a batch with a fixed capacity. The problem can be modelled by a graph G = (V,E), where each node v is an element of V corresponds to an order, its weight w(v) corresponds to the amount of ordered quantity and a pair of orders, say u and v may be grouped in a batch if there exists the edge (u,v) is an element of E. The objective is to maximize the number of batches filled up to its capacity lambda . In this paper, we prove that the problem is NP-hard and, moreover, that no PTAS exists unless P = NP. Then, an optimal algorithm is developed with running time O(|V|log |V|) for the special case when G is a tree.
- Keywords
- batch processing; three dimensional matching; tree; SYSTEMS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/24769
- DOI
- 10.1007/S10878-005-5488-Z
- ISSN
- 1382-6905
- Article Type
- Article
- Citation
- JOURNAL OF COMBINATORIAL OPTIMIZATION, vol. 9, no. 1, page. 121 - 138, 2005-02
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.