On a synchronization queue with two finite buffers

In this paper, we consider a synchronization queue (or synchronization node) consisting of two buffers with finite capacities. One stream of tokens arriving at the system forms a Poisson process and the other forms a PH-renewal process. The tokens are held in the buffers until one is available from each flow, and then a group-token is instantaneously released as a synchronized departure. We show that the output stream of a synchronization queue is a Markov renewal process, and that the time between consecutive departures has a phase type distribution. Thus, we obtain the throughput of this synchronization queue and the loss probabilities of each type of tokens. Moreover, we consider an extended synchronization model with two Poisson streams where a departing group-token consists of several tokens in each buffer. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal Open-Loop Control of Vacations,Polling and Service Assignment

We consider in this paper the optimal open-loop control of vacations in queueing systems. The controller has to take actions without state information. We first consider the case of a single queue, in which the question is when should vacations be taken so as to minimize, in some general sense, workloads and waiting times. We then consider the case of several queues, in which service of one queue constitutes a vacation for others. This is the optimal polling problem. We solve both problems using new techniques from [2,4] based on multimodularity.     

Asymptotic Analysis of Two Coupled Queues with Vastly Different Arrival Rates and Finite Customer Capacities

We consider two coupled queues, with each having a finite capacity of customers. When both queues are nonempty they evolve independently, but when one becomes empty the service rate in the other changes. Such a model corresponds to a generalized processor sharing (GPS) discipline. We study the joint distribution p(m, n) of finding (m, n) customers in the (first, second) queue, in the steady state. We study the problem in an asymptotic limit of “heavy traffic,” where also the arrival rate to the second queue is assumed to be small relative to that of the first. The capacity of the first queue is scaled to be large, while that of the second queue is held constant. We consider several different scalings, and in each case obtain limiting differential and/or difference equation for p(m, n), and these we explicitly solve. We show that our asymptotic approximations are quite accurate numerically. This work supplements previous investigations into this GPS model, which assumed infinite capacities/buffers. The present model corresponds to a random walk in a lattice rectangle, where p(m, n) satisfies a different boundary condition on each edge.     

A Mathematical Programming Approach to Optimal Markovian Switching of Poisson Arrival Streams to Queueing Systems

Motivated by certain situations in manufacturing systems and communication networks, we look into the problem of maximizing the profit in a queueing system with linear reward and cost structure and having a choice of selecting the streams of Poisson arrivals according to an independent Markov chain. We view the system as a MMPP/GI/1 queue and seek to maximize the profits by optimally choosing the stationary probabilities of the modulating Markov chain. We consider two formulations of the optimization problem. The first one (which we call the PUT problem) seeks to maximize the profit per unit time whereas the second one considers the maximization of the profit per accepted customer (the PAC problem). In each of these formulations, we explore three separate problems. In the first one, the constraints come from bounding the utilization of an infinite capacity server; in the second one the constraints arise from bounding the mean queue length of the same queue; and in the third one the finite capacity of the buffer reflect as a set of constraints. In the problems bounding the utilization factor of the queue, the solutions are given by essentially linear programs, while the problems with mean queue length constraints are linear programs if the service is exponentially distributed. The problems modeling the finite capacity queue are non-convex programs for which global maxima can be found. There is a rich relationship between the solutions of the PUT and PAC problems. In particular, the PUT solutions always make the server work at a utilization factor that is no less than that of the PAC solutions.     

Estimating the throughput of an exponential CONWIP assembly system

We consider a production system consisting of several fabrication lines feeding an assembly station where both fabrication and assembly lines consist of multiple machine exponential workstations and the CONWIP (CONstant Work-In-Process) mechanism is used to regulate work releases. We model this system as an assembly-like queue and develop approximations for the throughput and average number of jobs in queue. These approximations use an estimate of the time that jobs from each line spend waiting for jobs from other lines before being assembled. We use our approximations to gain insight into the related problems of capacity allocation, bottleneck placement and WIP setting.     

N-策略单重休假M/G/1排队系统的队长分布

本文考虑N-策略单重休假M/G/1排队系统,通过引进"服务员忙期"和使用全概率分解技术,从任意初始状态出发,研究了队长的瞬态分布和稳态分布,首次导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得一些特殊排队系统相应的结果.     

The effect of information on queue-scalping service systems

We consider an M/M/1 queueing system with a single queue scalper who makes profit by selling his position in the queue. The equilibrium purchasing strategies of customers under observable case (with double-threshold strategy) and unobservable case (with mixed strategy) are derived. The profits of the queue scalper are obtained under two information levels. Numerical experiments suggest that the queue scalper is better off with unobservable case when the system is too congested or the operating cost is too low.     

Questionnaire design improvement and missing item scores estimation for rapid and efficient decision making

In this paper we consider a single-server, cyclic polling system with switch-over times and Poisson arrivals. The service disciplines that are discussed, are exhaustive and gated service. The novel contribution of the present paper is that we consider the reneging of customers at polling instants. In more detail, whenever the server starts or ends a visit to a queue, some of the customers waiting in each queue leave the system before having received service. The probability that a certain customer leaves the queue, depends on the queue in which the customer is waiting, and on the location of the server. We show that this system can be analysed by introducing customer subtypes, depending on their arrival periods, and keeping track of the moment when they abandon the system. In order to determine waiting time distributions, we regard the system as a polling model with varying arrival rates, and apply a generalised version of the distributional form of Little??s law. The marginal queue length distribution can be found by conditioning on the state of the system (position of the server, and whether it is serving or switching).     

On the Shortest Queue Version of the Erlang Loss Model

