  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. When assigned a server, a node can execute a task. The
tasks are independently generated at each node by stochastically symmetric and
memoryless random processes and stored in a finite-capacity task queue.
Moreover, they are time-sensitive in the sense that within each slot there is a
non-zero probability 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. It is also demonstrated
that the MP coincides with the Whittle index policy. For task queues of
arbitrary capacity instead, the myopic policy is generally suboptimal, and its
performance is compared with an upper bound obtained through a relaxation of
the original problem. Overall, the settings in this paper provide a rare
example where a RMAB problem can be explicitly solved, and in which the Whittle
index policy is proved to be optimal.
