1. Introduction

A variety of simulation models, such as for manufacturing, telecommunications and service logistics includes serial structures of successive service stations. These service stations quite generally have finite capacity limitations on the number of jobs that they can accommodate. Unfortunately, analytic expressions, most notably of so-called product-form, are usually not available under these finite capacity constraints.

Nevertheless, by modifying the system, for the purpose of its evaluation, an analytic solution might be regained which may lead to rough but secure performance bounds, such as for a loss probability, throughput or mean delay. This approach has been described in Van Dijk (1993), Chapter 4, and extended in Van Dijk and Van der Sluis (2002) to queuing networks with finite clusters of stations.

So far, however, this approach has not been advocated for the purpose of simulation. More precisely, as will be outlined more detailed in Section 4 and despite their inaccuracy, these analytic performance bounds can be useful for simulation such as for:

1. determining an order of magnitude (see Section 4.1);
2. providing secure bounds (see Section 4.2);
3. verification purposes (see Section 4.3);
4. insensitivity results (see Section 4.4);
5. optimization (see Section 4.5).

The objective of this paper, therefore, is to promote and illustrate this modification approach as of possible interest to support the simulation for systems of a sequential or assembly line structure.

2. An instructive example

This section provides an instructive and generic example to illustrate the modification approach and the nature of its results. In the next section, four more examples are briefly presented. A more extended outline and formal support of the approach can be found in Van Dijk (1993) and Van Dijk and Van der Sluis (2002).

Consider a simple assembly line structure with four service stations, numbered 1, ..., 4 and finite capacity constraints T₁ for the total number of jobs at stations 1 and 2 (cluster1) and T₂ at stations 3 and 4 (cluster 2) (Figure 1).

Figure 1.

Finite tandem clusters.

Full figure and legend (5K)

The system has an arrival rate of jobs per unit of time and assume that station i has (an exponential) service rate _i(k) when k jobs are present. Let n_i denote the number of jobs at station i, i=1, ..., 4 and t_j the total number of jobs at cluster j, j=1, 2 (t₁=n₁+n₂ and t₂=n₃+n₄). When the first cluster is saturated (t₁=T₁), an arriving job is lost. When the second cluster is saturated (t₂=T₂), the service at cluster 1 (that is at both stations) is stopped. As simple as the system may look to analyse, there is no simple expression for the loss probability B or the throughput H=(1-B).

As outlined in Van Dijk and Van der Sluis (2002), in order for a system to exhibit a closed product-form expression, a notion of both balance per station (as also presented in Van Dijk, 1993) and of balance per cluster (that is, as if a cluster is regarded as one aggregated station) is to be satisfied. But clearly, both notions are violated in the present example, since when t₁<T₁ but t₂=T₂:

• the out-rate of stations 1 and 2 and the out-rate of cluster 1 are necessarily equal to 0 while the in-rate for station 1 (and possibly also for 2) and for cluster 1 are positive.

The following artificial modification to enforce these notions can therefore be suggested:

• When cluster 2 is saturated (t₂=T₂): stop the input.
• When cluster 1 is saturated (t₁=T₁): stop cluster 2 (that is, stop stations 3 and 4).

Indeed, with n=(n_l, n₂, n₃, n₄) the state description, e_i the unit vector for the ith component and 1_{A} the indicator of event A, under the above modification one easily verifies the station balance equations at S_U the set of admissible states:

as

by the product-form:

with c a normalizing constant. Clearly, the modification leads to an upper bound B_UB for the loss probability. Conversely, also a lower bound product-form modification B_L can be suggested. Hence,

Below some numerical results are given for the case of single server stations. Here _i represents the service speed of station i, B_L and B_U are the easily obtained lower and upper bound for the blocking probability, B_av=(B_L+B_U)/2 and B is obtained by numerical computation (Table 1).

Table 1 - Lower and upper bounds of the loss probability B (and throughput H by H=(1-B)) for finite two-cluster tandem example.

Full table

3. Further illustrative examples

