# Fluid Limits for Shortest Job First with Aging

Yonatan Shadmi
<EMAIL_ADDRESS>Viterbi Faculty of Electrical Engineering,
Technion – Israel Institute of Technology, Haifa 32000, Israel

###### Abstract

We investigate fluid scaling of single server queueing systems under the
shortest job first with aging (SJFA) scheduling policy. We use the measure-
valued Skorokhod map to characterize the fluid limit for SJFA queues with a
general aging rule and establish convergence results to the fluid limit. We
treat in detail examples of linear and exponential aging.

AMS subject classifications: 60K25, 60G57, 68M20

Keywords: measure-valued Skorokhod map, measure-valued processes, fluid
limits, shortest job first, aging

##  1 Introduction

It is well known that prioritizing jobs by their size is optimal in the sense
of minimizing the number of jobs in system at any point in time ([16], [19]).
This could be important in systems with limited buffer size. As the average
number of jobs in the queue and the average waiting time are related by
Little’s law, minimizing the number of jobs in the buffer is equivalent to
minimizing the average waiting time ([17],[12]). However, these kind of
policies may cause starvation and deny resource access from large sized jobs.
To avoid this undesired phenomenon, more dynamic approaches have been
suggested, that take into consideration the sojourn time as well as the job
size. In particular, the priority of a job is dictated initially by its size,
and is updated as time elapses. This is done in practice ([2], [8]) and is
common in the literature of computer science ([18], [4], [6]), and is known as
aging. In this case, even large sized jobs will eventually have higher
priority than smaller jobs with later arrival time. Scaling limits of such
policies have not been treated before, even though both fluid and diffusion
limits of SJF were extensively studied. This paper analyzes and characterizes
fluid limits of SJFA for the first time; the main tool is the measure valued
Skorokhod map from [1].

Prominent examples of aging rules are linear ([18]), exponential ([2],[8]),
_highest response ratio next_ (HRRN) ([4]) and the _fair sojourn protocol_
(FSP) ([6]). Among the many aging rules that our analysis covers, the linear
is the simplest one and most of the examples in this paper consider this rule.
Though somewhat more cumbersome, the exponential rule is used in practice in
UNIX ([2], [8]), which motivates us to study it in details as well. HRRN and
FSP are essentially different and are explained later. The exponential aging
rule in UNIX is implemented as follows (as described in [8], where other
details and examples can be found). One employs the rule

$\displaystyle pri=cpu\\_use+base+nice$

where: $pri$ stands for the priority value of a job at the current time, and
lower priority value corresponds to higher priority; $cpu\\_use$ stands for
recent CPU usage and is the term responsible of the aging. This value
increases linearly in time only when the process is running (discretely on
every clock interrupt), and is divided by two every second; $base$ is the base
priority for user processes; $nice$ is an optional additional term, if a user
is willing to reduce its own priority and be nice to others. In our analysis,
we ignore the terms $base$ and $nice$, as well as the linear increase of
$cpu\\_use$ which is irrelevant in non-preemptive policies because it happens
only while the process is running and not while it waits for service. Note
that the updating rule of $cpu\\_use$ is a discrete time version of
exponential aging due to the division by two every second of the priority
value.

The linear and exponential aging rules are the simplest among the above
examples, as they belong to a class of deterministic aging rules with non-
intersecting aging trajectories. Here, by aging trajectories we mean
trajectories on the time-priority plane, describing how a job priority is
updated with time. This means that jobs do not exchange places in the priority
ordering as time progresses. A generalization of these two rules is the class
of aging rules that can be described through an ordinary differential
equation. In this paper, we consider this class of aging rules.

Job size based priority systems is an active research topic in the operations
research literature since the work of Schrage and Miller [17], [16] (see also
[19] for a simpler proof of optimaility). In particular, some research effort
has been devoted to scaling limits of such policies. Fluid limits of the
preemptive version, the shortest remaining processing time policy, were shown
to exist, be unique, and were characterized in [7]. To describe the evolution
of the system, a measure valued process was used, one that counts the number
of jobs in the queue with job size in some set.

Diffusion scaling limits for _shortest remaining processing time_ (SRPT), the
preemptive version of the SJF, appeared shortly after in [9] under heavy
traffic assumption, again using measure valued processes as state descriptors.
The measure counting the number of jobs in the queue with size in some set is
shown to converge to a Dirac measure, concentrated on the rightmost point of
the support of the job size distribution. The magnitude of the limiting Dirac
delta is a reflected Brownian motion divided by the largest possible job size
(zero if the job size is unbounded). A followup of this work is [15], where
non-standard diffusion limit was taken to show a generalized state space
collapse- the queue length and the workload converge to the same process.

In [1], Atar et al. prove convergence to the fluid limit of several priority
queues, including SRPT and SJF. They introduce a measure valued Skorokhod map,
and use it to map the arrival process and the server effort process to a
measure valued state descriptor. This technique allows considering also time-
varying arrival and service distributions.

Most of the work on such policies studies SRPT, however, Gromoll and Keutel
argue in [10] that, at least on fluid scale, the performance of SRPT and SJF
is the same (they converge to the same fluid limit). See also [14], [11] and
[3] for more comparisons between SJF and SRPT.

Though the literature on SJF and SRPT and their asymptotic behaviour is rich,
there is no mentioning of aging in this context. With aging, the system state
changes not only when jobs arrive and depart, but also vary with time, as the
priority values undergo aging. These dynamics prevent a direct use of the
measure valued Skorokhod map as in [1].

Our objective here is to expand the existing asymptotic analysis to include
SJFA with deterministic aging and non-overlapping trajectories. The idea is to
first identify a coordinate transformation that transforms the system into an
equivalent system, and then use the measure valued Skorokhod map with measures
defined on the new coordinate system. As an easy example, for linear aging,
let $S_{i}$ and $\tau_{i}$ be the $i$-th job’s size and arrival time, resp.
Whereas SJFA prioritizes according to $S_{i}-\left(t-\tau_{i}\right)$, this is
equivalent to prioritizing according to $S_{i}+\tau_{i}$, which is independent
of time. For a general aging rule, this transformation requires further
effort. With these means we are able to prove convergence to the fluid limit
and characterize the limit.

Indeed, linear and exponential aging rules belong to the class of aging rules
that are described by an ordinary differential equation, as mentioned above.
However, we have also mentioned the HRRN and the FSP, which are important
policies that avoid starvation, but do not fall in the category we cover in
this work. In the HRRN policy, all jobs are assigned on arrival the same
priority value, but this value increases with a rate which is the inverse of
the job size. Thus, the aging trajectories do intersect, making it impossible
to use our method. In the FSP, there is a virtual processor sharing server and
jobs enter service in the order of their virtual departure process. In this
setting, the aging trajectories are stochastic; they depend on the system
state. This is a much more interesting and complicated situation which, we
assume, requires much more sophisticated tools to analyze. This motivates us
to seek further tools to cover other settings.

The paper is organized as follows. In §2 we introduce the queueing model and
state the main theorem. The proof is given in §3. §4 provides four examples
with different arrival distributions and aging rules.

### Notation

For any Polish space ${\cal S}$, let ${\mathbb{D}}_{\cal S}$ denote the space
of càdlàg functions from ${\mathbb{R}}_{+}$ to ${\cal S}$, equipped with the
Skorokhod J1 metric. Let ${\mathbb{C}}$ denote its subspace of continuous
functions. If ${\cal S}={\mathbb{R}}_{+}$ we simply write ${\mathbb{D}}$ and
${\mathbb{C}}$. Let $\mathbb{D}^{\uparrow}$ denote the subspace of non-
decreasing elements of ${\mathbb{D}}$. Let ${\cal M}$ denote the space of
finite Borel measures on ${\mathbb{R}}$ equipped with the Lévy metric, which
induces the topology of weak convergence, and let ${\cal M}_{0}$ denote its
subspace of atomless Borel measures on ${\mathbb{R}}$. It is well known that
${\cal M}$ is a Polish space, and so is $\mathbb{D}_{{\cal M}}$. Let
$\mathbb{D}_{{\cal M}}^{\uparrow}$ denote the subspace of non-decreasing
elements of $\mathbb{D}_{{\cal M}}$, where an element $\nu$ of
$\mathbb{D}_{{\cal M}}$ is said to be non-decreasing if $t\mapsto\int
fd\nu_{t}$ is non-decreasing for every non-negative continuous and bounded
function $f$.

