Section I. Operations Research Models

A Comparative Study of Vacation Models Under Various Vacation Policies

INTRODUCTION

In classical queueing models, the server providing services is assumed to be available at all times even when there is no customer in the system. This idle time of the server is a wasted resource for the service provider and was one of the motivating factors for the introduction of the (pure or classical) vacation models in the 1970s (see, e.g.. [1-2]). The term “vacation” can be interpreted in many ways depending on the context of the application. For example, the servers (or machines) may have to be rested, readjusted, or undergo preventive maintenance or be shared with other systems, among other things. Since then a number of variations in how the vacation starts and ends in the case of single- and multiple-sever systems have been introduced and studied in the literature. In the classical vacation models, the servers maybe used to provide services to systems other than the one from where they are going on vacations. Almost 30 years later, the concept of a working vacation was introduced [3] so that the vacationing servers can provide services (but at a lower rate) to the customers in the original system. Vacation/working vacation models have even more significant applications these days due to the service providers making their resources available in a dynamic way using their electronic devices. Since the introduction of the vacation and the working vacation models in queueing, several hundreds of papers have been written in the last three decades or so. It is not the purpose of this note to do a literature survey on these models, as one can refer to the survey papers [4, 5] and the book [6] to get an idea of the diversity and the applied nature of the vacation and the working vacation models. Here, due to a lack of adequate systematic study of comparing and contrasting classical vacation models under any setup, more so, in a general context, we plan to discuss a few comparisons involving the (pure) vacation models under some common vacation policies using a simulation approach. Note that we use, the adjective “pure” to point out that these models are such that the servers do not serve any customers in the current system while on vacations. Before we proceed further, we briefly summarize the types of (pure) vacation models and refer the reader to the references mentioned earlier.

Single-Server Systems

a. Exhaustive multiple adaptive vacations: The vacation starts when the system becomes idle and the server resumes servicing only when a customer is present at the time of a vacation completion or by remaining idle (if there is no customer waiting) after completing a maximum of a finite number of vacations. Note that when this maximum is set at infinity, we get the classical vacation.

b. Exhaustive multiple adaptive vacations with setup time: This is similar to item (a), but with an additional requirement of a setup time before offering the first service from a vacation.

c. Threshold models:

i. N-policy: Starts a service from a vacation only when there are N customers waiting in the queue.

ii. T-policy: Starts a service or stays idle from a vacation which lasts T units of time [This is a special case of (a) with constant single vacation],

d. Batch arrivals and apply one of the aforementioned cases.

e. Batch services: Batches of size in [a, h are served and when the number is less than a at the time of a service completion the server goes on a vacation.

A returning server will start a service only when the batch size is least a. Any service will have at most b and at least a customers in service.

f. Finite buffer and apply any of the rules from (a) to (e).

g. Non-exhaustive: Here, the server may take a vacation even before the system becomes idle. The types of non-exhaustive ones considered in the literature are:

i. Gated: All those who were present at the beginning of a service (offered after returning from a vacation) are served and then go on a vacation.

ii. Limited: Given a service period (constant or random), the server serves until the system is idle or the service period gets over before going on a vacation.

iii. Decrementing: Serve until the number left in the queue is less than a pre-specified number of those present at the beginning of service initiation.

iv. Bernoulli: With a certain probability offer a service or with complement probability go on a vacation.

v. Pure limited (P-limited): Take a vacation after every single service and take multiple vacations when no one is waiting at the end of a vacation.

vi. G-limited: Serve only min {number in queue at a vacation completion, M} customers, where M is predetermined threshold value.

vii. Batch limited (В-limited): Serve a fixed number, say, M, customers during every service period. If less than M present at the end of a vacation, go for another vacation until the queue hits at least M.

h. E-limited: Combines exhaustive and non-exhaustive policies as follows. Serve, say, M, customers (including any arrivals during services) or all (if less than M present or arrive during the services) before going on a vacation [M = 1] corresponds to P-limited and M = <*= corresponds to exhaustive model].

i. T-limited: Given a time duration, say, T, the server serves all those present at the beginning of a vacation or when T units of time have expired, before going on another vacation.

j. T-exhaustive limited: Given a time duration, say, T, the server serves until the system becomes empty or T units of time have expired, before going on another vacation.

k. P-decrementing: Starting from a nonempty queue (at the beginning of a service) the server goes on a vacation until the queue is one less than what it was at the beginning of a service period. Example, if there were 10 in the queue at the beginning of a service period, the server will be busy until the queue size drops to 9.

l. G-decrementing: Starting from a nonempty queue (at the beginning of a service) the server goes on a vacation until the queue is M less than what it was at the beginning of a service period. Example, if M = 5, and there were 10 in the queue at the beginning of a service period, the server will be busy until the queue size drops to 4. [Note: M = 1 reduces to P-decrementing and M = °° corresponds to exhaustive model].

Multiserver Systems

a. All-server vacation:

