Reducing the size of a waiting line optimally

M$5,2 LEFEBVRE

Department of Mathematics and Industrial Engineering

Polytechnique Montréal

2500, chemin de Polytechnique, Montréal (Québec) H3T 1J4

CANADA

https://www.polymtl.ca/expertises/en/lefebvre-mario

Abstract: The problem of reducing the number of customers waiting for service in a modified M/G/kqueueing

model is considered. We assume that the optimizer can decide how many servers are working at any time instant.

The optimization problem ends as soon as the objective has been achieved or a time limit has been reached.

Cases when dynamic programming can be used to determine the optimal control even if the service time is not

exponentially distributed are presented.

Key-Words: M/G/kmodel, first-passage time, homing problem, dynamic programming.

Received: December 23, 2022. Revised: August 29, 2023. Accepted: October 5, 2023. Published: October 27, 2023.

1 Introduction

Assume that customers arrive in a queueing system

according to a Poisson process with rate λand are

served one at a time. Then, the time Abetween two

customers has an exponential distribution with pa-

rameter λ. If there are kservers and if the service

time Shas an exponential distribution with parameter

µfor any server, then the queueing system is denoted

by M/M/k. It is also assumed that the service times

are independent random variables, and are also inde-

pendent of the times between successive customers.

The system capacity ccan be finite or infinite. Fi-

nally, the service policy is First in First out (FIFO).

When the queueing system is in equilibrium, or

steady state, customers leave according to a Poisson

process. As this is a Markovian stochastic process,

the notation Mis used to denote the model.

When the service time Shas a general distribution,

the notation becomes M/G/k. Important particular

cases are when Sis a constant, when it is uniformly

distributed, and when it has a gamma distribution.

Next, suppose that at the initial time t0the total

number X(t0)of customers in the system is equal to

k+l, where l≥1. Moreover, they are all waiting for

service. The time t0could be the opening time of a

store.

In, [1], the following stochastic optimal control

problem was considered: assuming that the optimizer

can choose the number n(t)of servers who are work-

ing at any time instant t, find how many servers must

be used in order to minimize the expected value of the

cost (or reward) function

J(t0, l) := ZT(t0,l)

t0{q0n(t)−m[n(t)]}dt. (1)

In the cost function, q0is a positive constant,

m[n(t)] is the money earned by the system, per unit

time, when n(t)∈ {1, . . . , k}servers are working,

and T(t0, l)is a first-passage time defined by

T(t0, l) = inf{t > t0:X(t) = k+ror t=t1},

(2)

where 0≤r < l and t1> t0.

The above problem, which is an extended homing

problem, was treated in, [1], in the case of the (modi-

fied) M/M/k/cqueueing system.

Homing problems, in which a stochastic process is

controlled until a given event occurs, were studied for

n-dimensional diffusion processes in, [2]. The author

also considered the case when the cost criterion takes

the risk-sensitivity of the optimizer into account in,

[3].

The author has written many papers on homing

problems; see, for instance, [4]. See also, [5], [6],

and, [7].

In, [1], the authors used dynamic programming to

prove the following proposition, in which the function

F(t0, l)is defined by

F(t0, l) := inf

n(t)

t∈[t0, T )

E[J(t0, l)].(3)

The function F(t0, l)(called the value function) is

such that it satisfies the condition F(t0, l)=0if

WSEAS TRANSACTIONS on SYSTEMS and CONTROL

DOI: 10.37394/23203.2023.18.35

Mario Lefebvre

E-ISSN: 2224-2856

342

Volume 18, 2023

l≤r. Moreover, the authors assumed that a cost

F1is incurred if the objective has not been achieved

by time t1:

F(t0, l) = F1>0if T(t0, l) = t1. (4)

Proposition 1.1. Let η=n(t0). The value function

F(t0, l)satisfies the dynamic programming equation

−∂

∂t0

F(t0, l) = inf