##  2 SJFA

###  2.1 Queueing model

Consider a sequence of single server queues, indexed by $N\in{\mathbb{N}}$,
operating under the SJFA with the same aging policy. Whenever the server is
available, it admits the highest priority job into service, where the priority
of each job is as follows. The system keeps track of each job’s priority
value, where lower value means higher priority. Each job is assigned an
initial value on arrival which is the job size. The value, $g$, varies
smoothly with time according to an aging rule. To formalize this, we order the
jobs according to their arrival, and denote by $\tau_{i}^{N}$ and $S_{i}^{N}$
the arrival time and job size, resp., of the $i$-th job to enter the $N$-th
system. The fact that the initial priority value is the job size is expressed
by

$\displaystyle g\left(\tau_{i}^{N}\right)=S_{i}^{N}.$ (1)

The aging rule is modeled by the differential equation

$\displaystyle\frac{dg}{ds}=f\left(g,s\right),\quad s\geq\tau_{i}^{N}.$ (2)

In the context of aging, $f$ is assumed to be negative, as the priority of a
job increases as times progresses (i.e. $g$ is decreasing). The linear and
exponential aging rules correspond to the choices $f\left(g,s\right)=-c$ and
$f\left(g,s\right)=-\lambda g$, resp., for constants $c,\lambda>0$.

In fact, under certain conditions, Equation (2) can be solved backwards as
well to obtain a solution for all $s$ in ${\mathbb{R}}_{+}$. This fact is used
is this work and, considering Equations (1) and (2) jointly, the aging
trajectory of the $i$-th job is described by

$\displaystyle\begin{cases}\frac{d}{ds}g=f\left(g,s\right),\quad
s\in{\mathbb{R}}_{+},\\\ g\left(\tau_{i}^{N}\right)=S_{i}^{N}.\end{cases}$ (3)

We require that $f$ is Lipschitz in the first argument. Then this problem
admits a unique solution on ${\mathbb{R}}_{+}$ ([5, Theorem 6]), that is, a
unique aging trajectory $g:{\mathbb{R}}_{+}\to{\mathbb{R}}$ satisfying
$g\left(\tau_{i}^{N}\right)=S_{i}^{N}$. This way, any point
$\left(x,t\right)\in{\mathbb{R}}_{+}^{2}$ has exactly one trajectory passing
through it, denoted $g_{\left(x,t\right)}$. In particular,
$g_{i}^{N}:=g_{\left(S_{i}^{N},\tau_{i}^{N}\right)}$ is the unique function
$h:{\mathbb{R}}_{+}\to{\mathbb{R}}$ such that
$\frac{d}{ds}h=f\left(h(s),s\right)$, $s\in{\mathbb{R}}_{+}$, and
$h\left(\tau_{i}^{N}\right)=S_{i}^{N}$. The trajectories of the linear and
exponential aging rules are, resp.,
$g_{\left(x,t\right)}\left(s\right)=x-c\left(s-t\right)$ and
$g_{\left(x,t\right)}\left(s\right)=x\exp\left(-\lambda\left(s-t\right)\right)$
(see Figure 1).

Figure 1: Illustration of aging trajectories in the cases of linear aging
(left hand side) and exponential aging (right hand side). The arrows
illustrate the flow of a priority value on the time-priority plane. The lines
describe the trajectories that the priority values follow.

We denote by $\theta_{i}^{N}$ the departure time of the $i$-th job, but stress
that in our model the priority value continues to change according to the
aging rule even after the job has departed from the system.

We introduce the following processes, underlying the queueing model in this
section.

$\displaystyle\alpha^{N}$ $\displaystyle:\quad$
$\displaystyle\alpha_{t}^{N}\left(-\infty,x\right]\text{ is the work to have
arrived at the queue by time $t$ }$ (4) $\displaystyle\text{with priority
value in $\left(-\infty,x\right]$ at time $t$},$ $\displaystyle\mu^{N}$
$\displaystyle:$ $\displaystyle\mu^{N}\left(t\right)\text{ is the total work
the server can complete by time $t$, if it is never idle},$
$\displaystyle\xi^{N}$ $\displaystyle:$
$\displaystyle\xi_{t}^{N}\left(-\infty,x\right]\text{ is the work in the queue
at time $t$ with priority value in $\left(-\infty,x\right]$ at time $t$},$
$\displaystyle\beta^{N}$ $\displaystyle:$
$\displaystyle\beta_{t}^{N}\left(-\infty,x\right]\text{ is the work completed
by the server by time $t$, with priority value in $\left(-\infty,x\right]$}$
$\displaystyle\text{at time $t$}.$

The sample paths of $\alpha^{N}$, $\xi^{N}$ and $\beta^{N}$ are in
$\mathbb{D}_{{\cal M}}$, and $\mu^{N}$ has sample paths in
$\mathbb{D}^{\uparrow}$. Mathematically, $\alpha^{N},\beta^{N}$ and $\xi^{N}$
are given by

$\displaystyle\alpha_{t}^{N}\left(-\infty,x\right]=\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\tau_{i}^{N}\leq
t\right\\}}\mathbbm{1}_{\left\\{g_{i}^{N}\left(t\right)\leq x\right\\}}$ (5)
$\displaystyle\beta_{t}^{N}\left(-\infty,x\right]=\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\theta_{i}^{N}\leq
t\right\\}}\mathbbm{1}_{\left\\{g_{i}^{N}\left(t\right)\leq x\right\\}},$ (6)
$\displaystyle\xi_{t}^{N}\left(-\infty,x\right]=\alpha_{t}^{N}\left(-\infty,x\right]-\beta_{t}^{N}\left(-\infty,x\right]=\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\tau_{i}^{N}\leq
t<\theta_{i}^{N}\right\\}}\mathbbm{1}_{\left\\{g_{i}^{N}\left(t\right)\leq
x\right\\}}.$ (7)

The initial state of the buffer is already contained in $\alpha_{0}^{N}$. We
assume that $\mu$ is given by
$\mu\left(t\right)=\int_{0}^{t}m^{N}\left(s\right)ds$, where
$m^{N}\left(s\right)$ is the service rate at time $s$ satisfying
$m^{N}\left(s\right)\geq m_{0}>0$ for all $s$. Define the busyness process
$B^{N}\left(t\right)=\mathbbm{1}_{\left\\{\text{The server is busy at time
$t$}\right\\}}$; then the work done by the server by time $t$ is
$T^{N}\left(t\right)=\int_{0}^{t}m^{N}\left(s\right)B^{N}\left(s\right)ds$,
and $\iota^{N}=\mu^{N}-T^{N}$ is the lost work due to idleness. Let the
process $J\left(t\right)$ denote the residual work of the job in service at
time $t$. It then holds that

$\displaystyle\beta_{t}^{N}\left[0,\infty\right)=T^{N}\left(t\right)+J^{N}\left(t\right)-J^{N}\left(0\right).$

At any time when the server is ready to serve a new job, the scheduler admits
to service the job with the highest priority, i.e. with the smallest priority
value. If the queue is empty and the server is idle, the next job to arrive
will be immediately admitted.

###  2.2 Main result

We provide sufficient conditions for
$\left(\bar{\xi}^{N},\bar{\beta}^{N},\bar{\iota}^{N}\right)$ to weakly
converge as a result, and characterize this weak limit by a formula.

######  Assumption 1.

The function $f$ in (3) is continuous as a function of two variables, and is
globally Lipschitz in the first argument on ${\mathbb{R}}_{+}^{2}$, i.e.
satisfies

$\displaystyle\left|f\left(x_{1},t\right)-f\left(x_{2},t\right)\right|\leq
L\left|x_{1}-x_{2}\right|$