i. Synchronous vacation: All servers go on a (common) vacation when the system becomes idle. Take multiple vacations when no one is present when (the group) returning from a vacation. In this policy, it is possible for some servers to be idle without going on a vacation.

ii. Asynchronous vacation: All free servers go on a vacation independently of each other. Multiple vacations are possible.

b. Some-server vacation: There is a limit on how many servers can be on a

vacation at any given time. This generalizes the all-server vacation policy.

c. Threshold-based vacation

i. All servers go on a (common) vacation when the system becomes idle and become available for service upon returning from a vacation only if there are, say, N, customers waiting in the queue.

ii. A subgroup of a predetermined number of idle servers can go on vacation at the moment the number of idle servers hits the predetermined number.

iii. In addition to point (ii), the number of waiting customers in the queue should be N: otherwise, the subgroup of servers go on another vacation.

VALIDATION OF THE SIMULATION

The validation of the simulated models is very important so as to use the simulated results for more complicated models. Hence, we validated our simulated models (under various combinations of arrivals/services and vacation durations) against a few published analytical models for which the numerical results are available (see e.g., [7-9]). To our knowledge, the analytical results along with the corresponding numerical results available in the literature are for МАР/РН/ 1-type model with exponential vacations. Thus, we validated against these models. The error percentages of the analytical results and the simulated ones for the mean sojourn time in the system in the case of a single-server system with MAP arrivals and phase type (PH) services varied anywhere from 0.02 percent through 12.0 percent depending on the type of arrival and service times. For the combination of positively correlated arrivals and hyperexponential services, the error percentage is largest. However, when the simulation is run for a longer period of time, the error percentage goes down. However, the error percentages for the fraction of time the server is on vacation is very low for all scenarios.

DETAILS ON INPUT DATA FOR SIMULATION

In order to conduct our simulation study, we need to select input parameters for the arrivals, services and for the server vacation times. Although selecting the parameters for the renewal arrivals is pretty straightforward, it is not very simple when it comes to the selection of those for the MAP processes. In Chakravarthy [9, Ю], a method was proposed to select the parameters of the MAP to qualitatively study the effect of correlation on system performance measures. We will use that to select the MAP parameters for our study here. For full details we refer the reader to [9, 10].

Let (а,Г) of dimension 5 denote an Erlang distribution with rate A., in each of the 5 phases. That is,

Define

where T° = -Те with e being a column vector of l’s. The specific values of p and p2 will be mentioned at appropriate places. For arrivals, we look at two renewals and two correlated processes. These are:

ERA: This is an Erlang of order 5 with parameter 5 A, in each of five stages, so that the mean and the standard deviation of the inter-arrival times are,

. , 1 , 0.447214

respectively, — and---.

A A*

HES: This is a hyperexponential with rates 1.9A. and 0.19A. with mixing probabilities, respectively, 0.9 and 0.1. Note that here the mean and the standard

1 2 24472

deviation of the interarrival times are, respectively, — and —Д-.

A, A,

NCA: This is MAP with parameter matrices (Z)0, Д) given in Eq. (1.1) by taking p = p2 =0.01, A.| = 2.75A., and X2 = 5.5X. Verify that here the mean

and standard deviation of the inter-arrival times are, respectively, and

—^—. Further, the correlation coefficient between two successive inter- A

arrival times can be verified to be -0.6454.

PCA This is MAP with parameter matrices (D0,D{) given in Eq. (1.1) by taking p = p2= 0.99, At, = 2.75X, and X2 = 5.57c. Verify that here the mean

and standard deviation of the inter-arrival times are, respectively, and

———. Further, the correlation coefficient between two successive inter- X 1

arrival times can be verified to be 0.6454. The value of — will be normal-

X

ized to a value required in the examples discussed later in this chapter. This normalization is needed to compare various arrival processes on a common ground. However, observe that these processes are qualitatively different in that they have different standard deviations and correlation structure.

For service times, we look at the following special cases of a /-‘//-distribution.

ERS: This is an Erlang of order 5 with parameter 5p in each of five stages, so that the mean and the standard deviation of the service times are, respec-

. , 1 J 0.447214

tively, — and-.

И Ц

HES: This is a hyperexponential with rates 1.9p and 0.19p with mixing probabilities, respectively, 0.9 and 0.1. Note that here the mean and the standard

1 2 24472

deviation of the service times are, respectively, — and-.

И Ц

For vacation times, we look at the following two special cases of a /77-distribution.

ERV: This is an Erlang of order 5 with parameter 5y in each of five stages, so that the mean and the standard deviation of the service times are, respec-

. , 1 J 0.447214

tively, — and-.

Y Y

HEV This is a hyperexponential with rates 1.9y and 0.19y with mixing probabilities, respectively, 0.9 and 0.1. Note that here the mean and the standard

1 2 24472

deviation of the service times are, respectively, — and-.

Y Y

 
Source
< Prev   CONTENTS   Source   Next >