Transient solutions of some multiserver queueing systems with finite spaces

The purpose of this paper is to provide explicit transient solutions for the multiserver queueing system Geom ( n )/ Geom ( n )/ c / N + c . The method proposed here can also be used for obtaining transient solutions of Markov chains having the transition matrix of Hesselberg type. To support this, we also consider a more complex model such as GI / M / c / N + c . In our analysis, we use eigenvalues and generalized eigenvectors of transition probability matrices. Since we use the Jordan canonical form from linear algebra, the method is good even if the eigenvalues are repeated. Numerical procedures for computations involved in various examples are also provided.     

Extension of the optimality of the threshold policy inheterogeneous multiserver queueing systems

The authors extend the validity of some results on the optimal control of two-server queueing models with service times of unequal distribution, operating in continuous or discrete time. The distribution of arrivals can be arbitrary subject to some conditions. Both discounted and long-run average costs are considered. Dynamic programming and probabilistic arguments are used to establish the assertion that the optimal policy is of threshold type, i.e. the slower server should be utilized only when the queue length exceeds a certain threshold value     

Stability analysis of multiserver discrete-time queueing systems with renewal-type server interruptions

For many queueing systems, the server is not continuously available. Service interruptions may result from repair times after server failures, planned maintenance periods or periods during which customers from other queues are being served. These service interruptions cause an overall performance degradation which is most striking when interruptions can start while a customer is being served and his service has to start all over after the interruption. This is the so-called preemptive repeat service discipline. This paper investigates stability conditions for discrete-time queueing systems with preemptive server interruptions. Under renewal assumptions for arrival, service and interruption processes, sufficient conditions for the positive recurrence of the single-server and multiserver queueing processes are established for the preemptive repeat different and the preemptive resume service disciplines.     

On a multiserver markovian queueing system with balking and reneging

In this paper a multi-server queueing model with balking and reneging is considered. Steady-state distribution of the number of customers in the system is obtained. An expression for the average loss of customers during a fixed duration of time is also advanced.     

An enhanced algorithm to solve multiserver retrial queueing systems with impatient customers

The homogenization of the state space for solving retrial queues refers to an approach, where the performance of the M/M/c retrial queue with impatient customers and c servers is approximated with a retrial queue with a maximum retrial rate restricted beyond a given number of users in the orbit. As a consequence, the stationary distribution can be obtained by the matrix-geometric method, which requires the computation of the rate matrix. In this paper, we revisit an approach based on the homogenization of the state space. We provide the exact expression for the conditional mean number of customers based on the computation of the rate matrix R with the time complexity of O(c). We develop simplified equations for the memory-efficient implementation of the computation of the performance measures. We construct an efficient algorithm for the stationary distribution with the determination of a threshold that allows the computation of performance measures with a specific accuracy.     

One multiserver mixed queueing system with the limited waiting time

In this paper, a M/G/n/c multiserver queueing system with basic and standby servers is studied. Customers servicing is disturbed by failures of servers that make up a simplest flow. After the failure, the server needs a random time for renewal. It is also assumed that customers have limited, exponentially distributed waiting time in the system. The system is studied in both stationary and nonstationary modes.     

On approximating the generalized occupancy of the G/M/K queueing system

The G/M/K is one of very few multiserver queueing systems for which analytical results exist. In 1951 Kendall [4] showed how to compute the steady-state probabilities of a G/M/K queueing system. Later, Takacs [6] suggested an iterative procedure for the evaluation of a needed component in Kendall's scheme; namely, the generalized occupancy ω^*. However, Takàcs' algorithm requires the computation of a general integral for each of its interations.In this paper we propose a simple and explicit approximation for the generalized occupancy of the G/M/K system. Several numerical results are also included.     

A general solution for multichannel queueing systems with ordered entry

This paper presents a general solution of multichannel ordered entry queueing systems with heterogeneous servers and storage. It is assumed that the arrivals follow a Poisson distribution and the service times are exponentially distributed (M/M/n queueing system). A computer program was developed to solve this queueing system numerically. Measures of the system's performance as well as the steady-state probabilities are evaluated.     

On fluid queueing systems with strict priority