We consider two parallel M / M / N / N queues. Thus there are N servers in each queue and no waiting line(s). The network is fed by a single Poisson arrival stream of rate λ, and the 2 N servers are identical exponential servers working at rate μ. A new arrival is routed to the queue with the smaller number of occupied servers. If both have the same occupancy then the arrival is routed randomly, with the probability of joining either queue being 1/2. This model may be viewed as the shortest queue version of the classic Erlang loss model. If all 2 N servers are occupied further arrivals are turned away and lost. We let  ρ=λ/μ  and   a = N /ρ= N μ/λ  . We study this model both numerically and asymptotically. For the latter we consider heavily loaded systems (ρ→∞) with a comparably large number of servers (   N →∞  with   a = O (1))  . We obtain asymptotic approximations to the joint steady state distribution of finding m servers occupied in the first queue and n in the second. We also consider the marginal distribution of the number of occupied servers in the second queue, as well as some conditional distributions. We show that aspects of the solution are much different according as   a > 1/2, a ≈ 1/2, 1/4 < a < 1/2, a ≈ 1/4  or  0 < a < 1/4  . The asymptotic approximations are shown to be quite accurate numerically.     

Dynamic server assignment in a two-queue model

We consider a polling model of two M/G/1 queues, served by a single server. The service policy for this polling model is of threshold type. Service at queue 1 is exhaustive. Service at queue 2 is exhaustive unless the size of queue 1 reaches some level T during a service at queue 2; in the latter case the server switches to queue 1 at the end of that service. Both zero- and nonzero switchover times are considered. We derive exact expressions for the joint queue length distribution at customer departure epochs, and for the steady-state queue-length and sojourn time distributions. In addition, we supply a simple and very accurate approximation for the mean queue lengths, which is suitable for optimization purposes.     

箱子是在线到达的带核元变尺寸装箱问题

本文考虑了一类箱子在线到达的带核元变尺寸装箱问题．假定箱子的尺寸可以是不同的．箱子是在线到达的，仅当箱子到达后其尺寸才知道．给定一个带有核元的物件表，目标是要将表中元素装入到达的箱子中，使得所用的箱子总长最小．我们首先证明了该问题是强NP—Hard，其次分析了经典算法NF(D)和FF(D)的性能界，指出NF(D)和FF(D)算法的性能界可以任意大．最后我们给出了相应的修改算法MNF(D)和MFF(D)，证明了它们的性能界都是3，此界是紧的．     

带有反馈机制的单服务台排队系统的泛函重对数律

本文考虑了一个带有贝努里反馈机制的单服务台排队系统.我们将该系统的一些数量指标如队长过程,忙期过程,负荷过程的泛函重对数律的问题转化为一个反射布朗运动相关的问题,利用已有的布朗运动的重对数率的结果,刻画了队长过程,忙期过程,负荷过程的重对数律.     

Optimal allocation of priority in a M/M/1 queue with two types of customers

We consider a M/M/1 queue with two types of customers.The server suffers some loss when a non-priority customer joins the queue if the size of the queue is greater than some predetermined level N. The problem is to decide which group receives priority in such a way as to minimize the expected cost per unit of time.We show first how to determine the optimal decision. Then we introduce approximations that enable us to show that the optimal decision has a simple behaviour as a function of N, the arrival and service parameters.     

Multi-server retrial queue with negative customers and disasters

We consider a multi-server retrial queue with waiting places in service area and four types of arrivals, positive customers, disasters and two types of negative customers, one for deleting customers in orbit and the other for deleting customers in service area. The four types of arrivals occur according to a Markovian arrival process with marked transitions (MMAP) which may induce the dependence among the arrival processes of the four types. We derive a necessary and sufficient condition for the system to be positive recurrent by comparing sample paths of auxiliary systems whose stability conditions can be obtained. We use a generalized truncated system that is obtained by modifying the retrial rates for an approximation of stationary queue length distribution and show the convergence of approximation to the original model. An algorithmic solution for the stationary queue length distribution and some numerical results are presented.      

N-策略M/G/1/∞排队系统的队长分布表达式

本文考虑N-策略M／G／1／∞排队系统，研究了队长的瞬态和稳态性质。通过引进“服务员忙期”和使用全概率分解技术，我们导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式，以及平稳队长的随机分解。特别地，通过本文可直接获得一些特殊排队系统相应的结果。     

The queue length distributions in the finite buffer bulk-service MAP/G/1 queue with multiple vacations

We consider a finite buffer batch service queueing system with multiple vacations wherein the input process is Markovian arrival process (MAP). The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service- and vacation- times are arbitrarily distributed. We obtain the queue length distributions at service completion, vacation termination, departure, arbitrary and pre-arrival epochs. Finally, some performance measures such as loss probability, average queue lengths are discussed. Computational procedure has been given when the service- and vacation- time distributions are of phase type (PH-distribution).     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

Metric inequalities for routings on direct connections with application to line planning

We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the well-known feasibility condition for arc capacities in ordinary multi-commodity flows. The condition can be expressed in terms of a class of metric inequalities for routings on direct connections. We illustrate the concept on the example of the line planning problem in public transport and present an application to large-scale real-world problems.     

BMAP/G/1/N queue with vacations and limited service discipline

We consider a finite buffer single server queue with batch Markovian arrival process (BMAP), where server serves a limited number of customer before going for vacation(s). Single as well as multiple vacation policies are analyzed along with two possible rejection strategies: partial batch rejection and total batch rejection. We obtain queue length distributions at various epochs and some important performance measures. The Laplace–Stieltjes transforms of the actual waiting time of the first customer and an arbitrary customer in an accepted batch have also been obtained.     

On the distribution of the number of retrials

We consider queuing systems where customers are not allowed to queue, instead of that they make repeated attempts, or retrials, in order to enter service after some time. We obtain the distribution of the number of retrials produced by a tagged customer, until he finds an available server.