Task allocation policies for State Dependent queues

[摘要] Consider a model of a dynamical queue with deterministic arrival and service rates, where the service rate depends on the server utilization history. This proposed queueing model occurs in many practical situations. for example in human-in-the-loop systems where widely accepted empirical laws describe human performance as a function of mental arousal, which increases when the human is working on a task and decreases otherwise. Formal methods for task management in state-dependent dynamical queues are gathering increasing attention to improve the efficiency of such systems. The focus of this research is hence to design maximally stabilizing task release control policies to maximize the useful throughput of such a system. Assuming that the error probability of a server is also related to its state., the useful throughput can be defined as the number of successfully completed tasks per unit time. Monitoring of both service and error rates is particularly typical in the realm of human-in-the-loop and production systems. This research focuses on developing policies to minimize both these penalty measures. For a server with deterministic service rate, the optimal policy is found to be a threshold policy that releases a task to the server only when the server state is less than or equal to a certain threshold. Assuming homogeneous tasks that bring in the same deterministic amount of work to be done, it can be shown that an appropriate threshold policy is maximally stabilizing and that this threshold value can be uniquely determined. This work is then further extended to the case when the server behaves stochastically and verified using simulation. Finally, a proof-of-concept experiment is proposed and developed to test the feasibility of the proposed theoretical policies in real-world settings. The experiment consisted of completing multiple-choice verbal analogy questions and the results confirm the effect of workload control in improving human performance.

[发布机构] Massachusetts Institute of Technology