1. INTRODUCTION
We consider a perishable inventory system (PIS) in which the arrival
times of items to be stored and those of the demands are independent
Poisson processes. The purpose of this article is to study the effect of
certain control policies that prevent possible serious consequences of
periods of emptiness.
When uncontrolled, the PIS in question works as follows. Fresh stock
arrives at the system according to a Poisson process with rate λ.
Without loss of generality, we assume that the lifetime of each item is
one time unit. If an item has not been consumed by demand before its
expiration date, it is discarded. The demand arrival times form a Poisson
process with rate μ. Demands are satisfied on a first in–first
out (FIFO) basis (i.e., oldest items are issued first). A demand that
arrives when the system is empty is lost. This basic model as well as
several extensions have been studied in previous articles (see, e.g.,
[8,16,17,21,22,23,24]), in which also various applications to
real-life systems such as blood banks and food storage places are
exhibited. Examples of perishable products include blood portions,
packaged chemicals and pharmaceuticals, fresh foods, and photographic
film.
To assess the efficiency of this PIS, one has to take into account the
number of items on the shelf (causing holding costs), the losses due to
outdatings of unused items, and the rate of demands that arrive while the
system is empty and thus have to leave unsatisfied. There are intuitively
obvious trade-offs among these three random quantities; for example, an
on-average well-filled shelf will usually entail a large number of
outdatings and a small number of unsatisfied demands. To balance the cost,
various types of intervention in the PIS are possible. Bang-bang policies
in the case that the demand and the arrival process can be controlled have
been studied in [19,20]. In this article, we focus on avoiding the
undesired consequences of unsatisfied demands under fixed model
parameters.
In particular, in blood banks the unavailability of items (blood
portions) when they are demanded can cause serious, possibly disastrous,
consequences. The first model we propose excludes the possibility of
unsatisfied demands by introducing a second source of fresh items that is
completely reliable and delivers without delay. This second source is
always available in the sense that a batch of items from it arrives
immediately whenever the controller places an order. To rule out
unsatisfied demands, n0 items are ordered whenever the
PIS becomes empty. Thus, after an instantaneous emptiness, the shelf is
refilled with n0 items. We call this model the
never-empty PIS.
The selection of n0 (if there is a choice)
depends, of course, on the structure of the ordering cost. Suppose that
the price of a special order of n0 items is of the
form D + dn0. Intuitively, a high value of
the setup cost D will be an incentive for the controller to place
special orders for a large number of items, but one has also to take into
account that a large order size n0 will have the
undesirable consequence of causing many outdatings, indicating an
inefficiently run PIS. On the other hand, if D is small compared
to d, the price per item in the delivery, n0
will probably be chosen small; in the extreme case D = 0, there
is no point in ordering more than one item at a time. Since a change of
any of the underlying parameters
(λ,μ,n0,D,d) gives rise to
contrary cost effects, no easy monotonicity properties can be expected. In
the case n0 = 1, the key stochastic process in our
approach will be seen to be Markovian; this property is, however, lost for
n0 > 1, making the analysis more complicated (and
more interesting).
In our second model, there is no additional ordering option by
outsourcing. To avoid the most adverse effects of unavailability, the
demands are classified into different categories of urgency. An incoming
demand will then be satisfied or not according to its category and the
current state of the system. We will analyze a particular PIS with
urgency classification, in which there are two categories of demands:
Those of type 1 will be satisfied whenever the shelf is not empty, whereas
those of type 2 will only be satisfied if there are at least
m0 items on the shelf or the residual lifetime of the
oldest one is at most t0 (with prespecified
m0 and t0).
In general, inventory models for nondurable goods can be classified
into two categories:
In Model 1, we try to combine replenishment by random arrivals (2b)
with an ordering option from an external source (2a) so as to avoid losses
due to unsatisfied demands. Model 2 pursues the same goal by satisfying
less urgent demands only if the inventory is well filled or the oldest
item is close to outdating. The article is organized as follows. Model 1
is analyzed in detail in Section 2. We introduce the basic so-called
virtual outdating time (VOT) process and derive its steady-state
distribution. It turns out that all relevant cost functionals can be
expressed in terms of this distribution. The VOT process is regenerative
but not Markovian; so, for its steady-state analysis, we have to exploit a
certain duality, leading to a Markov process for which classical
techniques can be used. A similar approach yields the cost functionals for
a modification of Model 1, including lead times. In Section 3, we study
the model with urgency classification.
2. MODEL 1: THE NEVER-EMPTY PIS
2.1. The Virtual Outdating Process
Demands arrive in the system according to a Poisson process of rate
μ. Items enter the PIS in two kinds: regular single arrivals at
Poisson times of rate λ (independent of the demand process) and
special arrivals that are ordered in batches of fixed size
n0 and arrive immediately every time the shelf becomes
empty (either because the last item on the shelf is taken away by a demand
or its lifetime of one time unit expires).
Let A(t) be the age of the oldest item (i.e. the
time it has spent in the system at time t). Note that there are
exactly n0 oldest items just after a special order;
their ages then start increasing in parallel and they are taken away
successively when new demands arrive. The ones that are still in the
system after one time unit (if any) are then outdated simultaneously. Let
A = {A(t)|t ≥ 0}. The key
process in our analysis is the VOT process W =
{W(t) : t ≥ 0} defined by
W(t) = 1 − A(t). Clearly,
W(t) can be interpreted as the time from t
until the next outdating if no demands arrive after t.
The VOT process W is regenerative (composed of independent
and identically distributed (i.i.d.) cycles) but non-Markovian. If
n0 = 1, W is a Markov process, but this
property does not hold if n0 > 1. A new cycle
starts whenever W reaches its maximum value 1. If the system has
just been emptied at some time t, then n0 new
items immediately start their shelf life and W(t) = 1.
Let us describe the stochastic evolution of W during a cycle.
First, W decreases linearly at rate 1 until these
n0 items have all been taken away by demands or their
common lifetime expires after one time unit. As the interarrival times of
demands are exp(μ), the first jump of W occurs after
min[E(μ,n0),1] time units,
where E(μ,n0) is an Erlang-distributed
random variable with parameters μ and n0. Before
this jump, new items may have arrived according to a Poisson process of
rate λ. Let Eλ be the time until the first
regular item arrival in the cycle. If Eλ <
min[E(μ,n0),1], this new
regular item becomes the oldest one and W jumps up by
Eλ; otherwise, the system has been emptied after
min[E(μ,n0),1] time units and a
new special batch arrival starts the next cycle. In the first case, the
cycle goes on and the next jump occurs at the arrival of the next demand
(after an exp(μ)-distributed time) or when 0 is hit, whichever comes
first, and the position after the jump at that time, say s, is
equal to min[W(s) +
Eλ′,1], where
Eλ′ is exp(λ) distributed. If this
latter minimum is 1, a new cycle starts; otherwise, the next jump occurs
after another exp(μ)-distributed time or when 0 is hit, and so on. All
of the random variables mentioned in this description are independent.
A typical sample path of W for n0 = 4 is
depicted in Figure 1. The following notation is
used:
A typical sample path of the VOT process in Model 1 with
n0 = 4.
The first cycle shown in Figure 1 starts
with the arrival of a special order in an empty system at time
S1. The first three special items are taken away by
demands at times A1, A2, and
A3. At time B1, the fourth special
item leaves. The regular item that arrived at time D1
becomes the only item on the shelf; it is outdated at time
O1. A second regular item arrived before, at time
D2; this item satisfies a demand at time
S2 and the system becomes empty. Thus, a new cycle
starts with the instantaneous arrival of four special items. Two of them
are taken away by demands and the other two are outdated at time
O2 = S3. Since there were no
Poisson item arrivals in the meantime, a new cycle begins.
A little reflection shows that W has the same distribution as
the content process of a special modified finite dam, which can be defined
as follows:
a. The dam has capacity 1 (overflows being immediately lost)
and releases water at rate 1.
b. The dry periods are deleted and the wet ones are glued
together.
c. The inputs are exp(λ) distributed.
d. Whenever the dam is completely filled, the time until the
next input is Erlang distributed with parameters μ and
n0, truncated at 1, whereas the subsequent
interarrival times between inputs are exp(μ)
distributed.
The long-run cost of operating a never-empty PIS of the above type
will depend on the following characteristics:
i. the number of items in the system in steady state (causing
holding costs);
ii. the rate λ* of outdatings;
iii. the rate μ* of special orders.
For a long-run average cost analysis and optimization, one can, for
example, try to minimize a linear combination
where a, b, and c are positive constants
and K is a random variable indicating the number of items in the
system in steady state. Decision variables can be the arrival rates λ
and μ within certain ranges (if they are controllable) and the batch
size n0 of the special orders. For example, if the
ordering cost per batch is of the form D + n0
d, where D is some setup cost and d is the
extra cost per unit, then the long-run average contribution of special
orders to the total cost will be (D + n0
d)μ*. The three components
of C depend on λ, μ, and n0 in a
complicated way. The following monotonicity properties seem obvious:
λ* is increasing in λ and n0 and decreasing in
μ; μ* is decreasing in λ and n0 and
increasing in μ. The dependence of
on λ, μ, and n0 is not clear. For example, a
larger value of λ gives rise to more random item arrivals but
decreases the number of special orders, so the overall change of
is hard to predict. One may conjecture that if n0
> 1, the expected inventory level, as a function of λ, first
decreases and then increases: When λ = 0, there are only special
orders, which increase the inventory level from zero to
n0 every time they are placed. As λ increases
starting from zero, the number of special orders will get smaller. For
moderately large values of λ, the reduction in inventory due to the
decrease of their frequency is likely to outweigh the increase due to
random arrivals. However, as λ gets large, the more and more frequent
random arrivals will probably outweigh the decrease of K due to
fewer special orders.
As a scenario in which λ and μ can be controlled, consider a
blood bank receiving donations from and serving hospitals in certain
neighboring areas. Suppose that the arrival times of donations and demands
from different neighborhoods are independent. Then by selecting or
excluding certain regions, the total rates of arrivals of items and
demands are at least partially controllable.
We will derive the steady-state density
fW of the VOT process W and then
express the rates λ* and μ* and the distribution of K in
terms of fW. As W is not Markovian,
it seems difficult to determine fW directly.
Our approach is to construct a certain dual process that turns out to be
Markovian, so that its steady-state distribution can be obtained by
well-known methods (mainly level crossing techniques and PASTA). The basic
arguments of this approach have been expounded in [25].
2.2. The Dual Process and the Steady-State
Density
We now construct the sample paths of the dual process V =
{V(t)|t ≥ 0} from those of A
by the following steps:
- Replace any jump of A by a linear decreasing piece of
trajectory with slope −1 on an interval whose length is equal to the
jump size.
- Replace the increasing pieces of A between its jumps by
positive jumps whose sizes are equal to the lengths of the linear
segments.
Thus, the process V results from a certain
“reversal” of jumps and linear segments of the sample paths.
In Figure 2, it is shown how the sample path of
W displayed in Figure 1 is transformed
first into the corresponding path of A and then to that of
V.
A typical sample path of the VOT process and its transformation to the
corresponding path of A and to that of V.
V can be interpreted as the content level process of a
special regenerative Markovian finite dam of the
M/G/1 type having the following features:
i. The underlying dam of V has capacity 1 (so that
the jumps due to inflows will be truncated at level 1) and V
decreases at rate 1 (between positive jumps).
ii. Instantenuous inflows arrive according to a Poisson
process with rate λ. The jump sizes are exp(μ)
distributed.
iii. Every dry period of V is replaced by an
Erlang-distributed jump with parameters μ and n0,
which is truncated at 1.
Thus, the dry periods are deleted, whereas the wet periods, forming
the cycles of V, are glued together and start with special jumps.
The cycle lengths have the same law as the times between truncated
overshoots of W (or the times between hittings of 0 of
A). In Theorem 1, we relate the steady-state laws of V
and W.
Theorem 1: Let fW and
fV be the steady-state densities of
W and V, respectively. Then for all x
∈ [0,1],
Hence, fV is given by
where the empty sum is defined to be 0 and
Proof: By level crossing theory (LCT), the steady-state
densities fW(x) and
fV(x) are given by the long-run
average rates of W and V, respectively, of downcrossing
level x (see, e.g., [25]).
Let 0 < T1 < T2 <
··· be the times of jumps of A and let 0 =
τ0 < τ1 < τ2 <
··· be the times of jumps of V. By
construction, A(Tn−) =
V(τn−1+) and
A(Tn+) =
V(τn−), and if
Tn is a time at which A hits 0, then
Tn = τn. Thus, the
long-run average downcrossing rates at any level x are the same
for A and V, so that their steady-state densities
coincide. Since W(t) = 1 − A(t)
for all t, we obtain the first equation in (2.2). To prove that
the right-hand side of (2.2) is equal to
fV(x), we note that there are two
types of arrival determining the jumps of V. The first are
Poisson arrivals of rate λ. For them, the conditional rate of
upcrossings of level x given V = v is
λe−μ(x−v), since
their jump sizes are exp(μ) distributed. By deconditioning on
V = v and using PASTA, we immediately recognize the
first term on the right-hand side of (2.2) as the upcrossing rate at
x due to the Poisson arrivals. Jumps of the second type occur
whenever V downcrosses level 0+. By LCT,
fV(0) is the long-run average rate of
downcrossings of level 0. Any jump following a hit of 0 is the first jump
in some cycle of V, and an upcrossing of level x takes
place if this jump is greater than x, an event that has
probability
because the first jump of the cycle is
Erl(μ,n0).
To solve the integral equation (2.2), let
and take derivatives. We obtain
whose general solution is
where C is some constant. For
fV, this yields
Setting x = 0 shows that C = 1. Moreover,
The functions
appearing in (2.5) satisfy the recursion
and are thus given in closed form by
Inserting (2.6) in (2.5) and the resulting expression in (2.4) yields
(2.3). Finally, fV(0) can be computed from
the normalizing condition
.
The proof is complete. █
2.3. Outdatings, Special Orders, and the Number of
Items in the System
It turns out that the relevant functionals can all be computed from
the steady-state density of the key process W. Let us first
determine the rates of outdatings and of special orders.
Lemma 1: The rate μ* of special orders is
given by
Proof: The rate of special orders is the rate of truncated
overshoots of level 1 by W. By conditioning on W and
then deconditioning, it is seen that the rate of upcrossings of level 1 by
W is
.
By Theorem 1, fW(w) =
fV(1 − w). █
Lemma 2: The rate λ* of outdatings is given
by
Proof: Since the Poisson arrivals and the arrivals of special
orders have rates λ and μ*, respectively, and every special order
is for n0 items, the long-run average input of items
is λ + n0 μ*. This equals the output rate,
which is the sum of the demand rate μ plus the outdating rate λ*.
█
Let K be the number of items in the system in steady state.
The third important functional is the expected value
.
We now derive the generating function of K. Define the event
To determine
,
consider the time interval I between two consecutive special
orders. This interval can be split into the part during which items from
the special order launched at the beginning of I are still
present and the ensuing part during which only regular items are present
(this second part may have length 0). The expected length of the first
part of I is
,
whereas the expected length of I is, of course, 1/μ*.
The sequence of these split intervals clearly forms an alternating renewal
process. Thus, it follows from the renewal theorem that
Hence,
Given Bc, all of the items in the system
are of the Poisson arrival type. Since the event {K = k}
means that k − 1 Poisson arrivals entered during the age of
the oldest item and fW(1 − v)
= fV(v), we get
where Veq is a random variable having the
steady-state distribution of V (i.e., its density is
fV).
Given B, there may be several oldest items, all coming from
some special order; all other items present, if any, are of the Poisson
arrival type. The event {K = k} then means that for some
i ∈ {1,…,n0 − 1}, exactly
i out of n0 oldest items have been taken away
by i demands and there have been k −
(n0 − i) Poisson item arrivals after
the last special order. Note that in this situation,
n0 − i − 1 oldest items are still
on the shelf and k − n0 + i
Poisson arrivals arrived during the age of the oldest items. Let
Eμ,i and Eμ be
two independent random variables that have the Erl(μ,i) and
the exp(μ) distribution, respectively. Then we obtain
We have proved the following result.
Lemma 3: The number K of items in the system in steady
state has the generating function
By Lemmas 1–3, the long-run average cost function
introduced in (2.1) can now be completely expressed in terms of the
steady-state density fV, which, in turn, has
been computed in Theorem 1.
2.4. A Model Variant with General Lead Times
Suppose now that as soon as the system becomes empty, the controller
places a special order of n0 items for which it takes
a random lead time to arrive. However, due to their high cost, such
special orders are canceled immediately if a regular item arrives at the
system before the specially ordered one. For example, if D +
n0 d is the price of a special order, at
least the setup cost D can be saved by this cancellation. In this
variation of Model 1, there are times when the shelf is empty and demands
have to leave unsatisfied.
Let G be the common distribution function of the lead times
and let
be its Laplace transform. Let
be the VOT process of the modified PIS. Unlike W, the process
is not limited to being less than or equal to 1. When
hits zero, it jumps to 1 + L, where L is a generic
random variable independent of the past and has distribution function
G; then
decreases linearly at slope −1 until it hits 1 (i.e., the ordered
items enter the system) or a regular item arrives. In this latter case,
immediately jumps down to 1; the special order is canceled. Inside
(0,1],
evolves like the VOT process W above.
It is assumed here that the lifetime of an item starts when it arrives
at the inventory system. Thus, we do not take into account reductions of
the lifetimes of items before their arrival at the PIS due to
transportation.
It is not difficult to see that
is a Markov process if n0 = 1 (i.e., if every special
order is for one item). In this case, the steady-state density can be
derived by level crossing. If n0 > 1, neither
nor its dual constructed as in Section 2.2 are Markovian, so our approach
is not applicable. In the following, we assume that n0
= 1.
Lemma 4: Let Y be the length of a time interval of
emptiness and let η(α) be the Laplace transform of Y.
Then
Proof: Clearly, Y =
min(Eλ,V), where
Eλ ∼ exp(λ), V has distribution
function G, and Eλ and V are
independent. Thus,
Now, we derive a Pollaczeck–Khintchine-type equation for the
steady-state density
.
Theorem 2: The density
satisfies
and is thus given by
where
Proof: In this model, there is no need for duality. The value
of the density
f at x is equal to the long-run average
number of downcrossings of level x by
.
Thus, it is sufficient to show that the right-hand side of (2.9) gives
the long-run average number of upcrossings of x. First, let 0
≤ x ≤ 1. Then there are two upcrossing possibilities: (i)
jumps at moments of Poisson demand arrivals and (ii) jumps at outdating
times. For upcrossings of type (i), note that the arrival rate of these
jumps is μ, and when jumping upwards from level w ∈
(0,x), the probability to upcross x is
e−λ(x−w). In case
(ii), the VOT has to reach level 0 and then to jump above x
(which happens with probability
e−λx). This leads to the two terms
on the right-hand side of (2.9) for x ∈ [0,1].
Now let x > 1. For a jump upcrossing x the
following has to happen:
a. The VOT is at some level w ∈ [0,1]
and an item leaves because it is outdated or a demand takes it
away.
b. The system becomes empty (i.e., no item has arrived during
the last 1 − w time units) and there is no regular
(Poisson) item arrival during the next x − 1 time units
(which, together, has probability
e−λ(x−w)).
c. A special order is launched and will arrive after
V time units (where V has distribution G)
unless it is canceled due to a regular arrival earlier.
d. We have V > x − 1 (which has
probability 1 − G(x − 1)).
These arguments immediately lead to the right-hand side of (2.9) for
any x > 1. The solution of (2.9) is straightforward, yielding
(2.10) and (2.11). █
In this model, the rate μ* of unsatisfied demands is given by
For the rate of launching special orders, we obtain
and for that of cancelling special orders,
3. MODEL 2: DIFFERENT CATEGORIES OF
URGENCY
In this section, we assume that there is no possibility of additional
ordering. The incoming demands are classified into different categories of
urgency. For simplicity, assume that there are two such categories whose
demand arrival times form independent Poisson processes of intensities
μ1 and μ2, respectively. One possible policy
is then to satisfy high-urgency (type 1) demands whenever possible (i.e.,
if the PIS is not empty) and demands of the less urgent type 2 only if
there are at least, say, m0 > 1 items on the shelf.
However, it has the undesirable effect of not taking the lifetime of the
oldest item into account. For example, under this policy, the oldest item
will not be used for a less urgent demand even if its residual lifetime is
very short, so its outdating is imminent. To avoid this drawback, we
propose to consider the following policy. Fix γ ∈ (0,1) and an
integer m0 > 1. A demand of type 1 is satisfied if
and only if the PIS is not empty; a demand of type 2 is satisfied if and
only if there are at least m0 items in the system or
the shelf age of the oldest item is at least 1 − γ. Any demand
(type 1 or 2) that is not immediately satisfied is lost. Let
= {W(t)|t ≥ 0} be the VOT process
of this PIS in steady state. We now derive its steady-state density
f using level crossing.
Theorem 3: We have
Proof: Again, we have to show that the right-hand sides of
(3.1)–(3.3) are the long-run average upcrossing rates of x,
this time distinguishing three different cases.
Case 1: 0 < x ≤ γ. Given that
W(t) ≤ γ, a jump of occurs in the
infinitesimal interval [t,t + dt]
with probability (μ1 + μ2)dt, since
every incoming demand is satisfied. In order to lead to an upcrossing of
level x (≤ γ), the jump size has to exceed x
− W(t). By PASTA, the latter probability is
equal to
.
Since f (0) is the long-run average rate of reaching level 0,
the product f (0)e−λx is
the rate of upcrossings of x by after hittings of
0.
Case 2: γ < x ≤ 1. The arrival rate of
demands of the first category is μ1 and such a demand
arrival causes an upcrossing of x with probability
.
Now, assume that at time t, a demand of type 2 is arriving.
There are two subcases. If W(t) < γ, the demand
is satisfied and an upcrossing of x occurs with probability
e−λ(x−w). However,
if
,
the demand is satisfied if and only if there are at least
m0 items on the shelf just prior to time t.
Moreover, to upcross level x, the process has to
jump from below x to [x,1); this means that there
have been no item arrivals in the time interval (t − (1
− w),t − (1 − x)) and at
least m0 − 1 arrivals in [t
− (1 − x),t), and the intersection of these
two events has probability
.
As earlier, the term f
(0)e−λx is the long-run average
rate of upcrossings of level 0 following hittings of 0 by
.
Case 3: x > 1. Jumps upcrossing x can
start from any level w ∈ (0,1) of for type 1
demands, any level w ∈ (0,γ] for type 2 demands,
and, of course, from level 0 (when the system becomes empty and there have
been no item arrivals for more than x time units). █
To solve (3.1)–(3.3), define
.
This function satisfies
It follows from (3.4) that
In particular,
On [γ,1], we solve (3.5) and find that
where
On [1,∞), we have, by (3.6),
The density f is then obtained by f (x)
=
e−λxG′(x).
The constant f (0) can be calculated from the normalizing
condition
.
Now, consider the cost functionals. Clearly, f (0) is the
outdating rate. The number of items in the system is n ≥ 1 if
and only if the number of arrivals during the sojourn time of the oldest
item is n − 1. Thus, the generating function of the number
K of items in steady state is
Finally, the rate of unsatisfied demands is
