화학공학소재연구정보센터
IEEE Transactions on Automatic Control, Vol.58, No.9, 2421-2425, 2013
On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks
Consider a discrete-time system in which a centralized controller (CC) is tasked with assigning at each time interval (or slot) K resources (or servers) to K out of M >= K nodes. A node can execute a task when assigned to a server. The tasks are independently generated at each node by stochastically symmetric and memoryless random processes and stored in a finite-capacity task queue. The tasks are time-sensitive since there is a non-zero probability, within each slot, that a task expires before being scheduled. The scheduling problem is tackled with the aim of maximizing the number of tasks completed over time (or the task-throughput) under the assumption that the CC has no direct access to the state of the task queues. The scheduling decisions at the CC are based on the outcomes of previous scheduling commands, and on the known statistical properties of the task generation and expiration processes. Based on a Markovian modeling of the task generation and expiration processes, the CC scheduling problem is formulated as a partially observable Markov decision process (POMDP) that can be cast into the framework of restless multi-armed bandit (RMAB) problems. When the task queues are of capacity one, the optimality of a myopic (or greedy) policy is proved. The settings in this technical note provide a rare example where a RMAB problem can be explicitly solved.