Effective Heuristics for Dynamic Pricing and Scheduling Problems with High Dimensionality

Abstract

High-dimensional state spaces and/or decision spaces sometimes arise when sequential operational decisions need to be made dynamically in reflection of complex system information. To tackle the "curse of dimensionality," effective heuristics are needed that achieve both computational efficiency and satisfactory performance (e.g. high revenue or low cost).This dissertation studies two such problems with three essays. The first two essays consider a dynamic pricing problem faced by a seller of a limited amount of inventory over a short time horizon. She faces an unknown demand which she must learn about during the selling season from observing customer purchase decisions. This problem can be formulated as a Bayesian dynamic program, with a high-dimensional state space representing the prior belief about the unknown demand. In the first essay, we develop insights, solution bounds, and heuristics for the problem. It is demonstrated that our derivative-based heuristics provide good revenue performance compared with two well-known algorithms in the literature. In the second essay, we apply open-loop policies to this dynamic pricing problem and reveal counter-intuitive observations. In particular, incorporating more information into a policy may actually hurt its revenue performance. This can be explained by the incomplete learning effect under limited inventory.The third essay studies the hospital's problem to dynamically schedule elective surgeries in advance. Since after surgeries patients stay for a random number of days in an ICU with limited bed capacity, the schedule takes into account current and future ICU congestion and dynamically adjusts itself accordingly. This problem is formulated as a dynamic program where both the state space and the decision space are infinite-dimensional. We devise two schemes to relax the problem as an allocation scheduling problem and use the solution to the relaxed problems to construct heuristic solutions to the original problem. Numerical experiment confirms that our heuristics outperform benchmarks.