Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout
We consider a single-server vacation queueing system that operates in the following manner. When the server returns from a vacation it observes the following rule. If there is at least one customer in the system, the server commences service and serves exhaustively before taking another vacation. If...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2007 |
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101781 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout / O.C. Ibe // Электронное моделирование. — 2007. — Т. 29, № 4. — С. 19-29. — Бібліогр.: 10 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101781 |
|---|---|
| record_format |
dspace |
| spelling |
Ibe, O.C. 2016-06-07T09:00:21Z 2016-06-07T09:00:21Z 2007 Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout / O.C. Ibe // Электронное моделирование. — 2007. — Т. 29, № 4. — С. 19-29. — Бібліогр.: 10 назв. — англ. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101781 We consider a single-server vacation queueing system that operates in the following manner. When the server returns from a vacation it observes the following rule. If there is at least one customer in the system, the server commences service and serves exhaustively before taking another vacation. If the server finds the system empty, it waits a fixed time c. At the expiration of this time the server commences another vacation if no customer has arrived; otherwise, it serves exhaustively before commencing another vacation. Analytical results are derived for the mean waiting time in the system. The timeout scheme is shown to be a generalized scheme of which both the single vacation and multiple vacations schemes are special cases, with c = ∞ and c = 0 respectively. The model is extended to the N-policy vacation queueing system. In both schemes we use a linear cost model to obtain an optimal operating value of c. Рассмотрена односерверная система массового обслуживания (СМО) с перерывами, работающая в таком режиме: при включении сервера после перерыва, если, по крайней мере, один клиент находится в системе, сервер начинает обслуживание и продолжает его до наступления очередного перерыва. Если обнаруживается, что система пуста, сервер находится в режиме ожидания фиксированное время с. По истечении этого времени наступает следующий перерыв в работе сервера, если новый клиент не появился. В противном случае, клиент обслуживается до наступления очередного перерыва. Получены аналитические оценки для среднего времени ожидания в системе. Показано, что схема прерываний является обобщенной схемой, в которой единичная и множественная схемы прерываний — частные случаи соответственно при c c = ∞ и c = 0. Модель распространяется на СМО с N-стратегиями перерывов. В обеих схемах использована линейная модель затрат для получения оптимального параметра срабатывания с. Розглянуто односерверну систему масового обслуговування (СМО) з перервами, що працює у такому режимі: при включенні сервера після перерви, якщо хоча б один клієнт перебуває у системі, сервер починає обслуговування і продовжує його до наступної перервиикщо виявляється, що система є пустою, сервер перебуває у режимі очікування фіксований час с. По закінченні цього часу починається наступна перерва у роботі сервера, якщо новий клієнт не з’явився. У протилежному випадку клієнт обслуговується до початку чергової перерви. Отримано аналітичні оцінки для середнього часу очікування в системі. Показано, що схема переривань є узагальненою схемою, в якій одинична та множинна схеми переривань — окремий випадок відповідно при c = ∞ і c = 0. Модель розповсюджується на СМО з N-стратегіями переривань. У обох схемах використано лінійну модель витрат для отримання оптимального параметра спрацьовування с. en Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout Анализ и оптимизация системы массового обслуживания с М/G/l перерывами и предельным временем ожидания сервера Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout |
| spellingShingle |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout Ibe, O.C. |
| title_short |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout |
| title_full |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout |
| title_fullStr |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout |
| title_full_unstemmed |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout |
| title_sort |
analysis and optimization of m/g/l vacation queueing systems with server timeout |
| author |
Ibe, O.C. |
| author_facet |
Ibe, O.C. |
| publishDate |
2007 |
| language |
English |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
Анализ и оптимизация системы массового обслуживания с М/G/l перерывами и предельным временем ожидания сервера |
| description |
We consider a single-server vacation queueing system that operates in the following manner. When the server returns from a vacation it observes the following rule. If there is at least one customer in the system, the server commences service and serves exhaustively before taking another vacation. If the server finds the system empty, it waits a fixed time c. At the expiration of this time the server commences another vacation if no customer has arrived; otherwise, it serves exhaustively before commencing another vacation. Analytical results are derived for the mean waiting time in the system. The timeout scheme is shown to be a generalized scheme of which both the single vacation and multiple vacations schemes are special cases, with c = ∞ and c = 0 respectively. The model is extended to the N-policy vacation queueing system. In both schemes we use a linear cost model to obtain an optimal operating value of c.
Рассмотрена односерверная система массового обслуживания (СМО) с перерывами, работающая в таком режиме: при включении сервера после перерыва, если, по крайней мере, один клиент находится в системе, сервер начинает обслуживание и продолжает его до наступления очередного перерыва. Если обнаруживается, что система пуста, сервер находится в режиме ожидания фиксированное время с. По истечении этого времени наступает следующий перерыв в работе сервера, если новый клиент не появился. В противном случае, клиент обслуживается до наступления очередного перерыва. Получены аналитические оценки для среднего времени ожидания в системе. Показано, что схема прерываний является обобщенной схемой, в которой единичная и множественная схемы прерываний — частные случаи соответственно при c c = ∞ и c = 0. Модель распространяется на СМО с N-стратегиями перерывов. В обеих схемах использована линейная модель затрат для получения оптимального параметра срабатывания с.
Розглянуто односерверну систему масового обслуговування (СМО) з перервами, що працює у такому режимі: при включенні сервера після перерви, якщо хоча б один клієнт перебуває у системі, сервер починає обслуговування і продовжує його до наступної перервиикщо виявляється, що система є пустою, сервер перебуває у режимі очікування фіксований час с. По закінченні цього часу починається наступна перерва у роботі сервера, якщо новий клієнт не з’явився. У протилежному випадку клієнт обслуговується до початку чергової перерви. Отримано аналітичні оцінки для середнього часу очікування в системі. Показано, що схема переривань є узагальненою схемою, в якій одинична та множинна схеми переривань — окремий випадок відповідно при c = ∞ і c = 0. Модель розповсюджується на СМО з N-стратегіями переривань. У обох схемах використано лінійну модель витрат для отримання оптимального параметра спрацьовування с.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101781 |
| citation_txt |
Analysis and Optimization of M/G/l Vacation Queueing Systems with Server Timeout / O.C. Ibe // Электронное моделирование. — 2007. — Т. 29, № 4. — С. 19-29. — Бібліогр.: 10 назв. — англ. |
| work_keys_str_mv |
AT ibeoc analysisandoptimizationofmglvacationqueueingsystemswithservertimeout AT ibeoc analizioptimizaciâsistemymassovogoobsluživaniâsmglpereryvamiipredelʹnymvremenemožidaniâservera |
| first_indexed |
2025-11-26T04:42:01Z |
| last_indexed |
2025-11-26T04:42:01Z |
| _version_ |
1850609371238629376 |
| fulltext |
O. C. Ibe
Department of Electrical and Computer Engineering
University of Massachusetts, Lowell
(1 University Avenue, Lowell, MA 01854, USA)
Analysis and Optimization of M/G/1 Vacation
Queueing Systems with Server Timeout
We consider a single-server vacation queueing system that operates in the following manner.
When the server returns from a vacation it observes the following rule. If there is at least one cus-
tomer in the system, the server commences service and serves exhaustively before taking another
vacation. If the server finds the system empty, it waits a fixed time c. At the expiration of this time
the server commences another vacation if no customer has arrived; otherwise, it serves
exhaustively before commencing another vacation. Analytical results are derived for the mean
waiting time in the system. The timeout scheme is shown to be a generalized scheme of which
both the single vacation and multiple vacations schemes are special cases, with c �� and c � 0 re-
spectively. The model is extended to the N-policy vacation queueing system. In both schemes we
use a linear cost model to obtain an optimal operating value of c.
Ðàññìîòðåíà îäíîñåðâåðíàÿ ñèñòåìà ìàññîâîãî îáñëóæèâàíèÿ (ÑÌÎ) ñ ïåðåðûâàìè, ðà-
áîòàþùàÿ â òàêîì ðåæèìå: ïðè âêëþ÷åíèè ñåðâåðà ïîñëå ïåðåðûâà, åñëè, ïî êðàéíåé ìåðå,
îäèí êëèåíò íàõîäèòñÿ â ñèñòåìå, ñåðâåð íà÷èíàåò îáñëóæèâàíèå è ïðîäîëæàåò åãî äî
íàñòóïëåíèÿ î÷åðåäíîãî ïåðåðûâà. Åñëè îáíàðóæèâàåòñÿ, ÷òî ñèñòåìà ïóñòà, ñåðâåð íàõî-
äèòñÿ â ðåæèìå îæèäàíèÿ ôèêñèðîâàííîå âðåìÿ ñ. Ïî èñòå÷åíèè ýòîãî âðåìåíè íàñòóïàåò
ñëåäóþùèé ïåðåðûâ â ðàáîòå ñåðâåðà, åñëè íîâûé êëèåíò íå ïîÿâèëñÿ.  ïðîòèâíîì ñëó÷àå,
êëèåíò îáñëóæèâàåòñÿ äî íàñòóïëåíèÿ î÷åðåäíîãî ïåðåðûâà. Ïîëó÷åíû àíàëèòè÷åñêèå îöåí-
êè äëÿ ñðåäíåãî âðåìåíè îæèäàíèÿ â ñèñòåìå. Ïîêàçàíî, ÷òî ñõåìà ïðåðûâàíèé ÿâëÿåòñÿ
îáîáùåííîé ñõåìîé, â êîòîðîé åäèíè÷íàÿ è ìíîæåñòâåííàÿ ñõåìû ïðåðûâàíèé — ÷àñòíûå
ñëó÷àè ñîîòâåòñòâåííî ïðè c �� è c � 0. Ìîäåëü ðàñïðîñòðàíÿåòñÿ íà ÑÌÎ ñ N-ñòðàòåãèÿìè
ïåðåðûâîâ.  îáåèõ ñõåìàõ èñïîëüçîâàíà ëèíåéíàÿ ìîäåëü çàòðàò äëÿ ïîëó÷åíèÿ îïòè-
ìàëüíîãî ïàðàìåòðà ñðàáàòûâàíèÿ ñ.
K e y w o r d s: vacation queueing systems, timeout policies, performance analysis, N-policy with
timeout.
Introduction. Vacation queueing systems have been extensively analyzed by
several authors. A survey of vacation queues is given in [1], and an excellent text
on the subject is [2]. There are several models of queueing systems, including the
single vacation system and the multiple vacation system. In the single vacation
queue, a server’s vacation begins whenever the system becomes empty. At the
end of the vacation, the server returns to begin serving the customers that arrived
during its vacation, if such customers exist; otherwise, it waits until a customer
arrives when a busy period commences. The time to serve customers and the du-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 19
ration of a vacation are assumed to be mutually independent. The multiple vaca-
tion queue operates in a manner similar to the single vacation queue with the ex-
ception that if no customers are found at the end of a vacation, the server imme-
diately commences another vacation.
A variety of problems can be modeled by the vacation queueing system.
These include machine breakdowns, maintenance in communication and com-
puter systems, and token passing local area networks. In these systems the server
becomes absent from a particular service center either because it is busy else-
where serving other customers or is unavailable due to system breakdown.
In the vacation models that have been analyzed in the literature, server time-
outs have not been considered. In this paper we consider vacation queueing sys-
tems with server timeouts. Specifically, we consider a system that operates in the
following manner. When the server has finished serving a customer and finds the
system empty, it takes a vacation whose duration is independent of both the ser-
vice time and the inter-arrival time. At the end of the vacation the server returns
to serve those customers, if any, who arrived during its vacation. It will com-
mence another vacation when the system becomes empty. If no customer arrived
during the vacation, the server waits for a fixed time c. If no customer arrives by
the end of this period, the server commences another vacation. If a customer ar-
rives before the period expires, the server commences service and serves
exhaustively before commencing another vacation.
Fig. 1 illustrates this scheme. Assume that the system has been operational
for some time and the server returns from a vacation of durationV
1
at a time la-
beled t
1
and found two customersC
1
and C
2
waiting. Before completing the ser-
vice of these customers, another customer C
3
arrives. After serving the three
customers the server takes another vacation of durationV
2
. Upon returning from
that vacation at a time t
2
it found no customer waiting. It waits for a time of dura-
tion c without any customer arriving. It thus leaves for another vacation of dura-
O. C. Ibe
20 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
N t( )
C
1
C
1
C
2
C
2
C
3
C
3
c c
C
4
V
4
V
3
V
2
V
1
t
1
t
2 t
3
t
4
t
C
4 C
7
C
8
C
5
C
5
C
6
C
6
Fig. 1. Vacation scheme with timeout
tionV
3
without serving a customer. It came back from the vacation at the time la-
beled t
3
and found two customers C
4
and C
5
waiting. Before completing the
service of these customers, another customer C
6
arrives. After serving these
three customers, the server takes another vacation of durationV
4
. Upon return-
ing from the vacation at the time labeled t
4
it found no waiting customers. How-
ever, before the expiration of the timeout, customer C
7
arrives to initiate another
busy period, and the process continues.
This vacation queueing is essentially a hybrid multiple and single vacation
scheme that was introduced in [3]. The main objective of the model in [3] was to
demonstrate how vacation queueing systems with exponentially distributed ser-
vice times and finite population could be modeled by the stochatic Petri net. In
this paper we assume that the population is infinite and service times have arbi-
trary distribution.
One important application of the vacation scheme with server timeout is to
enhance resource utilization in the single vacation model. Specifically, if there is
a problem in the arrival process that prevents customers from arriving for ser-
vice, the server may be idle indefinitely after returning from a vacation in the sin-
gle vacation. But when the idle time is bounded as described above, the server
can be used to perform other functions at the expiration of the timeout rather than
wait indefinitely. Thus, when the source is subject to breakdown, such as the dis-
ruption of the communication links along which messages arrive in a communi-
cation system, the server timeout scheme prevents the server from waiting indef-
initely for customers to arrive after returning from a vacation.
Two other hybrid vacation schemes have been proposed. In [4], if the server
returns from the ( )i�1 -th vacation and finds the system empty, it takes another
vacation with probability pi and waits for the first customer to arrive with proba-
bility 1� pi . In the later case the server takes a vacation after serving exhausti-
vely. In [2], if the server returns from a vacation and finds the system empty, it
takes at most J vacations repeatedly until it finds at least one customer waiting
in the system when it returns from a vacation. If no customer arrives by the J-th
vacation, the server waits until a customer arrives.
Analysis of the model. We assume that customers arrive at the system ac-
cording to a Poisson process with rate �� The time, X, to serve a customer has a
general distribution with cumulative distribution function (CDF) F xX ( ), mean
E X[ ] and second moment E X[ ]
2
. The Laplace—Stieltjes transform of X is
M sX ( ), which is defined by (see, for example, [5]):
M s E e e dF xX
sX sx
X( ) [ ] ( ).� �
� �
�
�
0
Analysis and Optimization of M/G/1 Vacation Queueing Systems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 21
The duration, V, of a vacation is also assumed to have a general distribution
with CDF F xV ( ) and Laplace—Stieltjes transform M sV ( ). The mean of V is
E V[ ] and its second moment is E V[ ]
2
. X and V are assumed to be mutually in-
dependent. Let the random variable A denote the number of customers in the sys-
tem at the beginning of a busy period. The probability mass function (PMF) of A
is p aA ( ) whose z-transform is given by G zA ( ) . That is,
G z E z z p aA
A a
A
a
( ) [ ] ( ).� �
�
�
�
0
The mean of A is E A[ ] and its second moment is E A[ ].
2
Let the random vari-
able B denote the number of customers left behind by an arbitrary departing cus-
tomer, and let L denote the number of customers in the system at an arbitrary
point in time. The PMF of B is p bB ( ) whose z-transform is given by G zB ( ).The
mean of B is E B[ ] and its second moment is E B[ ]
2
. Similarly, The PMF of L is
p lL ( ) whose z-transform is given by G zL ( ).The mean of L is E L[ ] and its sec-
ond moment is E L[ ].
2
Let Wq denote the waiting time in the system, and let the
utilization factor be defined as �� E X[ ] . The main result of the analysis is
the following.
Theorem. The mean waiting time in the system is given by
E W
E V
e M E V
E X
q c
V
[ ]
[ ]
{[ ] ( ) [ ]}
[ ]
( )
.�
�
�
�
�
� �
�
�
2 2
2 1 2 1
P r o o f. As shown in [6], a vacation queueing system can be analyzed by the
following decomposition:
G z G z G zL B L( ) ( ) ( ),
( / / )
�
M G 1
where G zL ( / / )
( )
M G 1
is the z-transform of the number of customers in the system
in a standard M/G/1 queue (i.e., one in which the server never takes a vacation).
In [7] it is shown that
G z
G z
z E A
B
A
( )
( )
( ) [ ]
,�
�
�
1
1
G z
z M z
M z z
L
X
X
( / / )
( )
( )( ) ( )
( )
.
M G 1
1 1
�
� � �
� �
� �
� �
Thus, applying Little’s law [8] we obtain the mean waiting time as
E W
d
dz
G z E X
E A E A
E A
E X
q L z
[ ] ( ) [ ]
[ ] [ ]
[ ]
[ ]
(
� � �
�
�
1
2 2
1
2 2
� �
�
1� )
.
O. C. Ibe
22 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
This means that once G zA ( ) is known we can obtain E Wq[ ]. The remainder
of the proof is devoted to deriving the expressions for G zA ( ) and M sW ( ), the
Laplace—Stieltjes transform of the waiting time.
Consider the following three mutually exclusive events associated with the
server’s experience after returning from a vacation.
1.The server returns from vacation, waits and commences another vacation
without serving a customer; the probability of this event is M eV
c
( )�
��
.
2. The server returns from vacation, waits and serves at least one customer
before taking another vacation; the probability of this event is M eV
c
( ){ }�
�
1�
�
.
3. The server returns from vacation and finds at least one waiting customer;
the probability of this event is1� MV ( )� .
Under event 2, a busy period is initiated with exactly one customer in the
system. Similarly, under event 3, a busy period is initiated with at least one cus-
tomer in the system. Therefore, if we define pk as the probability of event k,
given that a busy period was initiated before the server commences another va-
cation, where k �2 3, , then we obtain the following result:
G z zp
M z M
M
pA
V V
V
( )
( ) ( )
( )
,�
� �
�
2 3
1
� � �
�
where
p
M e
e M
V
c
c
V
2
1
1
�
�
�
�
�
( ){ }
( )
,
�
�
�
�
p
M
e M
V
c
V
3
1
1
�
�
�
�
( )
( )
.
�
�
�
From this we obtain the result:
E A p
E V
M
p
V
[ ]
[ ]
( )
,�
�
2 3
1
�
�
E A E A
E V
M
p
V
[ ] [ ]
[ ]
( )
,
2
2 2
3
1
�
�
�
�
E W
E V
E A e M
E X
q c
V
[ ]
[ ]
[ ][ ( )]
[ ]
( )
�
�
�
�
�
�
�
�
�
2 2
2 1 2 1
�
�
�
�
�
� �
�
�
E V
e M E V
E X
c
V
[ ]
{[ ] ( ) [ ]}
[ ]
( )
,
2 2
2 1 2 1
which completes the proof. We consider limiting cases for c:
lim [ ]
[ ]
[ ]
[ ]
( )
,
c
qE W
E V
E V
E X
�
�
�0
2 2
2 2 1
�
lim [ ]
[ ]
{ ( ) [ ]}
[ ]
( )
.
c
q
V
E W
E V
M E V
E X
��
�
�
�
� �
�
2 2
2 2 1
Analysis and Optimization of M/G/1 Vacation Queueing Systems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 23
These are the results obtained in [9] for the multiple vacation system and
single vacation system, respectively. Note that E Wq[ ]monotonically decreases
as c increases since
dE W
dc
E V M e
e M E V
q V
c
c
V
[ ] [ ] ( )
{[ ] ( ) [ ]}
�
�
�
�
�
�
� �
� �
�
�
2 2
2
2 1
0
which is consistent with the fact that the single vacation scheme ( )c �� has a
smaller mean waiting time than the multiple vacation scheme( )c �0 .
Also, in [2] it is shown that the Laplace—Stieltjes transform of the waiting
time is given by
M s
G s
E A s M s
W
A
X
( )
( ){ ( / )}
[ ]{ ( )}
.�
� � �
�
� �
� �
1 1 1
Applying this result to our model yields
M s
M s s e M
s e M
W
V
c
V
c
V
( )
( ){ [ ( )] ( ) ( )}
{ ( )
�
� �
�
�
�
�
1 1 1
1
� �
�
�
( [ ]}{ ( )}�
� � �
�
E V s M sX
which, on differentiation and evaluating at s �0, gives the same value of E Wq[ ]
obtained earlier.
Although the model has been analyzed with fixed timeout c, the analysis can
be extended to the case where the timeout is a random variable T with mean E T[ ]
and Laplace—Stieltjes transform M sT ( ). In this case only a slight modification
is required in the results. Specifically, we replace the factor e c��
with MT ( )� .
Optimal timeout design. As stated earlier,
dE W
dc
E V M e
e M E V
q V
c
c
V
[ ] [ ] ( )
{[ ] ( ) [ ]}
�
�
�
�
�
�
� �
� �
�
�
2 2
2
2 1
0
which means that E Wq[ ] decreases as c increases. Thus, c = � provides the
smallest mean waiting time. However, one of the benefits of a vacation queueing
system is to engage the server in other activities when the queue is empty. This
means that any idle time incurs some cost to the system operator. For ease of
analysis, we assume that a linear cost is associated with idle times. Thus, the cost
incurred in the time interval c is kc, where k �0. To further simplify the analysis
we assume that k �1. We also assume that there is a unit cost per unit mean wait-
ing time. Therefore, we formulate the following optimization problem:
Minimize
subject to
S c E W c
c
q( ) [ ]
.
�
� 0
O. C. Ibe
24 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
The solution to the problem satisfies the condition
d
dc
S c( ) .�0 That is,
�
�
�
�
�
� �
� �
�
�
2 2
2
2 1
1 0
E V M e
e M E V
V
c
c
V
[ ] ( )
{[ ] ( ) [ ]}
.
Let x e c
�
��
. Then we obtain
2 4 4
2 2 2 2 2M x M E V M M E V xV V V V( ) { ( ) [ ] ( ) ( ) [ ]}� � � � � ��
�{ ( [ ]) ( ) ( ) [ ]} .2 2 4 0
2 2 2
� � � �E V M M E VV V
The solution to the equation is
x
E V M E V E V E V MV V
�
�
{ [ ] ( ) [ ]} [ ]{ [ ] ( )� � � � � � �
2 2 2 2 2
4 4 8 8 E V
MV
[ ]}
( )
.
4 �
It can be shown that
� � � � � � �E V E V M E V E V M E VV V[ ]{ [ ] ( ) [ ]} [ ] ( ) [
2 2 2 2 2
8 8 4 4
�
].
Thus, we use the smaller of the two solutions as the feasible solution and obtain
x
E V M E V E V E V MV V* { [ ] ( ) [ ]} [ ]{ [ ] ( )
�
�
� � � � � �
2 2 2 2 2
4 4 8 8�
�
E V
MV
[ ]}
( )
.
4
From this we obtain c x* *
ln{ }.� �1 �
The N-policy with timeout. The N-policy was introduced in [10] and op-
erates as follows. The server goes on vacation at the end of a busy period. The
vacation ends with the arrival of the N-th customer since the end of the last busy
period.
The N-policy scheme with timeout operates as follows. Consider cycles of
busy periods and let Til denote the arrival time of the i-th customer in the l-th cy-
cle, where i = 1, 2, …, N, and l = 1, 2, ... . Starting from the arrival of the first cus-
tomer in a given cycle, if less than N � 1 other customers arrive within the time
interval c, then the server’s vacation ends and service is performed exhaustively
at the end which another vacation begins. Assume that the system is empty and,
therefore, the server is on the l-th vacation. The vacation ends at timeTl given by
T T c Tl l Nl�
min ( , )
1
l = 1, 2, ...
That is, the vacation ends at time TNl (when the N-th customer arrives) or
T cl1
(if less than N �1customers arrive within the timeout period c measured
from when the first customer arrived), whichever comes first. This means that
each busy period begins with either N customers, if T T cNL l�
1
,or n customers,
1 1� � �n N , otherwise. The server serves exhaustively and takes another vaca-
Analysis and Optimization of M/G/1 Vacation Queueing Systems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 25
tion when the system becomes empty, whatever number of customers the busy
period begins with.
The scheme is illustrated in Fig. 2, where it is assumed that N �3. In the fig-
ure, during the server’s first server vacation customer C
1
arrives and thus acti-
vates the timer. By the time the timeout expired only one other customer, C
2
, ar-
rived. Since the timeout has expired with less than 3 customers in the system, the
server initiates a busy period with two customers at time t
1
. Another customer,
C
3
, arrived during this busy period. After serving all 3 customers, the server
takes a vacation. While the server is on vacation, customerC
4
arrives to activate
the timer for the next cycle. The time expires at time t
2
and the server initiates a
busy period at that time with only one customer. During this busy period, cus-
tomersC
5
andC
6
arrive and are served before the server commences another va-
cation. While the server is on vacation, customer C
7
arrives and activates the
time. Before the timer expires customer C
8
arrives. The timer expires at time t
3
and the server initiates a busy period at that time with two customers. During that
busy period customer C
9
arrives and is served before the server commences an-
other vacation. The process continues, as shown in the figure. The intervals la-
beledVi , i = 1, 2, ..., indicate the vacation intervals under the normal N-policy.
The analysis of the model is similar to that for the single vacation with
server timeout. In the current scheme, a busy period will commence with exactly
N customers in the system with probability q N which is the probability of N �1
or more Poisson arrivals in an interval of length c and thus is given by
q
c
n
eN
n
n
N
c
� �
�
�
�
�1
0
2
( )
!
.
� �
O. C. Ibe
26 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
�
N t( )
C
1
C
1
C
2
C
2
C
3
C
3
cc c
C
4
V
4
V
3
V
2
V
1
t
1
t
2
t
3
t
C
4
C
7
C
7
C
9
C
9
C
8
C
8
C
5
C
5
C
6
C
6
Fig. 2. N-policy scheme with timeout
Similarly, a busy period will commence with n customers, 1 1� � �n N , with
probability qn , which is the probability of exactly n�1. Poisson arrivals in an in-
terval of length c and is given by
q
c
n
en
n
c
�
�
�
�( )
( )!
,
� �
1
1
1 1� � �n N .
Therefore,
G z z q z q z
c
n
eA
N
N
n
n
N
n
c
n
N
n
N
( )
( )
!
�
� �
�
�
�
�
�
�
�
�
�
�
�
�1
0
2
1
1
� �
� �
�
�
�
�
�
z
c
n
en
n
c
n
N
( )
( )!
,
� �
1
1
1
1
E A N
c
n
e
n c
n
e
n
c
n
N n
[ ]
( )
!
( )
( )!
� �
�
�
�
�
�
�
�
�
�
� �
�
�1
1
0
2 1
� �
� �c
n
N
�
�
�
�
1
1
� �
�
�
�
�
�
�
�N
N n c
n
e
n
c
n
N
( ) ( )
( )!
.
�
�
1
1
1
1
If we define D as the event that there are N customers at the beginning of a busy
period and E as the event that there are less than N customers at the beginning of
a busy period, then p qD N� , p qE n n� .
Mimicking the method used in [2] we have the following conditional
Laplace—Stieltjes transform of the waiting time:
M s D
s M s
N s M s
W
N
X
N
X
( )
( ){[ / ( )] [ ( )] }
{[ / ( )] [ (
�
�
�
�
1 � �
� � )]}
( ){ [ ( )] }
{ ( )}
,
� �
�
�
� �
1 1 M s
N s M s
X
N
X
M s E n
s M s
n s M
W
n
X
n
X
( , )
( ){[ / ( )] [ ( )] }
{[ / ( )] (
�
�
�
�
1 � �
� � s
M s
n s M s
X
n
X)}
( ){ [ ( )] }
{ ( )}
.
� �
�
�
� �
1 1
Thus, the unconditional Laplace—Stieltjes transform of the waiting time is
given by
M s M s D p M s E n pW W D W
n
N
E n( ) ( ) ( , )�
�
�
�
�
1
1
�
�
�
�
�
�M s D p M s E n
c
n
eW D W
n
N
c
( ) ( , )
(
( )!
.
1
1
1
�
���
�
From this we obtain the mean waiting time as
E W
N
p
E X
p
E X n
q D D[ ]
[ ]
( )
[ ]
( )
�
�
�
�
��
�
�
1
2 2 1 2 1
1
2
2 2
�
�
�
�
�
�
�
�
�
� �
�
�
n
N n
cc
n
e
1
1 1
1
( )
( )!
� �
Analysis and Optimization of M/G/1 Vacation Queueing Systems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 27
�
�
�
�
�
�
�
�
� �
�
�
N E X N n c
n
e
n
N n
c1
2 2 1 1
2
1
1 1
�
�
�
�
[ ]
( )
( ) ( )
( )!
E A E X[ ] [ ]
( )
.
�
�
1
2 2 1
2
�
�
Before considering the limiting values of c, we recall that the expected value of A
is given by
E A N
N n c
n
e
n
n
N
c
[ ]
( ) ( )
( )!
� �
�
�
�
�
�
�
�
�
�
�
1
1
1
1
� � � �
�
�
� �
�
�
�
�
� �
�N N e
N n c
n
e e
Nc
n
n
N
c c
( )
( ) ( )
( )!
(
1
1
1
2
1
� � �
� �
�
�
�
�
�
�
n c
n
e
n
n
N
c) ( )
( )!
.
�
�
1
2
1
1
Thus, lim [ ]
c
E A
�
�
0
1 and lim [ ]
c
E A N
��
� . This implies that
lim [ ]
[ ]
( )
,
c
qE W
E X
�
�
�0
2
2 1
�
lim [ ]
[ ]
( )
,
c
qE W
N E X
��
�
�
�
1
2 2 1
2
�
�
which are the results for a standard M/G/1 queue with no server vacation and a
standard N-policy scheme without timeout, as shown in [10] respectively. We
observe that
dE W
dc
e
N n c
n
N n c
n
q c
n n
[ ] ( ) ( )
( )!
( ) ( )
( )
�
�
�
�
�
�
�
� �
�
� �
�
1 2
1 2 !n
N
n
N
�
�
�
�
��
�
�
�
�
�
�
2
1
1
1
0
which means that the expected waiting time monotonically increases with c.
Therefore, the optimal value of c is zero.
Summary. We have derived expressions for the mean waiting time of a va-
cation queueing system in which the server does not immediately take another
vacation upon returning from a vacation and finding the system empty, as in the
multiple vacation scheme, or wait indefinitely for a customer to arrive, as in the
single vacation scheme. In the proposed model, if the server returns from a vaca-
tion and finds the system empty, it waits for a fixed time c. If at the expiration of
this time no customer arrives, the server will take a vacation; otherwise it serves
arriving customers exhaustively before taking another vacation. The results of
the analysis are consistent with those of the multiple vacations scheme (where
c �0, and the single vacation scheme where c ��). A linear cost model was as-
sumed to obtain the optimal value of c for the assumed model.
The model is also extended to the N-policy scheme where the timeout is
measured from the arrival of the first customer since the end of the last busy pe-
riod. The results have also been shown to be consistent with earlier results for the
O. C. Ibe
28 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 4
case when c �0, which is the standard M/G/1 queue, and the case when c ��,
which is the N-policy scheme without timeout. It is shown that the expected
waiting time increases monotonically with c, which means that c �0 gives the
minimum expected waiting time.
Ðîçãëÿíóòî îäíîñåðâåðíó ñèñòåìó ìàñîâîãî îáñëóãîâóâàííÿ (ÑÌÎ) ç ïåðåðâàìè, ùî
ïðàöþº ó òàêîìó ðåæèì³: ïðè âêëþ÷åíí³ ñåðâåðà ï³ñëÿ ïåðåðâè, ÿêùî õî÷à á îäèí ê볺íò
ïåðåáóâຠó ñèñòåì³, ñåðâåð ïî÷èíຠîáñëóãîâóâàííÿ ³ ïðîäîâæóº éîãî äî íàñòóïíî¿
ïåðåðâèèêùî âèÿâëÿºòüñÿ, ùî ñèñòåìà º ïóñòîþ, ñåðâåð ïåðåáóâຠó ðåæèì³ î÷³êóâàííÿ
ô³êñîâàíèé ÷àñ ñ. Ïî çàê³í÷åíí³ öüîãî ÷àñó ïî÷èíàºòüñÿ íàñòóïíà ïåðåðâà ó ðîáîò³
ñåðâåðà, ÿêùî íîâèé ê볺íò íå ç’ÿâèâñÿ. Ó ïðîòèëåæíîìó âèïàäêó ê볺íò îáñëóãîâóºòüñÿ
äî ïî÷àòêó ÷åðãîâî¿ ïåðåðâè. Îòðèìàíî àíàë³òè÷í³ îö³íêè äëÿ ñåðåäíüîãî ÷àñó î÷³êóâàííÿ
â ñèñòåì³. Ïîêàçàíî, ùî ñõåìà ïåðåðèâàíü º óçàãàëüíåíîþ ñõåìîþ, â ÿê³é îäèíè÷íà òà
ìíîæèííà ñõåìè ïåðåðèâàíü — îêðåìèé âèïàäîê â³äïîâ³äíî ïðè c �� ³ c � 0. Ìîäåëü
ðîçïîâñþäæóºòüñÿ íà ÑÌÎ ç N-ñòðàòåã³ÿìè ïåðåðèâàíü. Ó îáîõ ñõåìàõ âèêîðèñòàíî
ë³í³éíó ìîäåëü âèòðàò äëÿ îòðèìàííÿ îïòèìàëüíîãî ïàðàìåòðà ñïðàöüîâóâàííÿ ñ.
1. Doshi B.T. Queueing Systems with Vacations - A Survey // Queueing Systems.— 1986. —
Vol. 1. — P. 29—66.
2. Takagi H. Queueing Analysis — A Foundation of Performance Analysis. Vol. 1: Vacation
and Priority Systems. — Amsterdam: North-Holland, 1991.
3. Ibe O.C., Trivedi K.S. Stochastic Petri Net Analysis of Finite-Population Vacation Queueing
Systems// Queueing Systems. — 1991. — Vol. 8.— P. 111—128.
4. Kella O. Optimal Control of the Vacation Scheme in an M/G/1 Queue// Operations Re-
search. —1990. — Vol. 38. — P. 724—728.
5. Ibe O.C. Fundamentals of Applied Probability and Random Processes. — Burlington, Mas-
sachusetts: Elsevier Academic Press, 2005.
6. Fuhrmann S.W., Cooper R.B. Stochastic Decompositions in the M/G/1 Queue with General-
ized Vacations// Operations Research. — 1985. — Vol. 33. — P. 1117—1129.
7. Kleinrock L. Queueing Systems Vol. 1: Theory.— N. Y.: John Wiley & Sons, 1975.
8. Little J.D.C. A Proof of the Formula: L W�� //Operations Research. — 1961. — Vol. 9. —
P. 383 — 387.
9. Levy Y., Yechiali U. Utilization of Idle Time in an M/G/1 Queueing System// Management
Science. — 1975. — Vol. 22. — P. 202—211.
10. Yadin M., Naor P. Queueing Systems with a Removable Service Station//Operational Re-
search Quarterly. — 1963. — Vol. 14. — P. 393—405.
Ïîñòóïèëà 29.11.06
Analysis and Optimization of M/G/1 Vacation Queueing Systems
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 4 29
|