for some $L>0$ for all $\left(x_{1},t\right)$ and $\left(x_{2},t\right)$ in
${\mathbb{R}}\times{\mathbb{R}}_{+}$.

Assumption 1 guaranties the existence of a unique path, $g\left(s\right)$,
that solves the ODE ([5, Theorem 6])

$\displaystyle\begin{cases}\frac{\partial}{\partial
s}g=f\left(g,s\right),\quad s\in{\mathbb{R}}_{+},\\\
g\left(t\right)=x,\end{cases}$

for any given $x$ and $t$. The uniqueness of the path is on
${\mathbb{R}}\times{\mathbb{R}}_{+}$ in the sense that there is only one
solution passing through any point
$\left(x,t\right)\in{\mathbb{R}}\times{\mathbb{R}}_{+}$. As a consequence, two
solution paths are either the same path, or do not intersect.

######  Theorem 1.

Let the aging rule be as in (3). Suppose that Assumption 1 holds and that
$\left(\bar{\alpha}^{N},\bar{\mu}^{N}\right)\Rightarrow\left(\alpha,\mu\right)\in\mathbb{C}_{{\cal
M}_{0}}^{\uparrow}\times\mathbb{C}^{\uparrow}$. Denote
$\Xi\left(t,x\right):=\alpha_{t}\left(-\infty,g_{\left(x,0\right)}\left(t\right)\right]$.
Then
$\left(\bar{\xi}^{N},\bar{\beta}^{N},\bar{\iota}^{N}\right)\Rightarrow\left(\xi,\beta,\iota\right)$,
where for all $x$ and $t>0$

$\displaystyle\beta_{t}\left(x,\infty\right)+\iota\left(t\right)=-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,g_{\left(x,t\right)}\left(0\right)\right)-\mu\left(s\right)\right)\land
0\right\\},$ (8)
$\displaystyle\xi_{t}\left(-\infty,x\right]=\Xi\left(t,g_{\left(x,t\right)}\left(0\right)\right)-\mu\left(t\right)-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,g_{\left(x,t\right)}\left(0\right)\right)-\mu\left(s\right)\right)\land
0\right\\}.$ (9)

Above, (9) characterizes the measure valued process $\xi$, and (8)
characterizes both $\iota$ and $\beta$ by taking the limit $x\to\infty$ and
then subtracting $\iota(t)$.

In the proof given in the next section, the characterization of the limit is
expressed by other means. The somewhat complicated notation above is used in
order to avoid introducing a transformation of coordinates.

##  3 Proof

The fluid model is the unique triplet
$\left(\xi^{\prime},\beta^{\prime},\iota\right)\in\mathbb{D}_{{\cal
M}}\times\mathbb{D}_{{\cal M}}^{\uparrow}\times\mathbb{D}^{\uparrow}$
satisfying for given data
$\left(\alpha^{\prime},\mu\right)\in\mathbb{D}_{{\cal
M}}^{\uparrow}\times\mathbb{D}^{\uparrow}$ the following relations.

  1. 1.

$\xi^{\prime}\left[0,x\right]=\alpha^{\prime}\left[0,x\right]-\mu+\beta^{\prime}\left(x,\infty\right)+\iota$,

  2. 2.

$\xi^{\prime}\left[0,x\right]=0$ $d\beta^{\prime}\left(x,\infty\right)-a.s.$,

  3. 3.

$\xi^{\prime}\left[0,x\right]=0$ $d\iota-a.s.$,

  4. 4.

$\beta^{\prime}\left[0,\infty\right)+\iota=\mu$.

This was introduced as the measure-valued Skorokhod problem (MVSP) in [1],
followed by an existence and uniqueness theorem ([1, Proposition 2.8]).

Recall that the sample paths of $\alpha^{N}$ and $\beta^{N}$ belong to
$\mathbb{D}_{{\cal M}}$ but not to $\mathbb{D}_{{\cal M}}^{\uparrow}$, so it
is not yet clear how the MVSP is relevant to our model.

The MVSP defines a map
$\left(\xi^{\prime},\beta^{\prime},\iota\right)=\Theta\left(\alpha^{\prime},\mu\right)$,
referred to as the measure-valued Skorokhod map (MVSM). Namely, for each $x$,
$\left(\xi^{\prime}\left[0,x\right],\beta^{\prime}\left(x,\infty\right)+\iota\right)=\Gamma\left(\alpha^{\prime}\left[0,x\right]-\mu\right)$,
where $\Gamma:{\mathbb{D}}\to{\mathbb{D}}_{+}\times\mathbb{D}^{\uparrow}$,
$\Gamma(\psi)=\left(\Gamma_{1}(\psi),\Gamma_{2}(\psi)\right)$, is the
Skorokhod map

$\displaystyle\Gamma_{1}\left(\psi\right)\left(t\right)=\psi\left(t\right)-\inf_{s\in\left[0,t\right]}\left(\psi\left(s\right)\land
0\right),$
$\displaystyle\Gamma_{2}\left(\psi\right)\left(t\right)=-\inf_{s\in\left[0,t\right]}\left(\psi\left(s\right)\land
0\right).$

Note that (8) and (9) have this form exactly with
$\psi=\Xi\left(\cdot,g_{\left(x,t\right)}\left(0\right)\right)-\mu$.

###### Proof of Theorem 1.

The proof opens with the definition of a coordinate transformation,
$\varphi:{\mathbb{R}}\times{\mathbb{R}}_{+}\to{\mathbb{R}}\times{\mathbb{R}}_{+}$,
that maps a point $\left(x,t\right)\in{\mathbb{R}}\times{\mathbb{R}}_{+}$ to a
point
$\left(x^{\prime},t^{\prime}\right)=\varphi\left(x,t\right)\in{\mathbb{R}}\times{\mathbb{R}}_{+}$,
such that $\alpha^{\prime}$ and $\beta^{\prime}$ do belong to
$\mathbb{D}_{{\cal M}}^{\uparrow}$, where $\alpha^{\prime}$ and
$\beta^{\prime}$ are the weak limits of the measures defined by

$\displaystyle\bar{\alpha^{\prime}}^{N}_{t^{\prime}\left(x,t\right)}\left[0,x^{\prime}\left(x,t\right)\right]=\bar{\alpha}^{N}_{t}\left(-\infty,x\right],$
$\displaystyle\bar{\beta^{\prime}}^{N}_{t^{\prime}\left(x,t\right)}\left[0,x^{\prime}\left(x,t\right)\right]=\bar{\beta}^{N}_{t}\left(-\infty,x\right].$

The coordinate transformation
$\left(x^{\prime},t^{\prime}\right)=\varphi\left(x,t\right)$ is based on the
uniqueness of the path $g_{\left(x,t\right)}$ due to Assumption 1; for any
point $\left(x,t\right)$, we assign the point
$\left(x^{\prime},t^{\prime}\right)$, given by

$\displaystyle\begin{cases}t^{\prime}=t,\\\
x^{\prime}=g_{\left(x,t\right)}\left(0\right).\end{cases}$

The purpose of this transformation is to transform the aging trajectories in
such a way that the priorities do not vary with time in the new system. The
inverse transformation is given by

$\displaystyle\begin{cases}t=t^{\prime},\\\
x=g_{\left(x^{\prime},0\right)}\left(t^{\prime}\right).\end{cases}$

Note that $x^{\prime}\geq 0$ because $g(t)$ is assumed to be decreasing.

It will be convenient to define a function $F:\mathbb{D}_{{\cal
M}}\to\mathbb{D}_{{\cal M}}$ such that $\nu^{\prime}=F\left(\nu\right)$ is
defined by

$\displaystyle\nu^{\prime}_{t^{\prime}}\left[0,x^{\prime}\right]=\nu_{t\left(x^{\prime},t^{\prime}\right)}\left(-\infty,x\left(x^{\prime},t^{\prime}\right)\right].$

By the inverse transformation, the relation
$\nu=F^{-1}\left(\nu^{\prime}\right)$ corresponds to the relation

$\displaystyle\nu_{t}\left(-\infty,x\right]=\nu^{\prime}_{t^{\prime}\left(x,t\right)}\left[0,x^{\prime}\left(x,t\right)\right].$

