We investigate a dynamic scheduling framework to assign and route agents to satisfy geographically dispersed stochastic demand. Our problem is motivated by a home healthcare application where health practitioners (HPs) visit their patients on daily tours. We model the decision of which patients to assign to HPs as a discrete-time Markov decision process, and propose an approximate linear programming framework due to the curse of dimensionality and the complex combinatorial structure associated with an HP's daily travel. Specifically, we propose a one-step policy improvement approach where the basis policies are derived from a fluid approximation of the system, leveraging the tour structure to enhance the approximation quality. We study the asymptotic behavior of our fluid system and the resulting allocation and routing optimization model, which can be reduced to a two-stage stochastic program. Our solution methodology is compared to existing policies in a discrete-event simulation using data from a Canadian home care agency.

Weakly coupled Markov decision processes (WDPs) represent a class of multi-stage decision making models with structure that facilitates computationally tractable Lagrangian methods. WDPs ``couple" smaller component Markov decision processes via linking constraints. We investigate the value of new structure aware Lagrangian models that lie between two extremes: standard Lagrangian relaxation, which satisfies linking constraints in expectation, and feasible models that satisfy linking constraints exactly. Our investigation is based on a new combinatorial perspective for finding approximations. This perspective deepens the theoretical understanding of WDP approximations and provides approximation guarantees. We also show that our theory translates to significant improvements in existing feasible models, and enables new structured Lagrangian models of substantially smaller size.

Though variability and uncertainty have always posed challenges for power systems, the increasing use of renewable energy sources has exacerbated these issues. At a vertically integrated utility, the system operator manages many generation units -- renewable and otherwise -- and storage units to ensure that the total energy production matches contemporaneous demand. Current industry practice at these utilities involves solving ``unit commitment'' and ``economic dispatch'' optimization problems to choose production plans: these models, while complex, do not explicitly incorporate uncertainty. In this paper, we develop a dynamic framework to help system operators manage production under uncertainty. We formulate the problem as a stochastic dynamic program and use Lagrangian methods to decompose the system across units. The Lagrangian model relaxes the demand-matching constraint and introduces stochastic Lagrange multipliers that can be interpreted as prices representing the varying marginal value of energy production; each unit is then operated to maximize its own expected ``profit'' given these uncertain prices. These unit-specific value functions are then used to incorporate longer-term effects in dispatch decisions. The unit-specific value functions also provide a way to value generation and storage units in an uncertain environment. We develop relevant theory and demonstrate this dynamic framework using data from the Duke Energy Carolinas and Progress systems. Our numerical experiments demonstrate that this dynamic approach is computationally feasible at an industrial scale and can improve on current practice. Specifically, our results suggest that this dynamic approach can reduce operational costs by about 2\% on average in the present Duke Energy system and, in a ``future'' system with increased solar and storage capacity, can reduce operational costs by 4-5\% on average. Perhaps more strikingly, this dynamic approach, on average, performs within 0.2-0.3\% of production plans based on perfect foresight about future net demands.

We consider infinite horizon Markov decision processes (MDPs) with fast-slow structure, meaning that certain parts of the state space move "fast" (and in a sense, are more influential) while other parts transition more "slowly." Such structure is common in real-world problems where sequential decisions need to be made at high frequencies, yet information that varies at a slower timescale also influences the optimal policy. Examples include: (1) service allocation for a multi-class queue with (slowly varying) stochastic costs, (2) a restless multi-armed bandit with an environmental state, and (3) energy demand response, where both day-ahead and real-time prices play a role in the firm's revenue. Models that fully capture these problems often result in MDPs with large state spaces and large effective time horizons (due to frequent decisions), rendering them computationally intractable. We propose an approximate dynamic programming algorithmic framework based on the idea of "freezing" the slow states, solving a set of simpler finite-horizon MDPs (the lower-level MDPs), and applying value iteration (VI) to an auxiliary MDP that transitions on a slower timescale (the upper-level MDP). We also extend the technique to a function approximation setting, where a feature-based linear architecture is used. On the theoretical side, we analyze the regret incurred by each variant of our frozen-state approach. Finally, we give empirical evidence that the frozen-state approach generates effective policies using just a fraction of the computational cost, while illustrating that simply omitting slow states from the decision modeling is often not a viable heuristic.