论文标题
二次等待费用的随机请求的服务安排
Service Scheduling for Random Requests with Quadratic Waiting Costs
论文作者
论文摘要
我们研究了一个插槽系统中的服务调度问题，在该系统中，代理商根据Bernoulli流程将服务请求到达，并且必须在到达后的两个插槽内离开，服务费用是二次的服务率，并且也有等待费用。我们考虑二次等待成本。我们将问题作为平均成本Markov决策过程的平均成本。虽然研究的系统是具有二次成本的线性系统，但它具有状态依赖的控制。此外，在固定等待成本的情况下，它还具有非标准的成本函数结构，使优化问题复杂化。我们表征了最佳政策。我们提供一个明确的表达式，表明最佳策略在系统状态中是线性的。我们还考虑了代理商为各自的服务请求做出安排决策的系统，以保持自己的成本。我们将二次等待成本视为随机游戏。我们提供了这款游戏的NASH均衡。为了解决未知系统参数的问题，我们提出了一种算法来估算它们。我们还约束了使用估计参数所产生的实际成本和成本的成本差异。
We study service scheduling problems in a slotted system in which agents arrive with service requests according to a Bernoulli process and have to leave within two slots after arrival, service costs are quadratic in service rates, and there are also waiting costs. We consider quadratic waiting costs. We frame the problems as average cost Markov decision processes. While the studied system is a linear system with quadratic costs, it has state dependent control. Moreover, it also possesses a non-standard cost function structure in the case of fixed waiting costs, rendering the optimization problem complex. We characterize optimal policy. We provide an explicit expression showing that the optimal policy is linear in the system state. We also consider systems in which the agents make scheduling decisions for their respective service requests keeping their own cost in view. We consider quadratic waiting costs and frame these scheduling problems as stochastic games. We provide Nash equilibria of this game. To address the issue of unknown system parameters, we propose an algorithm to estimate them. We also bound the cost difference of the actual cost incurred and the cost incurred using estimated parameters.
