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

Young-Soo Myung and Ilkyeong Moon

Journal of the Operational Research Society, 2020, vol. 71, issue 8, 1301-1305

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.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1609879 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:71:y:2020:i:8:p:1301-1305

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1609879

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().