η{q0η−m(η) + F(t0, l + 1)λ

+F(t0, l −1)η µ −F(t0, l)(λ+η µ)}.(5)

In the current paper, we suppose that the service

time Sis not exponentially distributed. In, [8], the

author assumed that the random variable Sis actually

a constant. Here, in particular, the case when Shas a

uniform distribution will be considered.

Optimal control of queuing systems has been the

subject of numerous research papers. See, for exam-

ple, [9], [10], and, [11], for very recent ones. Here,

contrary to other articles found in the literature, the

final time is a random variable.

2 Non-exponential service times

Let Wbe an exponentially distributed random vari-

able with parameter α. We have

P[W≤t] = 1 −e−αt =αt +o(t).(6)

Moreover, if W1, . . . , Wjare independent random

variables distributed as W, then, as is well known,

min{W1, . . . , Wj}has an exponential distribution

with parameter j α.

It follows that in the case of the modified

M/M/k/cmodel considered in, [1], we can write

that

P[A≤∆t] = λ∆t+o(∆t)(7)

and

P[D≤∆t] = η µ∆t+o(∆t),(8)

where Ais the time taken for a new customer to arrive

in the system after time t0and Dis the time taken for

a customer to leave the system if there are ηservers

working at time t0.

Both Eq. (7) and Eq. (8) are needed to derive the

dynamic programming equation (5). Unfortunately,

in the case of an M/G/kqueueing system, the equa-

tion

P[D≤∆t] = κ∆t+o(∆t),(9)

where κis a positive constant, is generally not valid.

Assuming that the service time is exponentially

distributed is a simplifying assumption. Indeed, this

hypothesis is often made because then it is not neces-

sary to consider what happened since the initial time.

One only needs to observe the state of the system at a

given time instant to determine the future.

In practice, the service time Scannot be exactly

exponentially distributed. More realistic cases in-

clude the ones when Sis deterministic, or uniformly

distributed, etc.

In this section, we will present three distributions

for which Eq. (9) does hold. Let S1, . . . , Sjbe inde-

pendent random variables distributed as Sand M:=

min{S1, . . . , Sj}.

Case I. Assume first that the service time Sis uni-

formly distributed on the interval (0, L). We have

P[M > t] = L−t

Lj

for t∈(0, L).(10)

If follows that

P[M≤∆t] = 1 −L−∆t

Lj

= 1 −1

Lj(L−∆t)j

= 1 −1

LjLj−j Lj−1∆t+o(∆t)

Lj∆t+o(∆t),(11)

as required.

Case II. Assume next that the probability density

function of the service time is given by

fS(s) = 1

ln(1 + L)

1 + sfor s∈(0, L).(12)

We calculate

FS(s) = ln(1 + s)

ln(1 + L)for s∈(0, L).(13)

Hence, making use of the formula

ln(1 + x) = x−x2

2+x3

3+. . . for |x|<1,(14)

we can write that

P[M≤∆t] = 1 −1−ln(1 + ∆t)

ln(1 + L)j

= 1 −1−1

ln(1 + L)[∆t+o(∆t)]j

= 1 −1−j

ln(1 + L)∆t+o(∆t)

ln(1 + L)j∆t+o(∆t).(15)

Case III. Finally, we suppose that the probability den-

sity function of Sis

fS(s) = cos(s)

sin(L)for s∈(0, L),(16)

WSEAS TRANSACTIONS on SYSTEMS and CONTROL

DOI: 10.37394/23203.2023.18.35

Mario Lefebvre

E-ISSN: 2224-2856

343

Volume 18, 2023

where L≤π/2. This time, we use the formula

sin(x) = x−x3

3! +. . . for x∈R(17)

to write that

P[M≤∆t] = 1 −1−sin(∆t)

sin(L)j

= 1 −1−1

sin(L)[∆t+o(∆t)]j

= 1 −1−j

sin(L)∆t+o(∆t)

