DOI: 10.25549/usctheses-c40-335713
title: Newsvendor problems: optimization under resource/demand uncertainty

description: Motivated by wide-ranging applications such as video delivery over networks using Multiple Description Codes (MDP), congestion control, rate adaptation, spectrum sharing, provisioning of renewable energy, inventory management and retail, we study the state-tracking of a Markovian random process with a known transition matrix and a finite ordered state set, where the decision-maker must select a state as an action at each time step in order to minimize the total expected (discounted) cost. ❧ The decision-maker is faced with asymmetries both in cost and observation: in case the selected state is less than the actual state of the Markovian process, an under-utilization cost occurs and only partial observation about the actual state (i.e. an implicit lower bound characteristic on the actual state) is revealed; otherwise, the decision incurs an over-utilization cost and reveals full information about the actual state. ❧ We can formulate this problem as a Partially Observable Markov Decision Process (POMDP), which can be expressed as a dynamic program (DP) based on the last full observed state and the time of full observation. This formulation determines the sequence of actions to be taken between any two consecutive full observations of the actual state, in order to minimize the total expected (discounted) cost. However, this DP grows exponentially in the number of states, with little hope for a computationally feasible solution. ❧ We present an interesting class of computationally tractable policies with a percentile threshold structure. A generalization of binary search, this class of policies attempts at any given time to reduce the uncertainty by a given percentage. Among all percentile policies, we search for the one with the minimum expected cost. The result of this search is a heuristic policy which we evaluate through numerical simulations. We show that it outperforms the myopic policies and under some conditions performs close to the optimal policies. Furthermore, we derive a lower bound on the cost of the optimal policy which can be computed with low complexity and give a measure for how close our heuristic policy is to the optimal policy. ❧ We show the applicability of this problem formulation to congestion control in networks, and video delivery over unreliable networks using Multiple Description Coding (MDC) schemes. We also extend the result to the multi-period inventory control problem with inventory carry-over (i.e. the left-over inventory will be stored for later) and lost sales (i.e. only the sale, minimum of the demand and inventory, is observable). These different extensions need suitable modifications to the problem formulations. The structure of the cost function in the described problem is similar to Newsvendor problem in which the target is a trade-off between over-utilization and under-utilization costs. Inspired by this structure, we also consider another different problem: surgery sequencing in the Operating Room (OR) of hospitals in order to minimize the waiting cost for patients, idle cost for expensive resources such as doctors, surgery staffs, and surgery equipment, and overtime cost in case the surgeries do not finish before the shift end time. The cost structure of this surgery sequencing problem is similar to the Newsvendor problem. ❧ Sequencing and scheduling the surgeries in ORs can be a very important problem since (i) the duration of each surgery can be significantly uncertain, (ii) surgeries are a great source of revenue and a huge source of cost for the hospitals because doctors, OR staff, and surgery equipment are very expensive resources, and (iii) the satisfaction of patients and minimizing their waiting time is also a very important criteria. Solving this problem can reduce the costs and increase the satisfaction of patients significantly, but at the same time it is very hard to drive the solution mathematically. Even the sequencing sub-problem can be challenging if the number of surgeries are large. There is no known tractable optimal solution to this problem and in practice mostly, a heuristic policy which orders surgeries based on increasing duration variances, i.e. the surgery with the smaller variance is scheduled earlier, is applied. ❧ We propose a simple heuristic policy for the sequencing of the surgeries based on the Newsvendor cost and analyze it using a real hospital data set. We show that this heuristic outperforms the ordering based on variance since it takes the asymmetry of waiting and idle costs into account. For the cases where the difference between idle and waiting cost is large, which is the case in surgery sequencing, this heuristic achieves a better improvement in the total expected cost.