Dynamic control of stochastic and fluid resource-sharing systems (contrôle dynamique des systèmes stochastiques et fluides de partage de ressources)

Resumen

In this thesis we study the dynamic control of resource-sharing systems that arise in various domains:e.g. inventory management, healthcare and communication networks. We aim at efficiently allocating theavailable resources among competing projects according to a certain performance criteria. These type ofproblems have a stochastic nature and may be very complex to solve. We therefore focus on developingwell-performing heuristics. In Part I, we consider the framework of Restless Bandit Problems, which isa general class of dynamic stochastic optimization problems. Relaxing the sample-path constraint in theoptimization problem enables to define an index-based heuristic for the original constrained model, the socalledWhittle index policy. We derive a closed-form expression for the Whittle index as a function of thesteady-state probabilities for the case in which bandits (projects) evolve in a birth-and-death fashion. Thisexpression requires several technical conditions to be verified, and in addition, it can only be computedexplicitly in specific cases. In the particular case of a multi-class abandonment queue, we further provethat the Whittle index policy is asymptotically optimal in the light-traffic and heavy-traffic regimes. InPart II, we derive heuristics by approximating the stochastic resource-sharing systems with deterministicfluid models. We first formulate a fluid version of the relaxed optimization problem introduced in PartI, and we develop a fluid index policy. The fluid index can always be computed explicitly and henceovercomes the technical issues that arise when calculating the Whittle index. We apply the Whittle indexand the fluid index policies to several systems: e.g. power-aware server-farms, opportunistic schedulingin wireless systems, and make-to-stock problems with perishable items. We show numerically that bothindex policies are nearly optimal. Secondly, we study the optimal scheduling control for the fluid versionof a multi-class abandonment queue. We derive the fluid optimal control when there are two classesof customers competing for a single resource. Based on the insights provided by this result we build aheuristic for the general multi-class setting. This heuristic shows near-optimal performance when appliedto the original stochastic model for high workloads. In Part III, we further investigate the abandonmentphenomena in the context of a content delivery problem. We characterize an optimal grouping policy sothat requests, which are impatient, are efficiently transmitted in a multi-cast mode. // In this thesis we study the dynamic control of resource-sharing systems that arise in various domains:e.g. inventory management, healthcare and communication networks. We aim at efficiently allocating theavailable resources among competing projects according to a certain performance criteria. These type ofproblems have a stochastic nature and may be very complex to solve. We therefore focus on developingwell-performing heuristics. In Part I, we consider the framework of Restless Bandit Problems, which isa general class of dynamic stochastic optimization problems. Relaxing the sample-path constraint in theoptimization problem enables to define an index-based heuristic for the original constrained model, the socalledWhittle index policy. We derive a closed-form expression for the Whittle index as a function of thesteady-state probabilities for the case in which bandits (projects) evolve in a birth-and-death fashion. Thisexpression requires several technical conditions to be verified, and in addition, it can only be computedexplicitly in specific cases. In the particular case of a multi-class abandonment queue, we further provethat the Whittle index policy is asymptotically optimal in the light-traffic and heavy-traffic regimes. InPart II, we derive heuristics by approximating the stochastic resource-sharing systems with deterministicfluid models. We first formulate a fluid version of the relaxed optimization problem introduced in PartI, and we develop a fluid index policy. The fluid index can always be computed explicitly and henceovercomes the technical issues that arise when calculating the Whittle index. We apply the Whittle indexand the fluid index policies to several systems: e.g. power-aware server-farms, opportunistic schedulingin wireless systems, and make-to-stock problems with perishable items. We show numerically that bothindex policies are nearly optimal. Secondly, we study the optimal scheduling control for the fluid versionof a multi-class abandonment queue. We derive the fluid optimal control when there are two classesof customers competing for a single resource. Based on the insights provided by this result we build aheuristic for the general multi-class setting. This heuristic shows near-optimal performance when appliedto the original stochastic model for high workloads. In Part III, we further investigate the abandonmentphenomena in the context of a content delivery problem. We characterize an optimal grouping policy sothat requests, which are impatient, are efficiently transmitted in a multi-cast mode.