Partitioning Customers Into Service Groups.
We explore the issues of when and how to partition arriving customers into service groups that will be served separately, in a first-come first-served manner, by multiserver service systems having a provision for waiting, and how to assign an appropriate number of servers to each group. We assume that customers can be classified upon arrival, so that different service groups can have different service-time distributions. We provide methodology for quantifying the tradeoff between economies of scale associated with larger systems and the benefit of having customers with shorter service times separated from other customers with longer service times, as is done in service systems with express lines. To properly quantify this tradeoff, it is important to characterize service-time distributions beyond their means. In particular, it is important to also determine the variance of the service-time distribution of each service group. Assuming Poisson arrival processes, we then can model the congestion experienced by each server group as an M/G/s queue with unlimited waiting room. We use previously developed approximations for M/G/s performance measures to quickly evaluate alternative partitions.
Introduction
In this paper we consider how to design service systems. We assume that it is possible
to initially classify customers according to some attributes. We then consider partitioning
these customer classes into disjoint subsets that will be served separately, each in a first-come
first-served manner. We assume that all customer classes arrive in independent Poisson
processes. Thus the arrival process for any subset in the partition, being the superposition
of independent Poisson processes, is also a Poisson process. Each arriving customer receives
service from one of the servers in his service group, after waiting if necessary in a waiting
room with unlimited capacity. We assume that the service times are mutually independent
with a class-dependent service-time distribution. Hence, we model the performance of each
subset as an M/G/s service system with s servers, an unlimited waiting space and the first-come
first-served service discipline. The problem is to form a desirable partition and assign an
appropriate number of servers to each subset in the partition.
If all the service-time distributions are identical, then it is more efficient to have aggregate
systems, everything else being equal; e.g., see Smith and Whitt (1981) and Whitt (1992).
(See Mandelbaum and Reiman (1997) for further work on resource sharing.) Thus, with
common service-time distributions we should select a single aggregate system. However, here
we are interested in the case of different service-time distributions. With different service-time
distributions, the service-time distributions are altered in the partitioning process. With
different service-time distributions, there is a tradeoff between the economies of scale gained
from larger systems and the cost of having customers with shorter service times have their
quality of service degraded by customers with longer service times. Thus, there is a natural
motivation for separation, as in the express checkout lines in a supermarket.
When the different classes have different service-time distributions, the service-time distribution
for each subset in the partition is a mixture of the component service-time distributions.
This makes the mean just the average of the component means. If the component means are
quite different, though, then the subset service-time distribution will tend to be highly variable,
e.g., as reflected by its squared coefficient of variation (SCV, variance divided by the square
of its mean). This high variability will in turn tend to degrade the performance of the M/G/s
queue for the subset.
The customers may initially be classified in many ways. One way that we specifically want
to consider is by service time. It may happen that the customers' service requirements are
known (or at least can be accurately estimated) upon arrival. Then we can consider classifying
the customers according to their service times. We can then partition the positive halfline
into finitely many disjoint subintervals and let customers with service times in a common
subinterval all belong to the same class. Clearly, partitioning customers according to service
times tends to reduce variability; i.e., the variability within each class usually will be less than
the overall variability. (For ways to formalize this, see Whitt (1985a).)
Since there are (infinitely) many possible ways to partition service times into subintervals,
there are (infinitely) many possible designs. Thus, we want a quick method for evaluating
candidate designs. For that purpose, we propose previous M/G/s approximations, as in Whitt
(1992, 1993).
When the customer classes are specified at the outset, it is natural to formulate our design
problem as an optimization problem. The goal can be to minimize the total number of servers
used, while requiring that each class meet a specified performance requirement, e.g., the steady-state
probability that a class-i customer has to wait more than d i should be less than or equal
to p i for all i. These requirements might well not be identical for all classes. It is natural to
measure the waiting time (before beginning service) relative to the service time or expected
service time; i.e., customers with longer service times should be able to tolerate longer waiting
times. The alternatives that must be considered in the optimization problem are the possible
partitions that can be used and the numbers of servers that are used in the subsets. When
there are not many classes, this optimization problem can be easily solved with the aid of the
approximations by evaluating all (reasonable) alternatives.
Larger problems can be solved approximately by exploiting two basic principles. First, the
advantage of partitioning usually stems from separating short service times from long ones.
Thus, we should tend to put classes with similar service-time distributions in the same subset.
In many cases (as when we partition according to service times), it will be possible to rank
order the classes according to the usual size of service times. Then it may be reasonable
to restrict attention to partitions in which no two classes appear together unless all classes
ranked in between these two also belong. Then partitions can be easily characterized by their
boundary point in the ordering.
The second principle is that we should not expect to have a very large number of subsets
in the partition, because a large number tends to violate the efficiency of large scale. Thus
it is natural to only look for and then compare the best (or good) partitions of size 2, 3, 4,
and 5, say. For example, it is natural to consider giving special protection to one class with
the shortest service times; e.g., express lanes in supermarkets. It is also natural to consider
protecting the majority of the customers from the customers with the largest service times;
e.g., large file transfers over the internet. If only these two objectives are desired, then only
three classes are needed. It is not difficult to examine candidate pairs of boundary points
within a specified ordering.
In this paper we assume that the customer service-time distributions are unaffected by the
partitioning, but in general that need not be the case. Combining classes might actually make it
more difficult to provide service, e.g., because servers may need different skills to serve different
classes. This variation might be analyzed within our scheme by introducing parameters
for each pair of classes (i; We could then have each service time of a customer
of class i multiplied by j ij if classes i and j belong to the same subset in the partition. This
would cause the mean to be multiplied by j ij but leave the SCV unchanged. This modification
would require recalculation of the two service-time moments for the subsets in the partition,
but we still could use the M/G/s analysis described here. More general variants take us out
of the M/G/s framework, and thus remain to be considered.
Here is how the rest of this paper is organized. In Section 2 we review simple approximations
for M/G/s performance measures. In Section 3 we indicate how to calculate the parameters of
the subset service-time distributions when we partition according to service times. In Section 4
we indicate how to calculate service-time parameters when we aggregate classes. In Section 5
we indicate how we can select a reasonable initial number of servers for an M/G/s system, after
which we can tune for improvement. In Section 6 we illustrate the advantages of separating
disparate classes by considering a numerical example with three classes having very different
service-time distributions. In Section 7 we illustrate the potential advantage of partitioning
according to service requirement by considering a numerical example with a Pareto service-time
distribution. We split the Pareto distribution into five subintervals. We show there that
the partition may well be preferred to one aggregate system. In Section 8 we briefly discuss
other model variants; e.g., we point out that the situation is very different when there is no
provision for waiting. Finally, in Section 9 we state our conclusions.
2. Review of M/G/s Approximations
In this section we review basic approximations for key performance measures of M/G/s
systems. We want to be able to quickly determine the approximate performance of an M/G/s
system, so that we can quickly evaluate possible partition schemes. We shall be concerned with
the steady-state probability of having to wait, P (W ? 0), and the steady-state conditional
expected wait given that the customer must wait, E(W jW ? 0). The product of these two
is of course the mean steady-state wait itself, EW . We shall also want the steady-state tail
probability desired t. Relevant choices of t typically depend on the mean
service time, here denoted ES.
The basic model parameters are the number of servers s, the arrival rate - and the service-time
cdf G with k th moments m k , k - 1. The traffic intensity is we assume that
so that a proper steady state exists. This condition puts an obvious lower bound on
the number of servers in each service group. The service-time SCV is c 2
1 .
We propose using approximations for the M/G/s performance measures. We could instead
use exact M/M/s (Erlang C) formulas involving exponential service-time distributions with the
correct mean, but we advise not doing so because it is important to capture the service-time
distribution beyond its mean via its SCV. (This is shown in our examples later.) On the other
hand, we could use simulation or more involved numerical algorithms, as in de Smit (1983),
Seelen (1986) and Bertsimas (1988), to more accurately calculate the exact performance mea-
sures, but we contend that it is usually not necessary to do so, because the approximation
accuracy tend to be adequate and the approximations are much more easy to use and under-
stand. The adequacy of approximation accuracy depends in part on the intended application
to determine the required number of servers. A small change in the number of servers (e.g., by
one) typically produces a significant change in the waiting-time performance measures. This
means that the approximation error has only a small impact on the decision. Moreover, the
approximation accuracy is often much better than our knowledge of the underlying model parameters
(arrival rates and service-time distributions). If, however, greater accuracy is deemed
necessary, then one of the alternative exact numerical algorithms can be used in place of the
approximations here.
We now specify the proposed approximations. First recall that the exact conditional wait
for M/M/s is
E(W (M=M=s)jW (M=M=s) ?
which is easy to see because an M/M/s system behaves like an M/M/1 system with service
rate s=m 1 when all s servers are busy. As in Whitt (1993) and elsewhere, we approximate the
conditional M/G/s wait by
E(W (M=G=s)jW (M=G=s) ?
Following Whitt (1993) and references cited there, we approximate the probability of delay
in an M/G/s system by the probability of delay in an M/M/s system with the same traffic
intensity ae, i.e.,
where
with
Algorithms are easily constructed to compute the exact M/M/s delay probability in (2.4).
However, we also propose the more elementary heavy-traffic approximation from Halfin and
Whitt (1981),
where \Phi is the standard (mean 0, variance 1) normal cdf and
As shown in Table 13 of Whitt (1993), approximation (2.6) is quite accurate except for the
cases in which both s is large and ae is small (and the delay probability itself is small). An
alternative simple approximation for the M/M/s delay probability is the Sakasegawa (1977)
approximation
(Combine (2.9) and (2.12) of Whitt (1993).) We do not attempt to evaluate these approximations
here, because that has already been done. The approximation errors from using (2.6)
and (2.8) instead of the exact formula are displayed for a range of cases in Tables 1 and 13 of
Whitt (1993).
When we combine (2.2) and (2.3), we obtain the classic Lee and Longton (1959) approximation
formula for the mean, i.e.,
which we complete either with an exact calculation or approximation (2.6) or (2.8). We
may know roughly what the probability of delay will be; e.g., we might have
0:25. Then we can obtain an explicit back-of-the-envelope approximation by substituting
that approximation into (2.9). A simple heavy-traffic approximation is obtained by letting
equivalently, EW - (W jW ? 0), which amounts to
using (2.2). Then for fixed ae, there is a clear tradeoff between s (scale) on the one hand and
combination of mean and variability of the service-time distribution) on the other
hand.
We can approximate the tail probability roughly by assuming that the conditional delay is
exponential, i.e.,
Approximation (2.10) is exact for M/M/s, but not more generally. Approximation (2.10) is
also consistent with known heavy-traffic limits. The accuracy of (2.10) is often adequate.
Refinements can be based on the asymptotic behavior as t ! 1; e.g., see Abate, Choudhury
and Whitt (1995).
3. Splitting by Service Times
Suppose that we are given a single M/G input with arrival rate - and service-time cdf G.
We can create m classes by classifying customers according to their service times, which we
assume can be learned upon arrival. We use
We say that an arrival belongs to class i if its
service time falls in the interval 1. For class 1 the interval is [0; x 1 ]; for
class m the interval is
Since the service times are assumed to be independent and identically distributed (i.i.d),
this classification scheme partitions the original Poisson arrival process into m independent
Poisson arrival processes. Thus one M/G input has been decomposed into m independent
M/G inputs (without yet specifying the numbers of servers).
The arrival rate of class i is thus
(regarding G(0) as and the associated service-time cdf is
The k th moment of G i is
x
It is significant that the moments of the split cdf's can be computed in practice, as we now
Example 3.1. (exponential distributions). Suppose that the cdf G is exponential with
so that the density is
If G i is G restricted to the interval
The first two moments of G i are then
and
Example 3.2. (Pareto distributions). Suppose that the cdf G is Pareto with decay rate
ff, i.e., so that the complementary cdf is
and the density is
A Pareto distribution is a good candidate model for relatively more variable (long-tailed)
service-time distributions. The mean is infinite if ff - 1. If ff ? 1, then the mean is
then the variance is infinite. If ff ? 2, then the SCV is
If G i is G restricted to the interval
We can apply formulas (3.12) and (3.13) to calculate the first two moments of G i . They are
ff
and
ff
As indicated after (2.9), we can do a heavy-traffic analysis to quickly see the benefits of
service-time splitting. Suppose that we allocate servers proportional to the offered load, so
that ae
ae
Then, by (2.2),
and
for EW in (3.15). Hence, EW
This simple analysis shows
that important role played by service-time variability, as approximately described by the SCVs
s and c 2
si .
Remark 3.1. When we split service times, we expect to have c 2
s , but that need not be
the case. First, if G is uniform on [0; x], then G i is uniform on
1=3. Second, suppose that G assigns probabilities ffl=2, ffl=2 and 1 \Gamma ffl to 0, x 1 and x
so that we can have c 2
s .
4. Aggregation
Suppose that we are given m independent M/G inputs with arrival rates - i and service-time
m. Then the m classes can be combined
(aggregated) into a single M/G input with arrival rate the sum of the component arrival rates,
i.e.,
and service-time cdf a mixture of the component cdf's, i.e.,
having moments
It should be evident that if a single M/G input is split by service times as described in
Section 3 and then recombined, we get the original M/G input characterized by - and G back
again.
5. Initial Numbers of Servers
In this section we indicate how to initially select the number of servers in any candidate
M/G/s system. Our idea is to use an infinite-server approximation, as in Section 2.3 of Whitt
(1992) or in Jennings, Mandelbaum, Massey and Whitt (1996). In the associated M/G/1
system with the same M/G input, the steady-state number of busy servers has a Poisson
distribution with mean (and thus also variance) equal to the offered load (product of arrival
rate and mean service time, say !. The Poisson distribution can then be approximated by a
normal distribution. We thus let the number of servers be the least integer greater than or
equal
!, which is c standard deviations above the mean. A reasonable value of the
constant is often and we will use it. Then the number of servers is
A rough estimate (lower bound) for the probability of delay is then
where N(a; b) denotes a normal random variables with mean a and variance b, and \Phi c is the
complementary cdf of N(0; 1), i.e., \Phi c choice tends to keep the
waiting time low with the servers well utilized. Of course, the number of standard deviations
above the mean and/or the resulting number of servers can be further adjusted as needed.
6. A Class-Aggregation Numerical Example
In this section we give a numerical example illustrating how to study the possible aggregation
of classes into service groups. We let the classes have quite different service-time
distributions to demonstrate that aggregation is not always good. In particular, we consider
three classes of M/M input, each with common offered load 10. Classes 1, 2 and 3 have
arrival-rate and mean-service-time pairs (-
spectively. Each class separately arrives according to a Poisson process and has exponential
service times. Thus each class separately yields an M/M/s queue when we specify the number
of servers.
We consider all possible aggregations of the classes, namely, the subsets f1; 2g, f1; 3g,
f2; 3g and f1; 2; 3g as well as the classes separately. The arrival rates and offered loads of the
subgroups are just the sums of the component arrival rates and offered loads. However, the
aggregated subgroups differ qualitatively from the single classes because the service-time distributions
are no longer exponential. Instead, the service-time distributions of the aggregated
subgroups are mixtures of exponentials (hyperexponential distributions) with SCVs greater
than 1. The penalty for aggregation is initially quantified by the service-time SCV. The
service-time SCVs for classes f1; 2g, f1; 3g, f2; 3g and f1; 2; 3g are 5.05, 50.0, 5.05 and 26.4,
respectively. Consistent with intuition, from these SCVs, we see that the two-class service
group f1; 3g should not be as attractive as the other two-class service groups f1; 2g and f2; 3g.
We use the scheme in Section 5 to specify the number of servers. In particular, in each case
we let s be approximately
is the offered lead. Thus, for each class separately
we let for the two-class subgroups we let and for the entire three-class set we
more servers are used with smaller groups, we also consider the three-class
set with 39 servers, which is the sum of the separate numbers assigned to the separate classes.
We display the performance measures calculated according to Section 2 in Table 1. From
classes in server group
ES 1:0 10:0 100:0 1:818 1:980 18:18 2:703
ae 0:7692 0:7692 0:7692 0:800 0:800 0:800 0:833 0:769
s 1:0 1:0 1:0 5:05 50:0 5:05 26:4
EW 0:108 1:08 10:8 0:28 2:53 2:75 1:54 0:51
\Gamma131
\Gamma13
\Gamma5
\Gamma5
\Gamma6
\Gamma12

Table

1: Performance measures for the three classes separately and all possible aggregated
subsets in the example of Section 6.

Table

1, we see that the mean wait is about 10% of the mean service time for each class
separately. Also the probability that the wait exceeds one mean service time, P (W ? ES) is
for each class separately. In contrast, these performance measures degrade substantially
for the class with the shorter service times after aggregation. Consistent with intuition, the
performance for service group f1; 3g is particularly bad. The full aggregate service group
containing classes f1; 2; 3g performs better with 39 servers than 36, but in both cases the
performance for class 1 is significantly worse than the performance for class 1 separately.
The main point is that the approximations in Section 2 provide a convenient way to study
possible aggregations. Given a specification of performance requirements, e.g., delay constraints
it is possible to find the minimum number of
servers satisfying all the constraints (exploiting the best aggregation scheme). For example,
having the three classes separate is optimal. For the classes
separately with 12 and 14 servers, P respectively. Hence,
as indicated in Section 2, a unit change in the number of servers makes a big change in the
performance measures. The total number of servers required for the aggregate system to have
0:20 is 46, seven more than with the three classes separate.
This example also illustrates the importance of considering the service-time distribution
beyond its mean. If we assume that the aggregate system were an M/M/s system, then
the service-time SCV would be 1 instead of 26.4. Approximations (2.2), (2.3), (2.8) and (2.9)
indicate that using M/M/s model instead would underestimate the correct mean approximately
by a factor of 13.7. Using the M/M/s model for the aggregate system, we would deduce that
we only needed 37 servers in order to have 0:015). We
would also wrongly conclude that the aggregate system is better than the separate classes.
7. A Pareto-Splitting Numerical Example
In this section we illustrate the service-time partitioning by considering a numerical example
in which we split Pareto service times. We start with an M/G input consisting of a
Poisson arrival process having arrival rate and a Pareto service-time distribution as
in Example 3.2 with that it has mean 1 and SCV c 2
The offered load is 100, so that the total number of servers must be at least 101 in order
to have a stable system. Using the initial sizing formula in Section 5, we would initially let
This yields a probability of delay of P (W ?
mean delay of E(W jW ? and a mean delay of
However, the median of the chosen Pareto distribution is 0.43, so that 50% of the service
times are less than 0.43. Indeed, the conditional mean service time restricted to the interval
[0; 0:43] is 0:179. The conditional mean wait of 1.21 is about 6.8 times this mean; the
actual mean wait 0.343 is about 2 times the mean service time. These mean waits might be
judged too large for the customers with such short service requirements. Thus, assuming that
we know customer service requirements upon arrival, we might attempt to make waiting times
more proportional to service times by partitioning the customers according to their service-time
requirements.
Here we consider partitioning the customers into five subsets using the boundary points
1000. The first two boundary points were chosen to be the 50 th and 90 th
percentiles of the service-time distribution, while the last two boundary points were chosen
to be one and three orders of magnitude larger than the overall mean 1, respectively. In
particular, from formula (3.11), we find that the probabilities that a service time falls into the
interval (0; 0:43), (0:43; 2:2), (2:2; 10), (10; 1000) and (1000; 1) are 0.50, 0.40, 0.092, 0.0078
and 0:61 \Theta 10 \Gamma6 , respectively.
For each subinterval, we calculate the conditional mean and second moment given that
the service time falls in the subinterval using formulas (3.12) and (3.13), thus obtaining the
subinterval mean and second moment. The subinterval SCV is then obtained in the usual way.
We display these results in Table 2. Note that these subgroup service-time SCVs are indeed
much smaller than the original overall Pareto SCV of c 2
Given the calculated characteristics for each subinterval, we can treat each subinterval as a
separate independent M/G/s queue. The arrival rate is 100 times the subinterval probability.
The offered load, say !, is the arrival rate times the mean service time. Using the initial-sizing
formula in Section 5, we let the number of servers in each case be the least integer greater than
!. We regard this value as an initial trial value that can be refined as needed. Finally,
the traffic intensity ae is just the offered load divided by the number of servers, i.e., ae = !=s.
We display all these results in Table 2.
Next we describe the performance of each separate M/G/s queue using the formulas in
Section 2. For simplicity, here we use (2.8) for the probability of delay. Since we have chosen s
in each case to be about
!, it should be no surprise that the delay probability is nearly
the same for all groups except the last. In the last subinterval, the offered load is only 0:117,
so only one server is assigned, and the normal approximation is clearly inappropriate.
From

Table

2, we see that the mean wait EW i for each class i is substantially less than
the mean service time of that subclass. We also calculate the probability that the waiting
time exceeds the mean service time of that class, using approximation (2.10). For all classes,
consistently small.
service-time intervals
probability 0:5000 0:4004 0:0918 0:0078 0:00000061
subgroup
mean 0:1787 0:9811 3:935 19:94 1910
arrival rate 49:99 40:04 9:18 0:78 0:000061
offered load 8:94 39:28 36:12 15:54 0:117
servers 12 46 42 20 1
ae i 0:745 0:853 0:864 0:778 0:117

Table

2: Service-time characteristics and M/G/s performance measures when the original
Pareto service times are split into five subgroups.
Now we consider what happens if we aggregate some of the subgroups. First, we consider
combining the last two subgroups. We keep the total number of servers the same at 21. If
we group the last two classes together, then the new service time has mean 20.09 and SCV
5.29. Note that, compared to the (10, 1000) class, the mean has gone up only slightly from
19.94, but the SCV has increased significantly from 1.25. (The SCV is even bigger than it
was for the highest group.) The M/G/s performance measures for the new combined class
are
This combination might be judged acceptable, but the performance becomes degraded for the
customers in the (10, 1000) subgroup.
Finally, we consider aggregating all the subgroups. If we keep the same numbers of servers
assigned to the subgroups, then we obtain 121 servers instead of 110. This should not be
surprising, because the
algorithm should produce fewer extra servers with one large
group than with five subgroups. However, it still remains to examine the performance of the
original system when
:0094. The delay probability
is clearly better than with the partition, as it must be using approximation (2.3), but the
conditional mean wait is worse for the first three subgroups, and much worse for the first two.
The overall mean EW is worse for the first two subgroups, and much more for the first one.
The tail probabilities are much worse for the first two subgroups as well. Hence,
even with all 121 servers, performance in the single aggregated system might be considered far
inferior to performance in the separate groups for the first two groups.
Finally, we can clearly see here that an M/M/s model fails to adequately describe the
performance. By formulas (2.2), (2.3), (2.8) and (2.9), we see that the mean EW would be
underestimated by a factor of 11 in the aggregate system, and overestimated somewhat for
the first three service groups. Moreover, and we would incorrectly conclude that the aggregate
system must be better.
Remark 7.1. The Pareto service-time distribution in the example we have just considered
has finite variance since 2. Similar results hold if the service-time distribution has
infinite variance or even infinite mean. When the service-time distribution has finite mean but
infinite variance (when 1 ! ff - 2), the service-time variance is finite for all subclasses but the
last because of truncation. The service-time distribution for the last class then has finite mean
and infinite second moment. In the example here with one server assigned to the last class, we
then have 1. When the mean service-time is infinite for the
last class (when ff - 1), the waiting times for that class diverge to +1. However, the other
classes remain well behaved. Clearly, the splitting may well be deemed even more important
in these cases.
8. Other Model Variants
So far, we have considered service systems with unlimited waiting space. A very different
situation occurs when there is no waiting space at all. The steady-state number of busy servers
in an M/G/s/0 loss model has the insensitivity property; i.e., the steady-state distribution of
the number of busy servers depends on the service-time distribution only through its mean.
Thus, the steady-state distribution in the M/G/s/0model coincides with the (Erlang B) steady-state
distribution in the M/M/s/0 model with an exponential service-time distribution having
the same mean. Thus, the full aggregated system is always more efficient for loss systems, by
Smith and Whitt (1981).
Similarly, if there is extra waiting space, but delays are to be kept minimal, then it is natural
to use the M/G/1 model as an approximation, which also has the insensitivity property.
Hence, if our goal can be expressed in terms of the distribution of the number of busy servers
in the M/G/1 model, then we should again prefer the aggregate system.
Even for the M/G/s delay model, our approximation for the probability of experiencing any
wait in (2.3) has the insensitivity property. Hence, if our performance criterion were expressed
in terms of the probability of experiencing any wait, then we also should prefer the aggregate
system. In contrast, separation can become important for the delays, because the service-time
distribution beyond its mean (as described by the SCV) then matters, as we have seen.
So far, we have considered a stationary model. However, in many circumstances it is more
appropriate to consider a nonstationary model. For example, we could assume a nonhomogeneous
Poisson arrival process, denoted by M t , for each customer class. It is important to
note that the insensitivity in the M/G/s/0 and M/G/1 models is lost when the arrival process
becomes M t ; see Davis, Massey and Whitt (1995). The added complexity caused by the
nonstationarity makes it natural to consider the M t =G=1 model as an approximation. Since
insensitivity no longer holds, full aggregation is not necessarily most efficient. Partitioning in
this nonstationary setting can also be conveniently analyzed because the partitioning of non-homogeneous
Poisson processes produces again nonhomogeneous Poisson processes. Hence, all
subgroups behave as M t =G=s systems. For example, the server staffing and performance calculations
for each subset can be performed by applying the approximation methods in Jennings,
Mandelbaum, Massey and Whitt (1996). The formula for the mean number of busy servers at
time t in (6) there shows that the service-time distribution beyond the mean plays a role, i.e.,
where -(t) is the arrival-rate function and S e is a random variable with the service-time
equilibrium-excess distribution, i.e.,
ES
also see Eick, Massey and Whitt (1993). The linear approximation
in (8) of Eick et al. shows the first-order effect of the service-time SCV.
So far, we have only considered Poisson arrival processes. We chose Poisson arrival processes
because, with them, it is easier to make our main points, and because they are often
reasonable in applications. However, we could also employ approximation methods to study the
partitioning of more general (stationary) G/G inputs. In particular, we could use approximations
for aggregating and splitting of arrival streams in the queueing network analyzer (QNA)
in Whitt (1983) to first calculate an SCV for the arrival process of each server group and then
calculate approximate performance measures. When we go to this more general setting, the
arrival-process variability then also has an impact. With non-Poisson arrival processes, the
partitioning problem nicely illustrates how a performance-analysis software tool such as QNA
can be conveniently applied to study design problem. In that regard, this paper parallels our
application of QNA to study the best order for queues in series in Whitt (1985b).
It should be noted, however, that the QNA formulas for superposition (aggregation) and
splitting assume independence. The independence seems reasonable for aggregation, but may
fail to properly represent splitting. For aggregation, the assumed independence is among the
arrival processes for the different classes to be superposed, which we have already assumed in
the Poisson case.
For splitting, we assume that the class identity obtained by splitting successive arrivals are
determined by independent trials. Thus, if c 2
a is the original arrival-process SCV and p i is the
probability that each arrival belongs to class i, then the resulting approximation for the class-i
i from Section 4.4 of Whitt (1983) is
which approaches the value 1 as exact for renewal processes and is
consistent with limits to the Poisson for more general stationary point processes. However, in
applications it is possible that burstiness (high variability) may be linked to the class attributes,
so that a cluster of arrivals in the original process all may tend to be associated with a common
class. That means the independence condition would be violated. Moreover, as a consequence,
the actual SCV's associated with the split streams should be much larger than predicted by
(8.4). In such a situation it may be better to rely on measurements, as discussed in Fendick
and Whitt (1989).
9. Conclusions
We have shown how to evaluate the costs and benefits of (1) partitioning an M/G/s system
into independent subsystems by classifying customers according to their service times, assuming
that they can be estimated upon arrival, and (2) combining independent M/G/s systems with
different service-time distributions into larger aggregate M/G/s systems. When the service-time
distributions are nearly the same in component systems, then greater efficiency usually
can be obtained by combining the systems as indicated in Smith and Whitt (1981). On the
other hand, if the service-time distributions are very different, then it may be better not to
combine the systems. Previously established simple approximations for M/G/s performance
measures make it possible to evaluate alternatives quantitatively very rapidly. Afterwards, the
conclusions can be confirmed by more involved numerical algorithms, computer simulations or
system measurements.



--R

"Exponential Approximations for Tail Probabilities, I: Waiting Times,"
"An Exact FCFS Waiting Time Analysis for a General Class of G/G/s Queueing Systems,"
"Sensitivity to the Service-Time Distribution in the Nonstationary Erlang Loss Model,"
"The Physics of the M t =G=1 Queue,"

"Heavy-Traffic Limits for Queues with Many Exponential Servers,"
"Server Staffing to Meet Time-Varying Demand,"
"Queueing Processes Associated with Airline Passengers Check- In,"
"On Pooling in Queueing Networks,"
"An Approximation Formula L
"An Algorithm for Ph/Ph/c Queues,"
"A Numerical Solution for the Multi-Server Queue with Hyperexponential Service Times,"
"Resource Sharing for Efficiency in Traffic Systems,"
"The Queueing Network Analyzer,"
"Uniform Conditional Variability Ordering of Probability Distributions,"
"The Best Order for Queues in Series,"
"Understanding the Efficiency of Multi-Server Service Systems,"
"Approximations for the GI/G/m Queue,"
--TR

--CTR
Hui-Chih Hung , Marc E. Posner, Allocation of jobs and identical resources with two pooling centers, Queueing Systems: Theory and Applications, v.55 n.3, p.179-194, March     2007
Gans , Yong-Pin Zhou, Call-Routing Schemes for Call-Center Outsourcing, Manufacturing & Service Operations Management, v.9 n.1, p.33-50, January 2007
resource sharing;multiserver queues;service-system design;queues;Service Systems with Express Lines;service systems