| dc.description.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. | en_US |
