Technical Note—A Partitioning Problem with Additive Objective with an Application to Optimal Inventory Groupings for Joint Replenishment

We consider a problem of optimal grouping and provide conditions under which an optimal partition of an ordered set S = {r 1 , …, r n } consists of subsets of consecutive elements. We transform the problem into the problem of finding a shortest path on a directed acyclic graph with n + 1 vertices (for which efficient algorithms exist). These results may be used to solve the problem of grouping n items in stock into subgroups with a common order cycle per group so as to minimize the resulting economic order quantity costs.