|
Article Excerpt
1. Introduction
Queueing networks with finite buffers have been studied extensively in the literature (see, for example, Perros, 1989; Perros and Altiok, 1989; Dallery and Gershwin, 1992). These models have many applications in manufacturing, communication and computer systems. In most cases queueing networks with finite buffers are intractable; therefore the majority of the literature is devoted to approximations of performance characteristics such as throughput and mean sojourn times. To the best of our knowledge, the average errors in throughput and mean sojourn time approximations reported in the literature are usually around 5%. Typically, the errors are large (up to 30%) for systems with small buffers (see, for example, Van Vuuren et al. (2005)). Unfortunately, in manufacturing systems, it is common to have small buffers. Hence, good approximations for such systems are definitely needed. In this paper we propose a method for the approximative analysis of single-server tandem queues with general service times, small finite buffers and Blocking After Service (BAS). We are interested in the queue length distribution of each buffer; these distributions may be used to determine the throughput and mean sojourn time.
In this paper we consider a tandem queue (L) with N servers in tandem and N - 1 buffers [B.sub.i], i = 1,..., N - 1, of size [b.sub.i] in between. The servers are labeled [M.sub.i], = 0,..., N - 1. The random variable [S.sub.i] denotes the generic service time of server [M.sub.i]; [S.sub.i] is generally distributed with rate [[mu].sub.i] and squared coefficient of variation [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Each server can serve one customer at a time. Server [M.sub.0] is never starved and we consider the BAS blocking protocol. Figure 1 shows a tandem queue with four servers in tandem.
The method to approximate the queue length distribution of the buffers is based on decomposition of the tandem queue into single-buffer subsystems. Each buffer [B.sub.i] is considered in isolation, where to take into account the relation with the upstream line and downstream line, the service times of server [M.sub.i - 1] in front of buffer [B.sub.i] and server [M.sub.i] after buffer [B.sub.i] are adapted by including possible starvation of [M.sub.i - 1] before service and possible blocking of [M.sub.i] after service. It is important to note that dependencies between service time and blocking after service are carefully taken into account; this seems to be the most important source of performance improvement of the proposed approximation. By fitting the first two moments, the distributions of the service times including starvation and blocking are approximated by a simple phase-type distributions, the parameters of which are tuned by means of an iterative algorithm.
Decomposition techniques for single-server queueing networks have also been used by Gershwin (1987), Kerbache and MacGregor Smith (1987) and Perros (1994). Van Vuuren et al. (2005) extended the decomposition technique to multi-server tandem queues with finite buffers, and showed that the quality of the approximation substantially degraded when the buffers became small, i.e., errors can get as large as 30% in the throughput and mean sojourn time.
The results of the current method will be compared with the ones of Van Vuuren et al. (2005) and also with the ones of the approximation developed by Helber (2005), which is the most recent and best method available; the comparison shows that the current method performs substantially better than former methods, with average errors of around 1%.
This paper is organized as follows. In Section 2 we explain the decomposition of the tandem queue into subsystems. In the section thereafter we take a closer look al the subsystems. Section 4 describes the iterative algorithm. Numerical results are presented in Section 5 and they are compared with simulation and other approximation methods. Finally, Section 6 contains some concluding remarks.
2. Decomposition of the tandem queue
We decompose the original tandem queue L into N - 1 subsystems [L.sub.1],[L.sub.2],..., [L.sub.N - 1] Subsystem [L.sub.1] consists of buffer [B.sub.i] of size [b.sub.i], an arrival server in front of the buffer, and a departure server after the buffer. In Fig. 2 we show the decomposition of line L of Fig. 1.
[FIGURE 1 OMITTED]
[FIGURE 2 OMITTED]
The arrival server of subsystem [L.sub.i] is, of course, server [M.sub.i - 1] but, to take into account the connection with the upstream line, its service time is different from [S.sub.i - 1]. The random variable [A.sub.i] denotes the service time of the arrival server in subsystem [L.sub.i], i = 1,..., M - 1. This random variable represents the original service time [S.sub.i - 1] of server [M.sub.i - 1] including possible starvation of this server before the service start. Similarly, the random variable [D.sub.i], denotes the service time of the departure server in subsystem [L.sub.i] it represents the service time [S.sub.i] of server [M.sub.i] including possible blocking of this server after service completion. In the next section we elaborate further on the arrivals at and the departures from the subsystems.
3. Subsystems
In this section we describe how the service times of the arrival and departure servers in subsystem [L.sub.i] are modeled. Also, we describe the method to fit the first two moments, the computation of the first two moments of the maximum of two independent Erlang random variables and the detailed analysis of each subsystem.
3.1. Arrivals at and departures from the subsystems
In the description of the service time [A.sub.i] of arrival server [M.sub.i - 1] of subsystem [L.sub.i] we try to use all the information available. Note that an arrival in buffer [B.sub.i], i.e., a customer being served by [M.sub.i - 1] moving to buffer [B.sub.i], when space becomes available, corresponds to a departure from the upstream subsystem [L.sub.i - 1]. Just after this departure, two situations may occur: subsystem [L.sub.i - 1] is empty with probability [q.sub.i - 1.sup.e], or it is not empty with probability 1 - [q.sub.i - 1.sup.e] (where, of course, we do not count the customer at arrival server [M.sub.i - 2] as being in [L.sub.i - 1]. In the former situation, server [M.sub.i - 1] has to wait for a residual service time of arrival server [M.sub.i - 2] of subsystem [L.sub.i - 1], denoted as R[A.sub.i + 1], before the actual service can start. In the latter situation, the actual service [S.sub.i - 1] can start immediately. Hence, the service time [A.sub.i] is equal to R[A.sub.i + 1] + [S.sub.i - 1] with probability [q.sub.i - 1.sup.e] and equal to [S.sub.i - 1] with probability 1 - [q.sub.i - 1.sup.e]. Figure 3 shows a schematic representation of the service time [A.sub.i].
We now describe the service time [D.sub.i], of the departure server [M.sub.i] of subsystem [L.sub.i]. Here we distinguish between the service time of a customer for which the previous customer left behind an empty subsystem L, or not; the reason for doing so is that, when time elapses between the departure of the previous customer and the service start of the current customer, it will be less likely that the current one will be blocked. Let the random variable [D.sub.i.sup.e] denote the service time of departure server [M.sub.i] if just after the previous service completion subsystem [L.sub.i] is empty; [D.sub.i.sup.ne] is the service time if [L.sub.i], is not empty.
[FIGURE 3 OMITTED]
To describe the service times [D.sub.i.sup.e] and [D.sub.i.sup.ne] we condition on the situation in...
|