We consider priority fluid queueing systems where high-priority class has strict priority access to service. Sample path analysis tools, such as Poisson counter driven stochastic differential equation, are employed to study system queueing behavior in steady state. We are able to obtain various analytical results for different fluid traffic models and system configurations. Those results can be used as a general rule of thumb in buffer dimensioning and other traffic engineering issues.     

A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks

This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are block-structured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures can be calculated.Scope and purposeThe exact analysis of queueing networks with multiple servers at each workstation and finite capacities of the intermediate queues is extremely difficult as for even the case of exponential operation (service or processing) times the Markovian chain that models the system consists of a huge number of states which grows exponentially with the number of stations, the number of servers at each station and the queue capacity of each intermediate queue of the resulting system. The scope and purpose of the present paper is to analyze and provide a recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks. By applying the proposed algorithm one may create the transition matrix of a K-station queueing network for any K. This process allows one to obtain the exact solution of the resulting large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures of the system can be obtained.     

GSPN models of Markovian multiserver multiqueue systems

The paper presents exact results for the average customer waiting and sojourn times in Markovian systems comprising a number of finite-capacity queues cyclically attended by several servers. The system behaviour is described using generalized stochastic Petri nets (GSPN), and the performance indices are obtained numerically by means of GreatSPN, the software tool for the analysis of GSPN. The average waiting and sojourn times of customers in Markovian multiserver multiqueue systems are computed exactly in this paper for the first time: they were previously estimated for similar systems by other authors only through approximate models.     

Accuracy of approximating queueing network departure processes with independent renewal processes

A distributed and fully symmetric solution is presented for the distributed termination problem. In contrast to the existing solutions, the above solution does not require a predesignated process to detect termination. The case of asynchronous communications is also discussed.     

On queueing systems with a fractional number of devices

Queueing systems with several servers and a special discipline whereby demands are successively received by servers until the servicing is completed are considered. Among these systems, there are such systems whose characteristics constantly depend on a certain positive parameter. Given integer values of the latter, the waiting probability and average sojourn time coincide with those calculated using the Erlang C formula. Therefore, these systems can be considered as generalizations of the classical M/M/s system to a fractional number of servers.     

On performance characteristics for queueing systems with heterogeneous servers

The problem of optimal control for queueing system (QS) with heterogeneous servers was considering by many authors. In [8] it was shown that the optimal with respect to the number of jobs in the system minimization policy is a threshold type one and it obliges to use the fastest free server if necessary. However, calculation of performance characteristics under optimal policy and analysis of its preference before some other policies rest out of the investigators’ interests. The purpose of this paper is to analyze a multi-server heterogeneous exponential queue. We demonstrate the methods for the calculation of the steady-state probabilities and deriving the waiting and sojourn time distributions. Some performance characteristics of such a system under the optimal control policy are calculated and compared with the same characteristics for the model under other heuristic control policies, e.g., the usage of the Fastest Free Server (FFS) or Random Server Selection (RSS).     

Analysis of threshold-based batch-service queueing systems with batch arrivals and general service times

Most research concerning batch-service queueing systems has focussed on some specific aspect of the buffer content. Further, the customer delay has only been examined in the case of single arrivals. In this paper, we examine three facets of a threshold-based batch-service system with batch arrivals and general service times. First, we compute a fundamental formula from which an entire gamut of known as well as new results regarding the buffer content of batch-service queues can be extracted. Second, we produce accurate light- and heavy-traffic approximations for the buffer content. Third, we calculate various quantities with regard to the customer delay. This paper thus provides a whole spectrum of tools to evaluate the performance of batch-service systems.     

On the hardness of approximating label-cover

The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724-733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29-40] to Label-Cover showing it NP-hard to approximate to within 2^{(logn)1−o(1)}. This improves upon the best previous hardness of approximation results known for this problem.We also consider the Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307-320]. We show some hardness results for certain levels in this hierarchy, and place Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of Label-Cover in it.     

On the hardness of approximating Max-Satisfy

Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over Q. We prove that unless NP⊂BPP Max-Satisfy cannot be efficiently approximated within an approximation ratio of 1/n1−?, if we consider systems of n linear equations with at most n variables and ?>0 is an arbitrarily small constant. Previously, it was known that the problem is NP-hard to approximate within a ratio of 1/nα, but 0<α<1 was some specific constant that could not be taken to be arbitrarily close to 1.