Approximate Dynamic Programming for Dynamic Stochastic Resource Allocation with Applications to Healthcare

Applications in diverse fields including manufacturing, logistics, healthcare, telecommunications, and computing require that renewable resources be allocated dynamically to distinct classes of job service requests arriving randomly over slotted time. Depending on the application, arriving service requests are typically handled in one of two ways---(i) they either wait in queue, are rejected/diverted, or served immediately; or (ii) they are scheduled to specific future service slots. The former is termed allocation scheduling whereas the latter is called advanced scheduling. For example, in healthcare operations management, non-critical patients arriving at an emergency room wait to receive service; requests for hospital admissions are handled daily; whereas surgeries are often scheduled a few weeks ahead of time. The system manager's goal then is to devise a resource utilization strategy to optimize a system performance metric over a fixed or an indefinite horizon.;Such dynamic stochastic resource allocation problems very quickly become analytically and computationally intractable as the number of job classes increases beyond a few. This has severely limited a majority of quantitative research in this area to restrictive special cases such as two job classes and a single resource thus curtailing its applicability in practice. For instance, a hospital in reality may perform ten different types of surgeries or admit patients from dozens of different diagnosis related groups (DRGs).;In this dissertation, we formally introduce two large classes of dynamic stochastic resource allocation problems; one of these involves allocation scheduling and the other employs advanced scheduling. We formulate Markov Decision Process (MDP) models for these problems and build upon recent advances in Approximate Dynamic Programming (ADP) to develop efficient algorithms for their approximate solution. The central theme in almost all of this dissertation is that, in a given time-period, there is only one link interconnecting service decisions made regarding different job classes---the multi-dimensional knapsack-type constraints on total resource consumption. We show that this puts our models within the class of weakly coupled MDPs, and consequently build upon a recent Lagrangian relaxation technique akin to that of integer programming to approximately solve these otherwise intractable MDPs. We demonstrate that this high-level idea applies irrespective of the specific cost, revenue, arrival stream and stochastic service duration structure, and hence can be used to tackle a broad range of realistic large-scale problems in practice.;A detailed review of related literature is included in Chapter 2. Chapter 3 focuses on allocation scheduling problems where jobs incur a holding cost while waiting in queue to receive service, a penalty cost of rejection/diversion when the queue is filled to capacity, and generate a reward on completion. The goal is to select which jobs to service in each time-period so as to maximize total infinite-horizon discounted expected profit. We first study problems where service durations are deterministic and equal one time-period, then consider geometric service durations, and finally investigate general stochastic service durations. The state and action spaces of the corresponding three MDP models are increasingly more complex in structure and larger in size. We fortunately are able to show however that the MDPs are all weakly coupled and hence apply Lagrangian relaxation to approximate their optimal value functions. Exploiting the weakly coupled structure, we design an efficient dynamic programming approach to retrieve allocation scheduling policies from these approximate value functions on the fly. Our computational experiments reveal that these policies significantly outperform two common heuristics---a myopic policy and a microc-type rule (a heuristic that prioritizes jobs based on their rewards, costs, service durations, and resource consumptions).;In Chapter 4, we study advanced scheduling problems where arriving jobs are scheduled to future time-periods in a finite-length booking horizon. Costs incurred depend on the time between arrival and service and the planner is also penalized for rejecting/diverting jobs. The objective is to minimize total infinite-horizon discounted expected costs. The state and action spaces in the corresponding MDP model grow exponentially in both the number of job classes and the hooking horizon, rendering it intractable. We convert this MDP into an equivalent weakly coupled one, and design a hybrid Lagrangian relaxation-linear programming column generation approach to compute its approximate value function. A simple integer program is then solved to obtain advanced scheduling policies from this approximate value function on the fly. Computational results show that this approximation method significantly outperforms an intuitive rolling horizon policy.;Chapter 5 focuses on three healthcare applications of dynamic stochastic resource allocation. We first study an allocation scheduling problem arising from patient service decisions in a Computed Tomography section using data from Harborview Medical Center in Seattle. Then we apply the models and methods in Chapter 3 to allocation scheduling problem in healthcare settings. Finally, we employ the methodology in Chapter 4 to an operating room advanced scheduling problem.