Order Consolidation for Batch Processing

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.