Complexity and relaxation methods for minimising total average cycle stock subject to practical constraints

Abstract

This paper considers the problem of minimising total average cycle stock that is subject to practical constraints, as first studied by Silver and Moon and later by Hsieh, and Billionnet. For the problem, reorder intervals of a population of items are restricted to a given set, and the total number of replenishments allowed per unit time is limited. Previous researchers proposed different mathematical programming formulations and relaxation methods without identifying the computational complexity of the problem. In this study, we investigate the computational complexity of the problem and analyse the proposed relaxation methods. We identify NP-hard and polynomial time solvable cases of the problem and compare three different relaxations in terms of the lower bounds provided by each relaxation method. We also show that the relaxation with the strongest bound can be solved using a linear time greedy algorithm instead of a general-purpose linear programming algorithm.

Keywords:

• Inventory
• complexity
• greedy algorithm

Acknowledgements

The authors are grateful for the valuable comments from the associate editor and anonymous reviewers. The work by Ilkyeong Moon was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT & Future Planning [Grant no. 2017R1A2B2007812 ].

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The work by Ilkyeong Moon was supported by the National Research Foundation of Korea [2017R1A2B2007812].