Order consolidation for batch processing

Order consolidation for batch processing

0.00 Avg rating0 Votes
Article ID: iaor20053034
Country: Germany
Volume: 9
Issue: 1
Start Page Number: 121
End Page Number: 138
Publication Date: Feb 2005
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: graphs
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∈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)∈E. The objective is to maximize the number of batches filled up to its capacity λ. 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.

Reviews

Required fields are marked *. Your email address will not be published.