A higher-order Markov model for the Newsboy's problem

Abstract

Markov models are commonly used in modelling many practical systems such as telecommunication systems, manufacturing systems and inventory systems. However, higher-order Markov models are not commonly used in practice because of their huge number of states and parameters that lead to computational difficulties. In this paper, we propose a higher-order Markov model whose number of states and parameters are linear with respect to the order of the model. We also develop efficient estimation methods for the model parameters. We then apply the model and method to solve the generalised Newsboy's problem. Numerical examples with applications to production planning are given to illustrate the power of our proposed model.

Keywords:

• higher-order Markov model
• Newsboy's model
• shortage cost
• overage cost

Acknowledgements

We thank the two anonymous referees for their helpful comments. Their constructive suggestions enhanced the readability of this paper. This research was supported in part by RGC Grant No. HKU 7126/02P and HKU CRCG Grant Nos. 10203408, 10203501, 10203907, 10203919, 10204436.