A Hardness Result for the Joint Replenishment Problem with Constant Costs and Demands
We study the classical joint replenishment problem (JRP) with constant costs and demands . The objective is to coordinate a sequence of orders of multiple commodities, aiming to supply a constant demand rate over a time horizon of length T, with minimum overall ordering and holding costs. We show a hardness result for a particular variant of JRP where we restrict the orders to be placed periodically (GI policy with correction factor). In this setting, we prove that finding the optimal renewal ordering per commodity is as hard as integer factorization. This is the first hardness result for any variant of JRP with constant costs and demands.