In this section, some more examples will be provided, in line with the instructive example in Section 2, to illustrate the potential of the modification approach. For each of these examples there is no analytic expression known while the modifications guarantee closed product-form expressions similar to (2). These in turn will lead to easily computable bounds similar to (3). Some numerical results will be included to indicate the (in)accuracy and order of magnitude as of possible interest for simulation, as will be outlined in more detail in Section 4.

3.1. A nested blocking structure

As a nested analogue of the example from Section 2, consider an 8-station production line. In addition to the total cluster constraints T₁ for stations 1–4 and T₂ for stations 5–8, we can also allow capacity constraints N_i for each pair of stations (2_i-1, 2_i) i, i=1, ..., 4 (Figure 2) .

Figure 2.

Nested blocking structure.

Full figure and legend (6K)

The following modification now secures (2):

• When t₁=T₁, stop all stations 5–8.
• When t₂=T₂, stop all stations 1–4 and arrivals.
• When n_2i-1+n_2i=N_i, stop arrivals and all other stations j2_i-1, 2_i.

Clearly, this modification leads to an upper bound B_U for the loss probability B. Conversely, a lower bound B_L can be suggested. Some numerical results are presented below with _i the service parameter of each single server station i (Table 2).

Table 2 - Results for the nested blocking structure (=1).

Full table

3.2. A cluster with parallel stations

This example contains a random routing to either one of two stations in parallel within one cluster with a capacity constraint T for the total number of jobs at stations 2 and 3, next to capacity constraints N_i at each station i, i=1, ..., 4 (Figure 3).

Figure 3.

Parallel structure.

Full figure and legend (4K)

By regarding the cluster as one aggregated station as in Section 2, the following modifications lead to a product-form expressions:

• Stop arrivals and all stations either when one of stations (n_i=N_i) or the cluster (n₂+n₃=T) is saturated, or
• stop arrivals when the total number of jobs is equal to N₁+T+N₄=S, while stations 1 or 4 or stations 2 and 3 together may contain up to S jobs.

Clearly, the first modification leads to an upper bound B_U and the second to a lower bound B_L for the loss probability B of the original system. Some numerical results are shown in Table 3.

Table 3 - Results for the finite cluster with parallel stations (=1).

Full table

3.3. An overflow system

Consider two finite clusters in parallel with arrivals at cluster 1. If a job cannot enter cluster 1 it is rerouted to cluster 2. Each cluster consists of two finite stations in tandem. In addition to the total cluster constraints T₁ and T₂, we also allow capacity constraints N_i for each individual station i, i=1, ..., 4. We assume that ₁₃ and ₂₄ (Figure 4).

Figure 4.

Parallel nested structures.

Full figure and legend (5K)

For this example, the so-called notion of cluster balance is violated when cluster 2 is busy while cluster 1 is not saturated. In that case the outflow at cluster 2 is positive, but the in-rate is 0. The following two modifications are therefore suggested:

• Stop both stations in cluster 2 when cluster 1 is not saturated (t₁<T₁), or
• assign arriving jobs randomly to either one of the clusters proportional to the free buffer capacity at the two clusters.

By the first modification cluster 2 is slowed down and kept more congested. The arrival loss probability will thus be enlarged which leads to an upper bound B_U for the loss probability B of the original system. With the second modification, the faster overflow cluster is used more frequently than in the original system, which leads to a lower bound B_L (Table 4).

Table 4 - Results for parallel finite clusters with overflow.

Full table

3.4. A model with breakdowns

Reconsider two finite clusters in tandem, both of which are subject to breakdowns. In addition to the cluster constraints T₁ and T₂, we assume repair and breakdown rates ₁₀ and ₁₁ for cluster 1, and similarly, ₂₀ and ₂₁ for cluster 2 (Figure 5).

Figure 5.

Clusters with breakdowns.

Full figure and legend (4K)

Clearly, cluster balance is violated when either cluster is down. In addition to the modifications as for the instructive example in section 2, for an upper or lower bound respectively, the following two modifications are therefore added:

• Also stop both stations in cluster i when cluster j is down (ji), or
• the breakdown rate for both clusters is 0 (breakdowns do not take place).

Again, the first modification leads to an upper bound B_U and the second to a lower bound B_L for the loss probability B of the original system. Some numerical results are shown in Table 5.

