Optimal NT policies for M/G/1 system with a startup and unreliable server

This paper studies the control policies of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers are served in the queue exhaustively, the server immediately takes a vacation and operates two different policies: (i) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the completion period. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. Furthermore, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We analyze the system characteristics for each scheme. The total expected cost function per unit time is developed to determine the optimal thresholds of N and T at a minimum cost.     

Entropy maximization and NT vacation M/G/1 model with a startup and unreliable server: comparative analysis on the first two moments of system size

We consider the control policy of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers have been served in the queue, the server immediately takes a vacation and operates an NT vacation policy: the server reactivates as soon as the number of arrivals in the queue reaches a predetermined threshold N or when the waiting time of the leading customer reaches T units. In such a variant vacation system, the steady-state probabilities cannot be obtained explicitly. Thus, the maximum entropy principle is used to derive the approximate formulas for the steady-state probability distributions of the queue length. A comparitive analysis of two approximation approaches, using the first and the second moments of system size, is studied. Both solutions are compared with the exact results under several service time distributions with specific parameter values. Our numerical investigations demonstrate that the use of the second moment of system size for the available information is, in general, sufficient to obtain more accurate estimations than that of the first moment.     

Modelling manufacturing systems: A birth-death approach

An approximation method for modelling a manufacturing system is introduced. The system is considered as a queueing network, where each queue is limited in size, and interarrival and processing times are exponentially distributed. The birth-death approach is considered and an approximation method to reduce the dimension of the model is developed. The results are the marginal probability distribution of the number of units in each queue; other performance indices, such as mean queue lengths, utilizations of the working stations, and throughput can be easily obtained. The general procedure is applied to model, for example, queues in tandem, a split node, and a more complex network of queues. Simulation and, when possible, comparison with the exact solution show an acceptable error level of the proposed method.     

The workload-dependent MAP/PH/1 queue with infinite/finite workload capacity

We propose a numerical algorithm for finding the steady-state queue occupancy distribution for a workload-dependent MAP/PH/1 queue in which the arrival process and the service rate depend continuously on the instantaneous workload in the system. Both infinite and finite queue capacity scenarios are considered, including partial rejection and complete rejection policies for the latter. Using discretization, this system is approximately described by a multi-regime Markov fluid queue for which numerical algorithms are available. The computational complexity of the proposed method is linear in the number of regimes used for discretization. We provide numerical examples to validate the proposed approach.     

On the M/Ck/1 queue

We obtain the exact analytic expression of the probability distribution of the number of units in a single server queue with Poisson arrivals and Coxian service time distribution (notated as M/C_k/1). A recursive procedure for calculating this probability distribution is given. The well-known queues M/E_k/1 and M/D/1 are re-derived as special cases of the M/C_k/1 queue. Finally, the cases of M/C₂/1 and M/C₃/1 are fully worked out.     

Combining a maintenance center M/M/c/m queue into the economic production quantity model with stochastic machine breakdowns and repair

This article considers a production system in which “m” identical machines produce nonidentical products at production rates. Products made by each machine are on the other hand consumed at a specific demand rate. Machines may be affected by unwanted breakdowns. Machines break down according to a Poisson distribution with equal rates and the failed machines are sent to maintenance center for repair which is consisted of “c” servers or servicemen. However, Number of machines is greater than number of servicemen (m > c). Hence, if the number of failed machines is greater than that of servicemen, the machines have to be put in a queue. Machines are put in one queue with the order of queue being FCFS. The queue has a typical M/M/c/m system. If machines are broken down during production, shortage will occur. This problem has been considered to obtain a single production cycle for the machines and an optimum number of the servers such that costs are minimized. For this purpose, distribution of waiting time for machines in repair center is calculated and a cost function is formed. Steepest descent and direct search methods are applied in this work to obtain optimal production cycle and maintenance servers, respectively. The proposed methods are studied using a comprehensive example.     

Combining a maintenance center M/M/c/m queue into the economic production quantity model with stochastic machine breakdowns and repair

This article considers a production system in which “m” identical machines produce nonidentical products at production rates. Products made by each machine are on the other hand consumed at a specific demand rate. Machines may be affected by unwanted breakdowns. Machines break down according to a Poisson distribution with equal rates and the failed machines are sent to maintenance center for repair which is consisted of “c” servers or servicemen. However, Number of machines is greater than number of servicemen (m > c). Hence, if the number of failed machines is greater than that of servicemen, the machines have to be put in a queue. Machines are put in one queue with the order of queue being FCFS. The queue has a typical M/M/c/m system. If machines are broken down during production, shortage will occur. This problem has been considered to obtain a single production cycle for the machines and an optimum number of the servers such that costs are minimized. For this purpose, distribution of waiting time for machines in repair center is calculated and a cost function is formed. Steepest descent and direct search methods are applied in this work to obtain optimal production cycle and maintenance servers, respectively. The proposed methods are studied using a comprehensive example.     

