On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks

Details On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks

2011-12-06

arxiv.org/abs/1112.1229v1

Mathematics

Optimization and Control

Submitted to IEEE Transactions on Automatic Control, Nov. 2011. 33 pages, 5 figures

Scientific paper

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. The M nodes execute tasks that are independently generated at each node by stochastically symmetric and memoryless random processes. The tasks are stored by each node in a finite-capacity task queue, and 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 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. Overall, the scheduling problem considered herein is general. Practical applications include the scheduling of packet transmissions in wired and wireless networks and tasks assignment for distributed computing. 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, which is also demonstrated to coincide with the Whittle index policy. For task queues of arbitrary capacity, the myopic policy is generally suboptimal, and its performance is compared with an upper bound obtained through a relaxation of the original problem. The settings in this paper provide a rare example where a RMAB problem can be explicitly solved, and the Whittle index policy proved to be optimal.

Affiliated with

Also associated with

No associations

Rating

On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Optimal Scheduling of Independent, Symmetric and Time-Sensitive Tasks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-380910