Table 5 - Results for finite clusters with breakdowns (=1).

Full table

4. Applications for simulation

4.1. Order of magnitude

The values B_L and B_U give a first rough order of magnitude, say whether the loss probability, for a given parameter configuration of arrival and service rates _i and capacity numbers N_i and T_i, is in the order of at least or at most 1, 5, 10 or 20%. In fact, the average value B_A=(B_L+B_U)/2 even turns out to be reasonably accurate allover for the exact numerical value B in the exponential case. This first order estimate can be useful for simulation for a first choice of parameter settings.

4.2. Secure bounds

Simulation results have to rely upon confidence intervals and thus always encounter some (small) uncertainty on the 'real' value. Any guaranteed lower and upper bound for the exact value, even though inaccurate and under exponential assumption (with a possible relaxation as under 4.4), will thus be supportive. More specifically, a secure upper bound for the loss probability may typically be of practical interest so as to dimension the capacity numbers N_i and/or T_i such as to keep the loss probability under some percentage target. Simulation will then be required to estimate the performance under these numbers for the original system of interest.

4.3. Verification

The modification approach leads to detailed analytic expressions for the steady state probabilities of detailed state descriptions as of the form (2). By including this modification in the simulation model and checking one or a few specific state results, for example, the probability for a complete empty system or for the loss probability, up to confidence levels 100% accurate verification of the simulation program is thus obtained.

4.4. (In)sensitivity

Under specific disciplines, such as a processor sharing, multi-server loss or single server last-come first-served discipline, the product-form expressions as in (2) will be insensitive to service distributional forms. That is, the expressions only depend on the service distributions by their means and thus without exponentiality assumption. For example, in the situation from Section 2 and with processor sharing disciplines at both stations at cluster 2 (stations 3 and 4) expression (2), and thus also the bound (3), also apply for arbitrary non-exponential services with means _i^-1 at station i=3, 4. For simulation, this so-called insensitivity property can be fruitful in several ways:

1. Again, it can be used for verification purposes of the simulation program by including the modification as an option as well as more realistic non-exponential services. Again, a 100% exact verification (up to confidence levels) is obtained.
2. As the modifications are insensitive also the bounds B_L and B_U can be expected to be insensitive. As a consequence, an insensitive bandwidth is obtained for the performance measure of interest for arbitrary service distributions. Also the simulation results of the original model and for arbitrary distributions should thus be captured (up to their confidence inaccuracies) by this bandwidth.
3. As the average value B_A=(B_L+B_U)/2, which appear to approximate the 'real' value reasonably well in the exponential case, will adopt this insensitivity property, also the 'real' value can be expected to be 'rather' insensitive. For simulation purposes this implies that no detailed data or service distributional fittings are required other than a reasonably accurate estimate of their means.

4.5. An optimal design example

Reconsider the finite cluster tandem example from Section 2 in which the numbers T₁ and T₂ are still be determined by trading off capacity costs (T₁+T₂)² and opportunity losses 1000B due to rejections. Based upon the lower and upper bounds for the loss probability, lower and upper bound curves for the costs are easily computed (Figure 6). Despite the large discrepancy between the lower and upper bound values, the qualitative curving behaviour seems to almost pinpoint the same optimal number (9 or 10). A simulation can thus at first instance be restricted to these numbers. If one wishes to simulate more, with 100% certainty the optimal number is within the region 4–16.

Figure 6.

Optimal region.

Full figure and legend (52K)

5. Conclusion

A simple modification approach is presented to secure analytic (lower and upper) bounds for the loss percentage (and throughput) of simple but unsolvable finite production systems with blocking. The approach can be useful to support the simulation of these systems such as for verification, dimensioning, sensitivity and optimization purposes. Its application and extension to more complex structures seems of interest for logistical simulations.

References

1. Van Dijk N.M. (1993). Product Forms for Queueing Networks: A System's Approach. Wiley, New York.
2. Van Dijk N.M. and Van der Sluis E. (2002). Simple product-form bounds for queueing networks with finite clusters. Annals of Operations Research 113: 175–195. | Article |