The performance ratio of grouping policies for the joint replenishment problem (Q689953)

In an EOQ model with \(n\) products, joint setup costs provide incentives for joint replenishments. These joint setup costs may be modelled as a positive, nondecreasing, submodular set function. A grouping heuristic partitions the \(n\) products into groups, and all products in the same group are always jointly replenished. Each group is thus considered as a single ``aggregate product'' being replenished independently of the other groups and according to the EOQ formula. As a result, possible savings when several groups are simultaneously replenished are simply ignored. The problem of determining the worst-case performance ratio of grouping policies is formulated as a maximum problem, which is neither quasiconcave nor quasiconvex. We use a novel approach to estimate an upper bound. We find that the cost of a best grouping policy is no more than 44.8\% above the optimal cost.