标题： 跟踪并分配任务到马尔可夫机器 显示英文标题

标题： Tracking and Assigning Jobs to a Markov Machine

摘要： 我们考虑一个时隙通信系统，其中包括一台机器、一个云服务器和一个采样器。 用户的工作请求在服务器上排队，由机器完成。 机器有两种状态，即忙碌状态和空闲状态。 服务器可以以先进先出的方式将工作分配给机器。 如果机器处于空闲状态，它将完成来自服务器的工作请求；否则，它会丢弃该请求。 在丢弃工作请求时，服务器会受到惩罚。 当机器处于空闲状态时，机器可以通过内部工作进入忙碌状态。 当服务器未将工作请求分配给机器时，机器的状态演化为一个对称的马尔可夫链。 如果机器成功接受来自服务器的工作请求，机器的状态将进入忙碌状态，并且其动态与由于内部工作进入忙碌状态时的动态不同。 采样器对机器的状态进行采样，并通过无错误信道将其发送到服务器。 因此，服务器可以在接收到来自源的更新后估计机器的状态。 如果机器处于空闲状态，但服务器处的估计状态为忙碌，则采样器会支付成本。 我们将不正确信息的年龄概念纳入模型以模拟采样器的成本。 我们的目标是找到一个最优的采样策略，使得采样器的成本加上对机器的惩罚最小化。 我们将这个问题形式化为一个马尔可夫决策过程框架，并研究最优策略如何随着几个相关参数变化。 我们证明了阈值策略对于这个问题是最优的。 我们给出了一个阈值策略成为最优的必要充分条件。 最后，我们在不限制状态空间的情况下找到了最优阈值。 显示英文摘要

摘要： We consider a time-slotted communication system with a machine, a cloud server, and a sampler. Job requests from the users are queued on the server to be completed by the machine. The machine has two states, namely, a busy state and a free state. The server can assign a job to the machine in a first-in-first-served manner. If the machine is free, it completes the job request from the server; otherwise, it drops the request. Upon dropping a job request, the server is penalized. When the machine is in the free state, the machine can get into the busy state with an internal job. When the server does not assign a job request to the machine, the state of the machine evolves as a symmetric Markov chain. If the machine successfully accepts the job request from the server, the state of the machine goes to the busy state and follows a different dynamics compared to the dynamics when the machine goes to the busy state due to an internal job. The sampler samples the state of the machine and sends it to the server via an error-free channel. Thus, the server can estimate the state of the machine, upon receiving an update from the source. If the machine is in the free state but the estimated state at the server is busy, the sampler pays a cost. We incorporate the concept of the age of incorrect information to model the cost of the sampler. We aim to find an optimal sampling policy such that the cost of the sampler plus the penalty on the machine gets minimized. We formulate this problem in a Markov decision process framework and find how an optimal policy changes with several associated parameters. We show that a threshold policy is optimal for this problem. We show a necessary and sufficient condition for a threshold policy to be optimal. Finally, we find the optimal threshold without bounding the state space.