Note that $x^{\prime}\mapsto\nu^{\prime}_{t}\left[0,x^{\prime}\right]$ is
right-continuous for all $t>0$ because

$\displaystyle\left|\nu^{\prime}_{t}\left[0,x^{\prime}+\varepsilon\right]-\nu^{\prime}_{t}\left[0,x^{\prime}\right]\right|=\nu_{t}\left(x\left(x^{\prime},t\right),x\left(x^{\prime}+\varepsilon,t\right)\right],$

and, by Theorem 6 in [5],

$\displaystyle\left|x\left(x^{\prime}+\varepsilon,t\right)-x\left(x^{\prime},t\right)\right|=\left|g_{\left(x^{\prime}+\varepsilon,t\right)}\left(t\right)-g_{\left(x^{\prime},t\right)}\left(t\right)\right|\leq\varepsilon
e^{Lt}\to_{\varepsilon}0.$

In addition, it is monotone as $x^{\prime}\mapsto
x\mapsto\nu_{t}\left(-\infty,x\right]$ is. We will show later that
$\alpha^{\prime}$ has indeed sample paths in $\mathbb{D}_{{\cal
M}}^{\uparrow}$, and thus the fluid model can be defined through
$\left(\xi^{\prime},\beta^{\prime},\iota\right)=\Theta\left(\alpha^{\prime},\mu\right)$,
and $\xi=F^{-1}\left(\xi^{\prime}\right)$,
$\beta=F^{-1}\left(\beta^{\prime}\right)$.

Recall the model description from §2.1. Note that under Assumption 1 the
following conditions are equivalent:

$\displaystyle g_{i}^{N}\left(t\right)\leq
x=g_{\left(x,t\right)}\left(t\right)\iff{S^{\prime}}_{i}^{N}:=g_{i}^{N}\left(0\right)\leq
g_{\left(x,t\right)}\left(0\right)=x^{\prime}.$

With this, by Equations (5)-(7), $\alpha^{N}$, $\beta^{N}$ and $\xi^{N}$ take
the form

$\displaystyle\alpha_{t}^{N}\left(-\infty,x\right]=\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\tau_{i}^{N}\leq
t\right\\}}\mathbbm{1}_{\left\\{{S^{\prime}}_{i}^{N}\leq
x^{\prime}\right\\}}={\alpha^{\prime}}_{t^{\prime}}^{N}\left[0,x^{\prime}\right],$
(10)
$\displaystyle\beta_{t}^{N}\left(-\infty,x\right]=\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\theta_{i}^{N}\leq
t\right\\}}\mathbbm{1}_{\left\\{{S^{\prime}}_{i}^{N}\leq
x^{\prime}\right\\}}={\beta^{\prime}}_{t^{\prime}}^{N}\left[0,x^{\prime}\right],$
(11)
$\displaystyle\xi_{t}^{N}\left(-\infty,x\right]=\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\tau_{i}^{N}\leq
t<\theta_{i}^{N}\right\\}}\mathbbm{1}_{\left\\{{S^{\prime}}_{i}^{N}\leq
x^{\prime}\right\\}}={\xi^{\prime}}_{t^{\prime}}^{N}\left[0,x^{\prime}\right].$
(12)

Now,
$t^{\prime}\mapsto{\beta^{\prime}}_{t^{\prime}}^{N}\left(x^{\prime},\infty\right)$
is monotone and ${\alpha^{\prime}}^{N}\in\mathbb{D}_{{\cal M}}^{\uparrow}$.

Under Assumption 1, the priority condition is equivalent to the condition

$\displaystyle\begin{cases}\theta_{i}^{N}\geq\tau_{j}^{N}\\\
\theta_{j}^{N}\geq\tau_{i}^{N}\\\
g_{i}^{N}\left(0\right)<g_{j}^{N}\left(0\right)\end{cases}\Longrightarrow\theta_{i}^{N}<\theta_{j}^{N}.$

This implies

$\displaystyle\int{\xi^{\prime}}_{t}^{N}\left[0,x^{\prime}\right]d{\beta^{\prime}}_{t}^{N}\left(x^{\prime},\infty\right)$
$\displaystyle=\sum_{j=1}^{\infty}{\xi^{\prime}}_{\theta_{j}^{N}}^{N}\left[0,x^{\prime}\right]\left({\beta^{\prime}}_{\theta_{j}^{N}}^{N}\left(x^{\prime},\infty\right)-{\beta^{\prime}}_{\theta_{j}^{N}-}^{N}\left(x^{\prime},\infty\right)\right)$
$\displaystyle=\sum_{j=1}^{\infty}\sum_{i=1}^{\infty}S_{i}^{N}\mathbbm{1}_{\left\\{\tau_{i}^{N}\leq\theta_{j}^{N}<\theta_{i}^{N}\right\\}}\mathbbm{1}_{\left\\{g_{i}^{N}\left(0\right)\leq
x^{\prime}\right\\}}S_{j}^{N}\mathbbm{1}_{\left\\{g_{j}^{N}\left(0\right)>x^{\prime}\right\\}}$
$\displaystyle=0.$

Moreover, the non-idling property implies

$\displaystyle{\xi^{\prime}}^{N}\left[0,x^{\prime}\right]=0\quad
d{\iota}^{N}\quad a.s.$

In addition

$\displaystyle{\xi^{\prime}}_{t}^{N}\left[0,x^{\prime}\right]={\alpha^{\prime}}_{t}^{N}\left[0,x^{\prime}\right]-{\beta^{\prime}}_{t}^{N}\left[0,x^{\prime}\right]={\alpha^{\prime}}_{t}^{N}\left[0,x^{\prime}\right]-\mu^{N}\left(t\right)+\iota^{N}\left(t\right)-J^{N}\left(t\right)+J^{N}\left(0\right)+{\beta^{\prime}}_{t}^{N}\left(x^{\prime}\infty\right),$

and note that ${\alpha^{\prime}}^{N}\in\mathbb{D}_{{\cal M}}^{\uparrow}$ and
$\mu^{N}+J^{N}-J\left(0\right)\in\mathbb{D}^{\uparrow}$. The later is
justified by writing

$\displaystyle\mu^{N}+J^{N}-J\left(0\right)=\left(\mu^{N}-T^{N}\right)+\left(T^{N}+J^{N}-J\left(0\right)\right)=\iota^{N}+\beta^{N}\left[0,\infty\right).$

The above holds for the scaled processes as well, thus
$\left(\bar{{\xi^{\prime}}}^{N},\bar{{\beta^{\prime}}}^{N},\bar{\iota}^{N}\right)=\Theta^{\prime}\left(\bar{{\alpha^{\prime}}}^{N},\bar{\mu}^{N}+\bar{J}^{N}-\bar{J}^{N}\left(0\right)\right)$.

By Lemma 1 and the continuous mapping theorem, it follows that
$\bar{\alpha}^{N}\Rightarrow\alpha$ if and only if
$\bar{{\alpha^{\prime}}}^{N}\Rightarrow\alpha^{\prime}=F\left(\alpha\right)\in\mathbb{C}_{{\cal
M}}$. In addition,

$\displaystyle\alpha^{\prime}_{t}\left(\\{x^{\prime}\\}\right)=\alpha^{\prime}_{t}\left[0,x^{\prime}\right]-\alpha^{\prime}_{t}\left[0,x^{\prime}\right)=\alpha_{t}\left(-\infty,x\right]-\alpha_{t}\left(-\infty,x\right)=\alpha_{t}\left(\\{x\\}\right)=0,$

so $\alpha^{\prime}_{t^{\prime}}$ is also atomless. Finally,
$\mathbb{D}_{{\cal M}}^{\uparrow}$ is a closed subset of $\mathbb{D}_{{\cal
M}}$ ([1, Lemma 2.4]), and each ${\alpha^{\prime}}^{N}$ is in
$\mathbb{D}_{{\cal M}}^{\uparrow}$, so we conclude that $\alpha^{\prime}$ is
in $\mathbb{C}_{{\cal M}_{0}}^{\uparrow}$.

