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 user sensitivity to incremental delays, we also study job scheduling problems with quadratic service costs and quadratic waiting costs – quadratic waiting costs can be employed to capture higher job sensitivity to delays. Job arrivals and sojourn times are as in the previous problem. Our problem is a constrained optimization linear quadratic control Markov decision problem. However, unconstrained problem of our formulation can be cast as a standard linear quadratic control Markov decision problem. 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 in the system state. When the job sizes can take two or more distinct values, we provide an algorithm that yields the optimal policy. We propose a policy to cater to the cases with unknown parameters. In several systems of interest, agents can enter the system or leave only at slot boundaries, e.g., compute tasks derive utility only at slot boundaries. In such tasks that complete only at slot boundaries, the current operating job will be present in the system until its next slot boundary irrespective of the amount of pending service. Thus, the waiting involved is fixed and does not depend on the amount of deferred service. We study service scheduling problems in a slotted system where jobs arrive according to a Bernoulli process and have to leave within two slots after arrival. The service cost is quadratic in service rate, and a job also incurs a fixed waiting cost if it is not completed in the first slot after its arrival. We provide the optimal policy when the parameters satisfy certain conditions. We also propose an approximate policy that enables us to characterize the optimal policy. In all the above setups, we also consider scenarios where each service request comes from a rational agent interested in optimizing his/her own service and waiting costs. For example, in the context of EV charging, EV owners being rational agents would be interested in minimizing their own cost instead of the total system cost. In such scenarios we can frame service-scheduling problem as a non-cooperative dynamic game among the agents. Finally, we characterize symmetric Nash equilibria in all these cases. We next consider a more general scenario where job arrival statistics are unknown, jobs’ sojourn times are arbitrary, and service costs are convex increasing functions. We study job or service scheduling as a continuous-time problem with convex increasing service costs and linear waiting costs with focus on minimizing service and job waiting costs. We first consider the offline version of the problem where arrival times, requirements and deadlines of all the jobs are known a priori. We propose job scheduling algorithms that minimize the total accrued cost. We then consider the online version of the problem and propose two heuristics. Our problem can be seen as an extension of the well studied speed scaling problem with a waiting cost also included. Finally, we study service scheduling problems with service cost being a piecewise linear convex function of service rate. We now assume that service rates are upper bounded. Here, the central facility is not bound to serve of every job by its deadline. Hence, we do not consider waiting cost but consider a dissatisfaction cost instead. We model disutility for not serving the required amount in the form of dissatisfaction cost. We study the following variants of the service scheduling problem: (a) Stochastic arrivals with common departure epoch, (b) Common arrival epoch but distinct departure epochs, (c) Stochastic arrivals with maximum sojourn time of two slots, and (d) Stochastic arrivals with arbitrary sojourn times. We derive slot dependent optimal policies for cases (a), (b). We derive slot independent optimal policy for (c). We propose a heuristic for case (d) based on the optimal policy of common arrival epoch but distinct departure epochs.