sin(L)j∆t+o(∆t).(18)

In the next section, we will present a case when

Eq. (9) does not hold, but the problem can be trans-

formed into the one considered in, [1].

3 Gamma distributed inter-arrival

and service times

As mentioned in the previous section, in practice, the

service time Scannot be exactly exponentially dis-

tributed. Similarly, the time Abetween arrivals can-

not exactly follow an exponential distribution either.

A distribution that generalizes the exponential distri-

bution and is more more likely to be a good (approxi-

mate) model for Sis the gamma distribution. Indeed,

because the gamma distribution has a shape param-

eter, there are many real-life situations for which S

could be well approximated by a gamma distribution.

Let Xbe a random variable having a gamma dis-

tribution with shape parameter αand inverse scale pa-

rameter β, which will be denoted by G(α, β). Assume

that α=2 and β=1, so that

fX(x) = xe−xfor x > 0.(19)

We have

FX(x) = 1 −(x+ 1)e−xfor x > 0.(20)

Therefore,

P[X≤∆x]=1−(∆x+ 1)[1 −∆x+o(∆x)]

=o(∆x).(21)

Remark. The above result is also valid for a random

variable Yhaving a G(2, µ)distribution, for which

fY(y) = µ2y e−µy for y > 0.(22)

Moreover, if M:= min{X1, . . . , Xj}, where

Xn∼G(2, µ)for n= 1, . . . , j and X1, . . . , Xjare

independent, then we find that

P[M≤∆t] = o(∆t).(23)

Assume next, for the sake of simplicity, that both

the inter-arrival time Aand the service time Shave

a G(2,1) distribution. Let us define Z=X2. We

calculate

fZ(z) = 1

2e−√zfor z > 0.(24)

It follows that

P[Z≤∆z]=1−√∆z+ 1e−√∆z

2∆z+o(∆z).(25)

Similarly, proceeding as in the previous section,

we find that

P[min{Z1, . . . , Zj} ≤ ∆t] = j

2∆t+o(∆t),(26)

where the random variables Z1, . . . , Zjare indepen-

dent and distributed as Z.

Now, in order to obtain the dynamic programming

equation (5), we must also have

Zt0+∆t

t0{q0n(t)−m[n(t)]}dt=γ∆t+o(∆t),

(27)

where γis a constant.

Suppose that the cost function J(t0, l)defined in

Eq. (1) is replaced by

C(t0, l) := ZT(t0,l)

t0{q0n(t)−m[n(t)]}tdt. (28)

If we make the change of variable z=t2, we obtain

that

Zt0+∆t

t0{q0n(t)−m[n(t)]}tdt

=Z(t0+∆t)2

0q0n(√z)−m[n(√z)]1

2dz

≈ {q0n(t0)−m[n(t0)]}1

2(∆t)2+ 2t0∆t

={q0n(t0)−m[n(t0)]}t0∆t+o(∆t).(29)

From what precedes, we can state that if Aand S

have a G(2,1) distribution and the cost function is the

one defined in Eq. (28), then by making the change of

variable z=t2, the optimal control problem consid-

ered in this note (with t0>0) is transformed into a

problem for which the dynamic programming equa-

tion that corresponds to Eq. (5) can be derived.

WSEAS TRANSACTIONS on SYSTEMS and CONTROL

DOI: 10.37394/23203.2023.18.35

Mario Lefebvre

E-ISSN: 2224-2856

344

Volume 18, 2023

4 Conclusion

In this note, the problem of reducing the size of a wait-

ing line as quickly as possible, taking into account

control costs, has been extended to the case where the

inter-arrival and service times are not exponentially

distributed.

In Section 2, we gave three probability density

functions for which Eq. (9) is valid. This equation is

necessary for the derivation of the dynamic program-

ming equation in Proposition 1.1.

Then, in Section 3, we presented a problem that,

although Eqs. (7) and (9) do not hold, we were able to