Influence of the Limited Service Capacity of the Inspection Station on the Control Policy of an Automatized Production System

The influence of the limited capacity of an inspection station on the control policy is studied for a job shop manufacturing process. The production system and the control station are described by queue models M/G/1 and G/G/1, respectively. The deterministic sampling rate is obtained which, in case of breakdown, minimizes the number of defective units.     

Bounds estimation and practical stability of AIMD/RED systems with time delays

The Additive Increase and Multiplicative Decrease (AIMD) congestion control algorithm of TCP deployed in the end systems and the Random Early Detection (RED) queue management scheme deployed in the intermediate systems contribute to Internet stability and integrity. Previous research based on the fluid-flow model analysis indicated that, with feedback delays, the TCP/RED system may not be asymptotically stable when the time delays or the bottleneck link capacity becomes large [3]. However, as long as the system operates near its desired equilibrium, small oscillations around the equilibrium are acceptable, and the network performance (in terms of efficiency, loss rate, and delay) is still satisfactory. In this paper, we study the practical stability of AIMD/RED system with feedback delays and with both homogeneous and heterogeneous flows. We obtain theoretical bounds of the flow window size and the RED queue length, as functions of the number of flows, link capacity, RED queue parameters, and AIMD parameters. Numerical results with Matlab and simulation results with NS-2 are given to validate the correctness and demonstrate the tightness of the derived bounds. The analytical and simulation results provide important insights on which system parameters contribute to higher system oscillations and how to set parameters (such as buffer size and queue management parameters) to ensure system efficiency with bounded delay and loss. Our results can also help to predict and control the system performance for Internet with higher data rate links multiplexed with heterogeneous flows with different parameters.     

On the overflow processes from the PH1 + PH2/M/S/K queue with two independent PH-renewal inputs

This paper presents an analysis of overflow processes from a PH₁ + PH₂/M/S/K queue having two independent phase type renewal input streams. Both the superposed overflow process and individual overflow processes for the PH₁- and PH₂-streams are analyzed using first passage time distributions for the number of customers in the system. Each overflow process is characterized as a Markov renewal process. The nth moment of the number of customers in an infinite server group to which these overflows have been offered is derived using a theory for the MR/M/∞ queue with a Markov renewal input. The numerical examples for means and variance-to-mean ratios (peakednesses) of the individual overflow streams are given for an H₂ + H₂/M/S/S queue with interrupted Poisson inputs, which is a vital model for telephone network planning. In addition, overflow traffic characteristics are discussed by using these examples.     

Finite capacity priority queues with potential health applications

The queuing processes of interest in this paper are that of waiting lines with two priorities and multiple service channels. The arrival process is assumed Poison and the service time distribution is negative exponential. Arriving units enter service if there is at least one idle channel, otherwise they join a finite queue and are served according to a non-preemptive priority discipline. If a low priority arriving unit finds the queue full, it is not allowed to enter the system and is considered “blocked” or lost. In the first model a high priority arrival may displace a low priority unit from the full queue and may be “blocked” if the queue consists of high priority units only. In the second model the high priority unit may still displace a low priority unit from the full queue but it will never be “blocked” and may wait “outside” the system if the system is full. Thus far there has been no discussion of such models in queuing theory literature. In this paper analytical expressions for average waiting times have been obtained for the two models. Two potential applications of the models are described and the usefulness of the models is illustrated by numerical examples.     

Stability of Parallel Queueing Systems with Coupled Service Rates

This paper considers a parallel system of queues fed by independent arrival streams, where the service rate of each queue depends on the number of customers in all of the queues. Necessary and sufficient conditions for the stability of the system are derived, based on stochastic monotonicity and marginal drift properties of multiclass birth and death processes. These conditions yield a sharp characterization of stability for systems where the service rate of each queue is decreasing in the number of customers in other queues, and has uniform limits as the queue lengths tend to infinity. The results are illustrated with applications where the stability region may be nonconvex.     

A tandem queue with general bulk service and servers' “vacation”

This paper analyses two queueing models consisting of two units I and II connected in series, separated by a finite buffer of size N. In both models, unit I has only one exponential server capable of serving customers one at a time and unit II consist of c parallel exponential servers, each of them serving customers in groups according to general bulk service rules. When the queue length in front of unit II is less than the minimum of batch size, the free servers take a vacation. On return from vacation, if the queue length is less than the minimum, they leave for another vacation in the first model, whereas in the second model they wait in the system until they get the minimum number of customers and then start servicing. The steady-state probability vector of the number of customers waiting and receiving service in unit I and waiting in the buffer is obtained for both the models, using the modified matrix geometric method. Numerical results are also presented.     