We now have the same setting as in Theorem 5.13 from [1], by which
$\left(\bar{\xi^{\prime}}^{N},\bar{\beta^{\prime}}^{N},\bar{\iota}^{N}\right)\Rightarrow\Theta^{\prime}\left(\alpha^{\prime},\mu\right)$.
Finally, by Lemma 1, we conclude
$\bar{\xi}^{N}\Rightarrow\xi=F^{-1}\left(\xi^{\prime}\right)$,
$\bar{\beta}^{N}\Rightarrow\beta=F^{-1}\left(\beta^{\prime}\right)$. ∎

######  Lemma 1.

  1. 1.

The functions $F$ and $F^{-1}$, restricted to $\mathbb{D}_{{\cal
M}}\left(\left[0,T\right]\right),T>0$, are continuous.

  2. 2.

The function $F$, restricted to $\mathbb{D}_{{\cal
M}}\left(\left[0,T\right]\right),T>0$, sends elements of $\mathbb{C}_{{\cal
M}}$ to $\mathbb{C}_{{\cal M}}$.

###### Proof.

  1. 1.

Denote by $B\left(\nu,\varepsilon\right)$ the open ball in $\mathbb{D}_{{\cal
M}}\left(\left[0,T\right]\right)$ with radius $\varepsilon$, centered around
$\nu$. We show that $F\left(B\left(\nu,\varepsilon\right)\right)\subset
B\left(\nu^{\prime},e^{LT}\varepsilon\right)$,
$\nu^{\prime}=F\left(\nu\right)$. Take any $\lambda\in
B\left(\nu,\varepsilon\right)$ and denote
$\lambda^{\prime}=F\left(\lambda\right)$, then there exists a strictly
increasing mapping $\gamma:\left[0,T\right]\to\left[0,T\right]$, with
$\gamma\left(0\right)=0$, $\gamma\left(T\right)=T$ and
$\sup_{t\in\left[0,T\right]}\left|\gamma\left(t\right)-t\right|<\varepsilon$,
such that for any $t\in\left[0,T\right]$ and any $x$

$\displaystyle\lambda_{t}\left(-\infty,x-\varepsilon\right]-\varepsilon\leq\nu_{\gamma\left(t\right)}\left(-\infty,x\right]\leq\lambda_{t}\left(-\infty,x+\varepsilon\right]+\varepsilon,$

which is just
$\sup_{t\in\left[0,T\right]}d_{\cal{L}}\left(\nu_{\gamma\left(t\right)},\lambda_{t}\right)<\varepsilon$.

Making yet another use of Assumption 1, Theorem 6 in [5] yields

$\displaystyle
x^{\prime}\left(x,t\right)-x^{\prime}\left(x-\varepsilon,t\right)=g_{\left(x,t\right)}\left(0\right)-g_{\left(x-\varepsilon,t\right)}\left(0\right)\leq\varepsilon
e^{Lt}\leq\varepsilon e^{LT},$ $\displaystyle
x^{\prime}\left(x+\varepsilon,t\right)-x^{\prime}\left(x,t\right)=g_{\left(x+\varepsilon,t\right)}\left(0\right)-g_{\left(x,t\right)}\left(0\right)\leq\varepsilon
e^{Lt}\leq\varepsilon e^{LT}.$

Using the above inequalities, for any $t^{\prime}\in\left[0,T\right]$ and $x$,

$\displaystyle\nu^{\prime}_{\gamma\left(t\right)}\left[0,x^{\prime}\right]=\nu_{\gamma\left(t\right)}\left(-\infty,x\right]\leq\lambda_{t}\left(-\infty,x+\varepsilon\right]+\varepsilon=\lambda^{\prime}_{t}\left[0,x^{\prime}\left(x+\varepsilon,t\right)\right]+\varepsilon<\lambda^{\prime}_{t}\left[0,x^{\prime}+\varepsilon
e^{LT}\right]+\varepsilon e^{LT},$
$\displaystyle\nu^{\prime}_{\gamma\left(t\right)}\left[0,x^{\prime}\right]=\nu_{\gamma\left(t\right)}\left(-\infty,x\right]\geq\lambda_{t}\left(-\infty,x-\varepsilon\right]-\varepsilon=\lambda^{\prime}_{t}\left[0,x^{\prime}\left(x-\varepsilon,t\right)\right]-\varepsilon>\lambda^{\prime}_{t}\left[0,x^{\prime}-\varepsilon
e^{LT}\right]-\varepsilon e^{LT}.$

Hence,
$\sup_{t^{\prime}\in\left[0,T\right]}d_{\cal{L}}\left(\nu^{\prime}_{\gamma\left(t\right)},\lambda^{\prime}_{t}\right)<\varepsilon
e^{LT}$.

Continuity for $F^{-1}$ follows by similar arguments.

  2. 2.

Just as in the first part of the Lemma, if for all $t>0$ and $x$

$\displaystyle\nu_{t+h}\left[0,x-\varepsilon\right]-\varepsilon\leq\nu_{t}\left[0,x\right]\leq\nu_{t+h}\left[0,x^{\prime}+\varepsilon\right]+\varepsilon,$

then for all $t>0$ and $x^{\prime}>0$

$\displaystyle\nu^{\prime}_{t+h}\left[0,x^{\prime}-\varepsilon
e^{LT}\right]-\varepsilon
e^{LT}\leq\nu^{\prime}_{t}\left[0,x^{\prime}\right]\leq\nu^{\prime}_{t+h}\left[0,x^{\prime}+\varepsilon
e^{LT}\right]+\varepsilon e^{LT}.$

This means that for any $\varepsilon>0$, choosing $h$ small enough such that
$d_{\cal{L}}\left(\nu_{t+h},\nu_{t}\right)<\delta$, $\delta=\varepsilon
e^{-LT}$ (such $h$ exists as we assume $\nu\in\mathbb{C}_{{\cal M}}$), implies
$d_{\cal{L}}\left(\nu^{\prime}_{t+h},\nu^{\prime}_{t}\right)<\varepsilon$.

∎

##  4 Examples

In this section we provide insight through simplifications and examples. The
examples assume some workload arrival distribution of a fluid system, and
provide explicit solutions. Recall that for a pair of data
$\left(\alpha,\mu\right)\in\mathbb{C}_{{\cal
M}_{0}}\times\mathbb{C}^{\uparrow}$, the fluid solution is obtained by first
applying the appropriate change of coordinates
$x^{\prime}=g_{\left(x,t\right)}\left(0\right)$ and then finding the measure
valued process in $\mathbb{C}_{{\cal M}_{0}}^{\uparrow}$,
$\alpha^{\prime}=F\left(\alpha\right)$ (defined by
$\alpha^{\prime}_{t}\left[0,x^{\prime}\right]=\alpha_{t}\left(-\infty,x\right]$).
Then one applies the MVSM
$\left(\xi^{\prime},\beta^{\prime},\iota\right)=\Theta\left(\alpha^{\prime},\mu\right)$
and finally $\xi=F^{-1}\left(\xi^{\prime}\right)$,
$\beta=F^{-1}\left(\beta^{\prime}\right)$. The entire procedure is summarized
in the formulation of Theorem 1 through Equations (8) and (9),

$\displaystyle\beta_{t}\left(x,\infty\right)+\iota\left(t\right)=-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,g_{\left(x,t\right)}\left(0\right)\right)-\mu\left(s\right)\right)\land
0\right\\},$
$\displaystyle\xi_{t}\left(-\infty,x\right]=\Xi\left(t,g_{\left(x,t\right)}\left(0\right)\right)-\mu\left(t\right)-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,g_{\left(x,t\right)}\left(0\right)\right)-\mu\left(s\right)\right)\land
0\right\\},$