transform into a problem for which it is possible to use

dynamic programming to obtain the optimal solution.

Once the dynamic programming equation has been

derived, we need to solve difference equations in or-

der to determine the optimal control.

Finally, it would be interesting to try to solve prob-

lems for which only one of Eqs. (7) and (9 holds. As

we saw in Section 3, we must also define the cost

function appropriately. Moreover, in general one can-

not use dynamic programming to obtain the optimal

control.

Acknowledgements. The author is grateful to the

anonymous reviewers of this paper for their construc-

tive comments.

References:

[1] M. Lefebvre and R. Yaghoubi. Optimal control

of a queueing system. (Submitted for publica-

tion)

[2] P. Whittle. Optimization over Time, Vol. I, Wi-

ley, Chichester, 1982.

[3] P. Whittle. Risk-sensitive Optimal Control, Wi-

ley, Chichester, 1990.

[4] M. Lefebvre and P. Pazhoheshfar. An optimal

control problem for the maintenance of a

machine. International Journal of Systems

Science, vol. 53, no. 15, 2022, pp. 3364–3373.

https://doi.org/10.1080/00207721.2022.20832-

[5] J. Kuhn. The risk-sensitive homing problem.

Journal of Applied Probability, vol. 22, 1985,

pp. 796–803. https://doi.org/10.2307/3213947

[6] C. Makasu. Risk-sensitive control for a class of

homing problems. Automatica, vol. 45, no. 10,

2009, pp. 2454–2455. https://doi.org/10.1016/-

j.automatica.2009.06.015

[7] M. Kounta and N.J. Dawson. Linear quadratic

Gaussian homing for Markov processes

with regime switching and applications

to controlled population growth/decay.

Methodology and Computing in Applied

Probability, vol. 23, 2021, pp. 1155–1172.

https://doi.org/10.1007/s11009-020-09800-2

[8] M. Lefebvre. An optimal control problem for a

modified M/G/kqueueing system. Proceedings

of the Workshop on Intelligent Information Sys-

tems (WIIS2023), October 2023, Chişinǎu, Re-

public of Moldova, 8 pages.

[9] L. Luo, Y.-H. Tang, M.-M. Yu and W.-Q. Wu.

Optimal control policy of M/G/1 queueing sys-

tem with delayed randomized multiple vaca-

tions under the modified min(N, D)-policy con-

trol. Journal of the Operations Research Society

of China, 2022. https://doi.org/10.1007/s40305-

022-00413-9

[10] A. Petrović, M. Nikolić, U. Bugarić, B.

Delibašić and P. Lio. Controlling highway toll

stations using deep learning, queuing theory,

and differential evolution. Applications of Ar-

tificial Intelligence, vol. 119, 2023, 105683.

https://doi.org/10.1016/j.engappai.2022.105683

[11] F. Xinzhe and N. Modiano. Joint learning and

control in stochastic queueing networks with

unknown utilities. Proceedings of the ACM on

Measurement and Analysis of Computing Sys-

tems, vol. 6, no. 3, 2022, Article 58, 32 pages.

https://doi.org/10.1145/3570619

Contribution of Individual Authors to the

Creation of a Scientific Article (Ghostwriting

Policy)

The author did all the research work of this study.

Sources of Funding for Research Presented in a

Scientific Article or Scientific Article Itself

This research was supported by the Natural

Sciences and Engineering Research Council of

Canada.

Conflicts of Interest

The author has no conflict of interest to declare

Creative Commons Attribution License 4.0

(Attribution 4.0 International , CC BY 4.0)

This article is published under the terms of the

Creative Commons Attribution License 4.0

https://creativecommons.org/licenses/by/4.0/deed.en

_US

WSEAS TRANSACTIONS on SYSTEMS and CONTROL

DOI: 10.37394/23203.2023.18.35

Mario Lefebvre

E-ISSN: 2224-2856

345

Volume 18, 2023