This paper considers joint replenishment problems (JRP) of n items under deterministic and constant demand. Two new algorithms for JRP are proposed, based on a pair of tighter bounds for optimal cyclic time. The proposed algorithms can be used to determine the optimal cyclic policy and the optimal strict cyclic policy. Both algorithms are qualified for JRP with small major set-up costs, while only one of them can cope with JRP with any type of major set-up costs. Numerical experiments on randomly generated problems show that the new algorithms significantly outperform the existing exact algorithms for almost all of the test problems.
