주문집약문제에 대한 1/3 -근사해법

We consider the order consolidation problem that arises in production systems where customer orders are processed in batches. The problem involves maximizing the number of batches while satisfying the following conditions: (i) the total quantity processed in each batch must be above a prescribed level; (ii) the quantity in an order can be split and processed in more than one batches; (iii) each batch can include up to two different orders but can do so only when the two orders are compatible pair. This problem is known to be NP-hard and max-SNP hard. In this study, we develop an approximation algorithm with factor 1/3.