The GI/M/1 queue and the GI/Geo/1 queue both with single working vacation

We first consider the continuous-time GI/M/1 queue with single working vacation (SWV). During the SWV, the server works at a different rate rather than completely stopping working. We derive the steady-state distributions for the number of customers in the system both at arrival and arbitrary epochs, and for the FIFO sojourn time for an arbitrary customer. We then consider the discrete-time GI/Geo/1/SWV queue by contrasting it with the GI/M/1/SWV queue.     

The M/G/1 retrial queue with Bernoulli schedules and general retrial times

This paper is concerned with the analysis of a single-server queue with Bernoulli vacation schedules and general retrial times. We assume that the customers who find the server busy are queued in the orbit in accordance with an FCFS (first-come-first-served) discipline and only the customer at the head of the queue is allowed access to the server. We first present the necessary and sufficient condition for the system to be stable and derive analytical results for the queue length distribution, as well as some performance measures of the system under steady-state condition. We show that the general stochastic decomposition law for M/G/1 vacation models holds for the present system also. Some special cases are also studied.     

基于模糊逻辑的重传控制策略

本文在分析WCDMA的无线链路控制（RLC）层中自动请求重传（ARQ）的实现机制的基础上,综合考虑RLC队列长度、TCP分组到达强度、无线链路层纠错强度以及TCP发送端的应用时延要求等因素,提出了基于模糊逻辑控制的重传控制策略。仿真结果表明,该策略能够有效地提高TCP通过无线网络的吞吐量,高效利用系统无线资源。     

Optimal scheduling in some multiqueue single-server systems

The authors address the problem of optimal scheduling in a multiqueue single-server (MQSS) model. An arriving customer joins queue j with probability 1/N, j=1,. . ., N. The server visits each queue for a random period of time whose duration is independent of the queue length. At the end of a visit period, either all customers of the attended queue leave the system (variant I), or only customers that were present in the queue upon the arrival of the server leave the system (variant II). A scheduling policy is a rule that selects the next queue to be visited by the server. When the controller has no information on the state of the system, it is shown that a cyclic policy minimizes the expected number of customers in the system. When the controller knows the number of customers in each queue, it is shown that the so-called most customers first (MCF) policy minimizes, in the sense of strong stochastic ordering, the vector of the number of customers in each queue whose components are arranged in decreasing order     

Matrix generation algorithm for an M-stage closed tandem queue with blocking

This paper contains a discussion concerning state transition rate matrix generation for a closed tandem queue with a fixed number of pallets and with blocking due to there being intermediate queue between any pair of machines. The method is based on the blocal balance concept. 'with this matrix, one can obtain the limiting probability of each system state. Once the limiting probabilities are found, machine utilizations and average queue lengths are readily computed. The computational algorithm for a closed tandem queue with blocking is provided and the results are compared to the average values of a computer simulation model.     

Information theoretic approximations for M/G/1 and G/G/1 queuing systems

Summary This paper presents new results concerning the use of information theoretic inference techniques in system modeling and concerning the widespread applicability of certain simple queuing theory formulas. For the case when an M/G/1 queue provides a reasonable system model but when information about the service time probability density is limited to knowledge of a few moments, entropy maximization and cross-entropy minimization are used to derive information theoretic approximations for various performance distributions such as queue length, waiting time, residence time, busy period, etc. Some of these approximations are shown to reduce to exact M/M/1 results when G = M. For the case when a G/G/1 queue provides a reasonable system model, but when information about the arrival and service distributions is limited to the average arrival and service rates, it is shown that various well known M/M/1 formulas are information theoretic approximations. These results not only provide a new method for approximating the performance distributions, but they help to explain the widespread applicability of the M/M/1 formulas.     

非强占有限优先权M/G/1排队系统

针对部分数据帧有完全优先权发送的计算机网络数据服务系统存在的网络拥塞风险问题,提出了一种非强占有限优先权M/G/1排队系统模型的方法。该系统模型引入控制完全优先权的参数n,使得数据帧的完全优先权变成有限优先权,考虑了不同优先级队伍之间的公平性,降低了计算机网络数据服务系统拥塞的风险,使得网络系统在有限优先权下有较好的稳定性。在模型研究中,运用全概率拆解方法获得各级队伍平均等待时间、平均逗留时间和平均队长的理论结果。对模型采用Matlab 2010a软件实验仿真,实验得到的各级队伍平均等待时间和理论平均等待时间的平均绝对误差为0.951%。实验中,有限优先权条件下各级顾客的平均等待时间比值显著小于完全优先权条件下各级顾客的平均等待时间比值。实验结果表明对非强占有限优先权M/G/1排队系统模型研究的理论结果是正确的,该模型具有更稳定的系统特性。