with
$\Xi\left(t,x\right)=\alpha_{t}\left(-\infty,g_{\left(x,0\right)}\left(t\right)\right]$.
In many cases, it is more natural to describe the arrival process through the
instantaneous arrival distribution rather than through the cumulative arrival
process $\alpha$. The instantaneous arrival distribution describes the
distribution of either the job sizes or the workload (each can be derived from
the other) of the arriving work at each instant. Therefore, it is useful to
have a relation connecting $\alpha$ with this distribution. Let $\pi_{t}$ be
the instantaneous workload arrival distribution at time $t$, then
$\alpha_{t}\left(-\infty,x\right]=\int_{0}^{t}\pi_{s}\left[0,g_{\left(x,t\right)}\left(s\right)\right]ds$.
All the following examples are of this form, where various instantaneous
workload arrival distributions are considered. First we present a
simplification of the formula for $\xi$ and $\beta$ under certain conditions.
There appear four examples afterwards. The first three examples are of linear
aging and the last is of exponential aging. In the first example, the
instantaneous workload arrival distribution is uniform over the interval
$[0,1]$, in the second example it is uniform over a time-varying interval, and
in the two last examples it is Pareto distributed.

### A simplification

Assume for simplicity that the arrival rate is larger than the service rate;
in this case, $\iota=0$. We then may guess the following solution on the prime
plane:

$\displaystyle\begin{cases}\beta^{\prime}_{t}\left[0,x^{\prime}\right]=\alpha^{\prime}_{t}\left[0,x^{\prime}\right]\land\mu\left(t\right),\\\
\xi^{\prime}_{t}\left[0,x^{\prime}\right]=\alpha^{\prime}_{t}\left[0,x^{\prime}\right]-\beta^{\prime}_{t}\left[0,x^{\prime}\right]=\left[\alpha^{\prime}_{t}\left[0,x^{\prime}\right]-\mu\left(t\right)\right]^{+}.\end{cases}$
(13)

Note that this is not always a valid guess, as it is not clear that

$\displaystyle\beta^{\prime}_{t}\left(x^{\prime},\infty\right)=\mu\left(t\right)-\beta^{\prime}_{t}\left[0,x^{\prime}\right]=\left[\mu\left(t\right)-\alpha^{\prime}_{t}\left[0,x^{\prime}\right]\right]^{+}$

is non-decreasing in $t$. However, it is true in many cases, e.g. when the job
size distribution, and the arrival and service rates are time invariant. To
verify that this guess is the true solution whenever
$\beta^{\prime}_{t}\left(x^{\prime},\infty\right)$ is non-decreasing, observe
that either $\xi^{\prime}_{t}\left[0,x^{\prime}\right]$ or
$\beta^{\prime}_{t}\left(x^{\prime},\infty\right)$ is zero, Hence,
$\int\xi^{\prime}_{t}\left[0,x^{\prime}\right]d\beta^{\prime}_{t}\left(x^{\prime},\infty\right)=0$,
and by definition $\beta^{\prime}_{t}\left[0,\infty\right)=\mu\left(t\right)$
and
$\xi^{\prime}\left[0,x^{\prime}\right]=\alpha^{\prime}\left[0,x^{\prime}\right]-\beta^{\prime}\left[0,x^{\prime}\right]$.
Thus, this guess is the unique solution to the MVSP with data
$\left(\alpha^{\prime},\mu\right)$.

The interpretation of the guess (13) is that there is a process
$x^{*}\left(t\right)=\inf\\{x:\alpha^{\prime}_{t}\left[0,x\right]\geq\mu\left(t\right)\\}$
such that the entire mass below $x^{*}\left(t\right)$ was served by time $t$
and the entire mass above it is in the queue at time $t$. The guess (13) is
equal to the fluid solution if $t\mapsto x^{*}\left(t\right)$ is non-
decreasing. Note that the aging ”pushes” $x^{*}\left(t\right)$ to the right,
thus does not invalidates the guess.

This simplification is used in the first example in this section to illustrate
its usefulness. We do not use this simplification in the other examples.

### Linear aging with uniformly distributed workload

We begin by analyzing the case of uniformly distributed workload, specifically
on $\left[0,x\right]$, with constant arrival rate. This corresponds for
$\pi_{s}\left[0,x\right]=1\land\left(x\lor 0\right)$. The aging rule in this
example is chosen to be the linear aging rule. This is a rather simple example
where closed form solutions can be found. For linear aging, the cumulative
workload arrival process is derived from $\pi$ by
$\alpha_{t}\left(-\infty,x\right]=\int_{0}^{t}\pi_{s}\left[0,x+t-s\right]ds$.
We can compute

$\displaystyle\alpha_{t}\left(-\infty,x\right]$
$\displaystyle=\begin{cases}t&\text{ if }x>1,\\\
t+x-\frac{x^{2}}{2}-\frac{1}{2}&\text{ if }0<x<1\text{ and }x>1-t,\\\
xt+\frac{t^{2}}{2}&\text{ if }0<x<1\text{ and }x<1-t,\\\
x+t-\frac{1}{2}&\text{ if }x<0\text{ and }x>1-t,\\\ 0&\text{ if }x<0\text{ and
}x<-t,\\\ \frac{\left(x+t\right)^{2}}{2}&\text{ if }x<0\text{ and
}-t<x<1-t,\\\ \end{cases}$

and, consequently, compute

$\displaystyle\alpha^{\prime}_{t}\left[0,x^{\prime}\right]$
$\displaystyle=\begin{cases}t&\text{ if }x^{\prime}>1+t,\\\
x^{\prime}-\frac{\left(x^{\prime}-t\right)^{2}}{2}-\frac{1}{2}&\text{ if
}t<x^{\prime}<1+t\text{ and }x^{\prime}>1,\\\
x^{\prime}t-\frac{t^{2}}{2}&\text{ if }t<x^{\prime}<t+1\text{ and
}x^{\prime}<1,\\\ x^{\prime}-\frac{1}{2}&\text{ if }x^{\prime}<t\text{ and
}x^{\prime}>1,\\\ 0&\text{ if }x^{\prime}<t\text{ and }x^{\prime}<0,\\\
\frac{x^{\prime 2}}{2}&\text{ if }x^{\prime}<t\text{ and }0<x^{\prime}<1.\\\
\end{cases}$

If we choose for example $\mu\left(t\right)=t/2$, we can obtain
$x^{*}\left(t\right)=\left(t+1\right)/2$, which is increasing with $t$. Hence,
the guess (13) is valid. To simplify the expressions of $\xi^{\prime}$ and
$\beta^{\prime}$, we consider times $t>1$. Then the solution is given by

$\displaystyle\beta^{\prime}_{t}\left[0,x^{\prime}\right]$
$\displaystyle=\begin{cases}\frac{t}{2}&\text{ if
}x^{\prime}>\frac{1+t}{2},\\\ x^{\prime}-\frac{1}{2}&\text{ if
}1<x^{\prime}<\frac{t+1}{2},\\\ 0&\text{ if }x^{\prime}<0,\\\ \frac{x^{\prime
2}}{2}&\text{ if }0<x^{\prime}<1,\\\ \end{cases}$
$\displaystyle\xi^{\prime}_{t}\left[0,x^{\prime}\right]$
$\displaystyle=\begin{cases}\frac{t}{2}&\text{ if }x^{\prime}>1+t,\\\
x^{\prime}-\frac{\left(x^{\prime}-t\right)^{2}}{2}-\frac{1}{2}-\frac{t}{2}&\text{
if }t<x^{\prime}<1+t\text{ and }x^{\prime}>1,\\\
x^{\prime}-\frac{1+t}{2}&\text{ if }t>x^{\prime}>\frac{t+1}{2},\\\ 0&\text{ if
}x^{\prime}<\frac{t+1}{2}.\\\ \end{cases}$

For the sake of completeness, we give the explicit expression for
$\xi_{t}\left(-\infty,x\right]$,

$\displaystyle\xi_{t}\left[0,x\right]$
$\displaystyle=\begin{cases}\frac{t}{2}&\text{ if }x>1,\\\
x+t-\frac{x^{2}}{2}-\frac{1}{2}-\frac{t}{2}&\text{ if }0<x<1\text{ and
}x>1-t,\\\ x+\frac{t-1}{2}&\text{ if }0>x>\frac{1-t}{2},\\\ 0&\text{ if
}x<\frac{1-t}{2}.\\\ \end{cases}$

