Service scheduling with Service Waiting and Dissatisfaction costs

Abstract

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 cost. 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. In several systems, jobs are admitted only at slot boundaries, but they can leave as soon as their services are complete, e.g., consider EVs at EV Charging stations. Then the waiting period of an agent can depend on the amount of deferred service. To capture the disutility due to waiting in such cases, we introduce waiting costs that are linear in the amount of deferred services. We study service scheduling problems with quadratic service costs and linear 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 problem complex. We obtain explicit optimal policies in the case when all the jobs are of the same size. In particular, we show that the optimal policy is linear or piece-wise linear in the system state, depending on the system parameters. We extend our study to a scenario where job sizes can take distinct values and job arrivals constitute a Markov chain. We provide an algorithm that yields the optimal scheduling policy but has exponential complexity. Hence, we propose an approximate policy of linear complexity and derive its performance bound. We also study systems with maximum sojourn time of three slots. To account for higher us...