Service or job scheduling problems arise in many contexts such as cloud computing, task scheduling in CPUs, traffic routing and scheduling, production scheduling in plants, scheduling charging of electric vehicles (EVs), etc. For instance, in cloud computing, server power consumption increases as a convex function of the load. Hence, delay-tolerant jobs need to be deferred in order to save on long-term average power costs. The jobs, while being delay tolerant, may not be delay-insensitive and may also have hard deadlines. In all such cases, it is crucial to schedule jobs or services to minimize a weighted sum of service and waiting costs, the latter capturing delay sensitivity of the jobs. We study service scheduling problems with quadratic service costs and linear, quadratic, and fixed waiting costs. We frame the problems as average cost Markov decision processes. While the studied system is a linear system with quadratic costs, it has state-dependent control and a non-standard cost function structure, rendering the optimization problems complex. We provide optimal policy for each of these frameworks. We also consider scenarios where each service request comes from a rational agent interested in optimizing his/her own service and waiting costs rather than the total system cost. In such scenarios, we frame the service-scheduling problems as non-cooperative dynamic games among the agents. We characterize symmetric Nash equilibria and compare these with the solutions to the optimal control problems.
Ramya Burra, IISc Bangalore
Ramya Burra is a Ph.D. student in the Department of ESE at the Indian Institute of Science, Bangalore. She received her B.Tech. degree in 2012. She currently works on optimal resource allocation and their game theoretic solutions. Specifically, she uses techniques and results from Markov Decision Process literature to solve resource allocation problems.