Figure 2(2(a)) shows the evolution of $\xi_{t}\left(-\infty,x\right]$ with
time. In this figure, and in all the other as well, the system is assumes to
be empty at time $t=0$.

(a) $\xi_{t}\left(-\infty,x\right]$ when the aging is linear and the workload
arrival distribution is uniform over the interval $[0,1]$.

(b) $\xi_{t}\left(-\infty,x\right]$ when the aging is linear and the workload
arrival distribution is uniform with time-varying support.

(c) $\xi_{t}\left(-\infty,x\right]$ when the aging is linear and the workload
arrival distribution is Pareto with parameter $\eta=1.2$.

(d) $\xi_{t}\left(-\infty,x\right]$ when the aging is exponential and the
workload arrival distribution is Pareto with parameters $\eta=1.2$ and
$\lambda=0.1$.

Figure 2: Examples of $\xi_{t}\left(-\infty,x\right]$ for different aging
rules and different workload arrival distribution.

### Time varying arrival distribution

In many cases it is possible to obtain an expression for
$\alpha_{t}\left(-\infty,x\right]$ when the instantaneous workload arrival
distribution is periodic. This is exactly the setting in the following
example. In this example, the instantaneous workload distribution is again
uniform, but its support is now a periodically-time-varying interval
$\left[0,a(t)\right]$. This corresponds to
$\pi_{t}\left[0,x\right]=a(s)\land\left(x\lor 0\right)$. Our aging rule is
still linear. We solve for a specific choice of $a(t)$, a triangular wave- a
piecewise linear periodic function as illustrated in Figure 3.

$a(t)$$\frac{1}{2}$$1$$0$$1$$2$$3$$4$$5$$t$ Figure 3: Time-varying upper
boundary of the workload distribution support.

To describe the solution, we define the following.

$\displaystyle N\left(x,t\right)$
$\displaystyle=2\left\lfloor\frac{x+t}{2}\right\rfloor,$ $\displaystyle
A_{1}\left(x,t\right)$ $\displaystyle=\frac{1+\left\lfloor
x+t\right\rfloor}{2},$ $\displaystyle s_{1}^{*}\left(x,t\right)$
$\displaystyle=2\left(x+t-A_{1}\left(x,t\right)\right),$ $\displaystyle
A_{2}\left(x,t\right)$
$\displaystyle=\frac{1}{2}-\left\lfloor\frac{x+t}{2}\right\rfloor,$
$\displaystyle s_{2}^{*}\left(x,t\right)$
$\displaystyle=\frac{2\left(x+t-A_{2}\left(x,t\right)\right)}{3}.$

To ease the notation, the dependency of $x$ and $t$ is omitted, and we simply
write $N,A_{i},s_{i}^{*},i=1,2$. Let $D_{1}=\\{\left(x,t\right):N\leq
x+t<N+1/2\\}$ and $D_{2}=\\{\left(x,t\right):N+1/2\leq x+t<N+2\\}$. Solving
the integral $\int_{0}^{t}\pi_{s}\left[0,x+t-s\right]ds$ gives

$\displaystyle\alpha_{t}\left(-\infty,x\right]=$
$\displaystyle\begin{cases}\frac{3}{4}\left\lfloor
t\right\rfloor+t-\left\lfloor t\right\rfloor-\frac{\left(t-\left\lfloor
t\right\rfloor\right)^{2}}{4}&\text{ if }t\leq s^{*}\text{ and }\left\lfloor
t\right\rfloor\text{ is odd}\\\ \frac{3}{4}\left\lfloor
t\right\rfloor+\frac{t-\left\lfloor
t\right\rfloor}{2}+\frac{\left(t-\left\lfloor
t\right\rfloor\right)^{2}}{4}&\text{ if }t\leq s^{*}\text{ and }\left\lfloor
t\right\rfloor\text{ is even}\\\ \frac{3}{4}\left\lfloor
s_{1}^{*}\right\rfloor+s_{1}^{*}-\left\lfloor
s_{1}^{*}\right\rfloor-\frac{\left(s_{1}^{*}-\left\lfloor
s_{1}^{*}\right\rfloor\right)^{2}}{4}+\left(x+t\right)\left(t-s_{1}^{*}\right)-\frac{t^{2}-s_{1}^{*2}}{2}&\text{
if }0\leq s_{1}^{*}<t\leq x+t\text{ and }D_{1}\\\ \frac{3}{4}\left\lfloor
s_{2}^{*}\right\rfloor+\frac{s_{2}^{*}-\left\lfloor
s_{2}^{*}\right\rfloor}{2}+\frac{\left(s_{2}^{*}-\left\lfloor
s_{2}^{*}\right\rfloor\right)^{2}}{4}+\left(x+t\right)\left(t-s_{2}^{*}\right)-\frac{t^{2}-s_{2}^{*2}}{2}&\text{
if }0\leq s_{2}^{*}<t\leq x+t\text{ and }D_{2}\\\ xt+\frac{t^{2}}{2}&\text{ if
}s^{*}<0<t<x+t\\\ \frac{\left(x+t\right)^{2}}{2}&\text{ if }s^{*}<0<x+t<t\\\
\frac{3}{4}\left\lfloor s_{1}^{*}\right\rfloor+s_{1}^{*}-\left\lfloor
s_{1}^{*}\right\rfloor-\frac{\left(s_{1}^{*}-\left\lfloor
s_{1}^{*}\right\rfloor\right)^{2}}{4}+\left(x+t\right)\left(t+x-s_{1}^{*}\right)-\frac{\left(t+x\right)^{2}-s_{1}^{*2}}{2}&\text{
if }0<s_{1}^{*}<x+t<t\text{ and }D_{1}\\\ \frac{3}{4}\left\lfloor
s_{2}^{*}\right\rfloor+\frac{s_{2}^{*}-\left\lfloor
s_{2}^{*}\right\rfloor}{2}+\frac{\left(s_{2}^{*}-\left\lfloor
s_{2}^{*}\right\rfloor\right)^{2}}{4}+\left(x+t\right)\left(t+x-s_{2}^{*}\right)-\frac{\left(t+x\right)^{2}-s_{2}^{*2}}{2}&\text{
if }0<s_{2}^{*}<x+t<t\text{ and }D_{2}\\\ 0&\text{ if }x+t<0.\end{cases}$

In the above, the condition $s^{*}>t$ should be interpreted as either
$s_{1}^{*}>t$ and $D_{1}$, or $s_{2}^{*}>t$ and $D_{2}$; and likewise for
$s^{*}<0$.

It is now possible to find $\alpha^{\prime}$ and $x^{*}(t)$, though obtaining
$\xi^{\prime}$, $\beta^{\prime}$ and $\iota^{\prime}$ is rather tedious even
for such $\mu(t)$ for which the guess (13) is valid, and we do not continue
with that line. The general solution, as mentioned at the beginning of the
section, takes the form

$\displaystyle\xi_{t}\left(-\infty,x\right]=\Xi\left(t,x+t\right)-\mu\left(t\right)-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,x+t\right)-\mu\left(s\right)\right)\land
0\right\\},$

with $\Xi\left(t,x\right)=\alpha_{t}\left(-\infty,x-t\right]$. Figure 2(2(b))
shows the evolution of $\xi_{t}\left(-\infty,x\right]$ with time. Note the
difference between 2(2(a)) and 2(2(b)). The fact that $\pi_{s}$ is periodic is
reflected in the wiggliness of the graph.

### Pareto distributed workload

The Pareto distribution is a heavy tailed distribution, used often in queueing
theory to model internet packet inter-arrival times ([13]). This distribution
is of a special interest in this section because we can find explicit
expressions for $\alpha$ when the workload is Pareto distributed, both for
linear and for exponential aging. We begin with the linear aging setting, and
compare the results later with the exponential aging setting. For the Pareto
distribution of the arriving workload we choose the parameters 1 and $\eta$,
which correspond to
$\pi_{s}\left[0,x\right]=\left(1-x^{-\eta}\right)\mathbbm{1}_{\left\\{x\geq
1\right\\}}$. In this case we can calculate $\alpha$ and obtain

