Approximation Algorithm for Multi-Product Newsboy Problem with Stochastic Yield

Abstract

In this paper, we consider the newsboy problem when two uncertainties are presented, including demand and yield. Based on previous research in this arena, the optimal solution can be obtained analytically for uniform distribution. However, for other distributions the problem becomes much more complex and difficult, in the other words no optimal solution can be found. The reason of this dilemma could be non-integrable property of the objective function. Therefore, we extend that of Karl in 2004 to present the approximation algorithm for general probability distribution, both demand and yield’s randomness are incorporated by different types of probability distribution such as Normal, Uniform and Beta distributions. The algorithm framework consists of two measures: one involving the approximation of the first derivative of the objective functions based on numerical integration; and second involving the problem solving steps based on Newton’s method. From the experiment, it can give the good solution for Normal and other distributions yet it is easy to implement by insert function in available spreadsheet program.