Service Scheduling for Bernoulli Requests and Quadratic Cost

Abstract

We study service scheduling problems in a slotted system in which jobs arrive according to a Bernoulli process and have to leave within two slots after arrival, service costs are quadratic in service rates, and there is also a linear waiting cost. We illustrate how these systems can be used to model CPU speed scaling, EV charging at a charging center, load scheduling in smart grids etc. 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 non-standard cost function structure, rendering the optimization problem complex. We obtain explicit optimal policies in the case when all the jobs are of 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. Further, when the job sizes can take two distinct values, we provide an algorithm that yields the optimal policy. We illustrate different forms of these policies via numerical examples.