$\displaystyle\alpha_{t}\left[0,x\right]$
$\displaystyle=\int_{0}^{t}\pi_{s}\left[0,x+t-s\right]ds=\int_{0}^{t}\left(1-\left(x+t-s\right)^{-\eta}\right)\mathbbm{1}_{\left\\{x+t-s\geq
1\right\\}}ds$ $\displaystyle=\begin{cases}0&x<1-t,\\\
x+t-1+\frac{\left(x+t\right)^{1-\eta}-1}{\eta}&1-t\leq x\leq 1,\\\
t+\frac{\left(x+t\right)^{1-\eta}-x^{1-\eta}}{\eta}&1<x.\end{cases}$

Now one can then find

$\displaystyle\alpha^{\prime}_{t}\left[0,x^{\prime}\right]$
$\displaystyle=\begin{cases}0&x^{\prime}<1,\\\ x^{\prime}-1+\frac{x^{\prime
1-\eta}-1}{\eta}&1\leq x^{\prime}\leq 1+t,\\\ t+\frac{x^{\prime
1-\eta}-\left(x^{\prime}-t\right)^{1-\eta}}{\eta}&1+t<x^{\prime}.\end{cases}$

The solution takes again the form

$\displaystyle\xi_{t}\left(-\infty,x\right]=\Xi\left(t,x+t\right)-\mu\left(t\right)-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,x+t\right)-\mu\left(s\right)\right)\land
0\right\\},$

with $\Xi\left(t,x\right)=\alpha_{t}\left(-\infty,x-t\right]$.

Figure 2(2(c)) shows the evolution of $\xi_{t}\left(-\infty,x\right]$ with
time, when we used $\eta=1.2$. Figure 4 shows the influence of the Pareto
parameter $\eta$ on the shape of the graphs.

Figure 4: $\xi_{t}\left(-\infty,x\right]$ when the aging is linear and the
workload arrival distribution is Pareto, after 5 time units.

### Exponential aging

We continue with an example in a setting with exponential aging. For this
example we choose again the Pareto distribution with parameters $1$ and $\eta$
as the instantaneous workload arrival distribution corresponding to
$\pi_{s}\left[0,x\right]=\left(1-x^{-\eta}\right)\mathbbm{1}_{\left\\{x\geq
1\right\\}}$. We calculate

$\displaystyle\alpha_{t}\left[0,x\right]=\int_{0}^{t}\pi_{s}\left[0,xe^{-\lambda\left(s-t\right)}\right]ds=\int_{0}^{t+\lambda^{-1}\log\left(x\land
1\right)}\left(1-x^{-\eta}e^{\lambda\eta\left(s-t\right)}\right)ds$
$\displaystyle\hskip 256.0748pt=\begin{cases}0&x\leq e^{-\lambda t}\\\
t+\frac{1}{\lambda}\log(x)-\frac{x^{-\eta}}{\lambda\eta}\left(x^{\eta}-e^{-\lambda\eta
t}\right)&e^{-\lambda t}<x<1,\\\
t-\frac{x^{-\eta}}{\lambda\eta}\left(1-e^{-\lambda\eta t}\right)&x\geq
1,\end{cases}$
$\displaystyle\alpha^{\prime}_{t}\left[0,x^{\prime}\right]=\alpha_{t}\left[0,x^{\prime}e^{-\lambda
t}\right]=\begin{cases}0&x^{\prime}\leq 1,\\\
\frac{1}{\lambda}\log(x^{\prime})-\frac{1-x^{\prime-\eta}}{\lambda\eta}&1<x^{\prime}<e^{\lambda
t},\\\ t-\frac{x^{\prime-\eta}}{\lambda\eta}\left(e^{\lambda\eta
t}-1\right)&x^{\prime}\geq e^{\lambda t}.\end{cases}$

The solution takes the form

$\displaystyle\xi_{t}\left(-\infty,x\right]=\Xi\left(t,xe^{\lambda
t}\right)-\mu\left(t\right)-\inf_{s\in\left[0,t\right]}\left\\{\left(\Xi\left(s,xe^{\lambda
t}\right)-\mu\left(s\right)\right)\land 0\right\\},$

with $\Xi\left(t,x\right)=\alpha_{t}\left(-\infty,xe^{-\lambda t}\right]$.

Figure 2(2(d)) shows the evolution of $\xi_{t}\left(-\infty,x\right]$ with
time for this example with the choice $\mu(t)=t/2$. It is interesting to
compare 2(2(c)) with 2(2(d)), both sharing the same workload arrival
distribution while differing in their aging rules.

## References

  * [1] R. Atar, A. Biswas, H. Kaspi, and K. Ramanan.  A Skorokhod map on measure-valued paths with applications to priority queues.  Ann. Appl. Probab., 28(1):418–481, 02 2018\.
  * [2] M. Bach, A. . T, AT, and T. I. S. (Firm).  The Design of the UNIX Operating System.  Prentice-Hall international editions. Prentice-Hall, 1986.
  * [3] N. Bansal and M. Harchol-Balter.  Analysis of SRPT scheduling: investigating unfairness.  In Proceedings of the Joint International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS 2001, Cambridge, MA, USA, June 16-20, 2011), pages 279–290, United States, 2001. Association for Computing Machinery, Inc.
  * [4] H. S. Behera, B. K. Swain, A. K. Parida, and G. Sahu.  A New Proposed Round Robin with Highest Response Ratio Next ( rrhrrn ) Scheduling Algorithm for Soft Real Time Systems.  2012\.
  * [5] G. Birkhoff and G. Rota.  Ordinary Differential Equations.  Introductions to higher mathematics. Wiley, 1989.
  * [6] M. Dell’Amico, D. Carra, M. Pastorelli, and P. Michiardi.  Revisiting Size-Based Scheduling with Estimated Job Sizes.  In 2014 IEEE 22nd International Symposium on Modelling, Analysis Simulation of Computer and Telecommunication Systems, pages 411–420, 2014.
  * [7] D. G. Down, H. C. Gromoll, and A. L. Puha.  Fluid Limits for Shortest Remaining Processing Time Queues.  Mathematics of Operations Research, 34(4):880–911, 2009.
  * [8] D. Feitelson.  Notes on Operating Systems.  The Hebrew University of Jerusalem, 2011.
  * [9] H. C. Gromoll, u. Kruk, and A. L. Puha.  Diffusion Limits for Shortest Remaining Processing Time Queues.  Stochastic Systems, 1(1):1–16, 2011.
  * [10] M. Gromoll H.C., Keutel.  Invariance of fluid limits for the shortest remaining processing time and shortest job first policies.  Queueing Syst, 70:145–164, 02 2012.
  * [11] M. Harchol-Balter, K. Sigman, and A. Wierman.  Asymptotic Convergence of Scheduling Policies with Respect to Slowdown.  Performance Evaluation, 49, 07 2003.
  * [12] J. D. C. Little.  A Proof for the Queuing Formula: L = $\lambda$w.  Operations Research, 9(3):383–387, 1961.
  * [13] S. Mirtchev and R. Goleva.  Evaluation of Pareto/D/1/K queue by simulation.  01 2008.
  * [14] M. Nuyens and B. Zwart.  A large-deviations analysis of the G/G/1 SRPT queue.  Queueing Systems: Theory and Applications, 54(2):85–97, 2006.
  * [15] A. L. Puha.  Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling.  Ann. Appl. Probab., 25(6):3381–3404, 12 2015\.
  * [16] L. Schrage.  Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline.  Operations Research, 16(3):687–690, 1968.
  * [17] L. E. Schrage and L. W. Miller.  The Queue M / G /1 with the Shortest Remaining Processing Time Discipline.  Operations Research, 14(4):670–684, 1966.
  * [18] A. Silberschatz, P. Galvin, and G. Gagne.  Operating System Concepts.  Windows XP update. Wiley, 2005.
  * [19] D. R. Smith.  Technical Note—A New Proof of the Optimality of the Shortest Remaining Processing Time Discipline.  Operations Research, 26(1):197–199, 1978.