Incentive Effects of Multiple-Server Queueing Networks: The Principal-Agent Perspective

A two-server service network has been studied from the principal-agent perspective. In the model, services are rendered by two independent facilities coordinated by an agency, which seeks to devise a strategy to suitably allocate customers to the facilities and to simultaneously determine compensation levels. Two possible allocation schemes were compared — viz. the common queue and separate queue schemes. The separate queue allocation scheme was shown to give more competition incentives to the independent facilities and to also induce higher service capacity. In this paper, we investigate the general case of a multiple-server queueing model, and again find that the separate queue allocation scheme creates more competition incentives for servers and induces higher service capacities. In particular, if there are no severe diseconomies associated with increasing service capacity, it gives a lower expected sojourn time in equilibrium when the compensation level is sufficiently high.     

两类排队网络的逼近研究

本文给出了两类排队网络。一类是容量有限的队列网络,我们证明了在高负荷下,标准化的队长过程弱收敛于半鞅反射的布朗运动：另一类是带有反馈的多类顾客多服务台队列网络,我们获得了队列网络中负荷过程的扩散逼近。     

On the optimality of exhaustive service policies in multiclass queueing systems with modulated arrivals and switchovers

Consider a single-server multiclass queueing system withK classes where the individual queues are fed byK-correlated interrupted Poisson streams generated in the states of aK-state stationary modulating Markov chain. The service times for all the classes are drawn independently from the same distribution. There is a setup time (and/or a setup cost) incurred whenever the server switches from one queue to another. It is required to minimize the sum of discounted inventory and setup costs over an infinite horizon. We provide sufficient conditions under which exhaustive service policies are optimal. We then present some simulation results for a two-class queueing system to show that exhaustive, threshold policies outperform non-exhaustive policies. This research was supported in part by the Office of Naval Research and the Department of Science and Technology grant N00014-93-1017.     

Using state-dependent processing rates to emulate SPT queue discipline in an FCFS queueing network

Using the 'shortest processing time' queue discipline results in long queues being quickly reduced as the short jobs are quickly pushed through the system. We approximate this effect under the 'first-come, first-served' queue discipline by having the service rate increase with the queue length. That is, instead of picking the shortest job, the server instead picks the first job, but then processes it at a higher rate. This new load-dependent queue is compared with the original queue both individually and within open queueing networks.     

Periodic review inventory-control for perishable products under service-level constraints

Food retail inventory management faces major challenges by uncertain demand, perishability, and high customer service level requirements. In this paper, we present a method to determine dynamic order quantities for perishable products with limited shelf-life, positive lead time, FIFO or LIFO issuing policy, and multiple service level constraints. In a numerical study, we illustrate the superiority of the proposed method over commonly suggested order-up-to-policies. We show that a constant-order policy might provide good results under stationary demand, short shelf-life, and LIFO inventory depletion.     

Polling of two queues with synchronized correlated inputs and zero walktime

Abstract

This paper studies the polling of two infinite queues by a synchronous server. The inputs to these queues are correlated and restricted to occur only at equally spaced time intervals. For simplicity, the walktime for the server to move from one queue to the other is assumed to be zero in this study. In essence, the problem studied in this paper is equivalent to a fixed service time queueing system which accepts two types of synchronized correlated inputs and adopts an alternating priority discipline. This paper contains a complete analysis of both the busy period and the waiting time. The validity of the analysis has been verified by computer simulations.     

On the analysis of single server finite queue with state dependent arrival and service processes: M(n)/G(n)/1/K

This paper discusses the analysis of a single server finite queue with Poisson arrival and arbitrary service time distribution, wherein the arrival rates are state dependent which are all distinct or all equal, service times are conditioned on the system length at the moment of service initiation. The analytic analysis of the queue is carried out and the final results have been presented in the form of recursive equations which can be easily programmed on any PC to obtain the distributions of number of customers in the system at arbitrary, departure and pre-arrival epochs. It is shown that the method works for all service time distributions including the non-phase type and also for low and high values of the model parameters. Some performance measures, and relations among the state probabilities at arbitrary, departure and pre-arrival epochs are also discussed. Furthermore, it is shown that results for a number of queueing models can be obtained from this model as special cases. To demonstrate the effectiveness of our method some numerical examples have been presented.     

Approximate Analysis for the Merge Configuration of an Open Queueing Network with Blocking

A merge configuration of open queueing networks with exponential service times and finite buffers is analysed. We offer an iterative algorithm to approximate the steady-state probabilities for each queue of the system. The procedure decomposes the queueing network into individual queues and analyses each individual queue in isolation. An M/M/l/N or M/G/l/N model is used for the analysis of the merging queues; an M/M/l/N with state dependent arrival rates is used for the receiving queue. The approximation method is easy to implement, requires little memory, is computationally fast and yields very accurate results.     

On a Computational Approach to Some Value Functions in an M/EZ/1 Queue

An M/E_z/1 queue (i.e. a single-server queue having a Poisson arrival process and weighted-sum Erlangian service) can approximate a wide range of queueing systems quite closely. For this system a practical computational scheme is developed for determining (1) the expected amount of time the server is idle in the interval (0, t] and (2) the expected waiting time of a customer arriving at time t. The initial service load can be specified arbitrarily. Sample results and computer time requirements are also discussed.     

WARD: a transmission control protocol-friendly stateless active queue management scheme

In this article, the problem of providing a fair bandwidth allocation to the flows sharing a congested link in a router is investigated. Queue management, bandwidth share and congestion control are very important to both the robustness and fairness of the Internet. The buffer at the outgoing link is a simple FIFO, shared by packets belonging to the flows. A new transmission control protocol (TCP)-friendly router-based active queue management scheme, termed WARD, is proposed to approximate the fair queueing policy. WARD is a simple packet-dropping algorithm with a random mechanism which discriminates against flows that submit more packets per second than is allowed as their fair share. By doing this, it not only protects TCP connections from user datagram protocol flows, but also solves the problem of competing bandwidth among different TCP versions, such as TCP Vegas and TCP Reno. In addition, WARD works quite well for TCP flow isolation even with different round trip times. In other words, WARD improves the unfair bandwidth allocation properties. Furthermore, as it is stateless and easy to implement, WARD controls unresponsive or misbehaving flows with only a minimum overhead.     

多服务速率多重休假M/G(M/G)/1可修排队

本文通过对系统中顾客数设置门限N,考虑研究了服务台的服务速度依门限发生变化且当服务台未服务顾客(休假或故障)时到达顾客仅以概牢p进入系统的多重休假可修M／G(M／G)／1排队系统。通过L-变换、母函数以及补充变量方法得到了队长分布的瞬态解、稳态解及一些可靠性结果,并指出当两个服务速度相等时该模型与前人研究的M／G／1(E,MV）排队一致。     

Performance evaluation of a transportation-type bulk queue with generally distributed inter-arrival times

This paper is motivated by the performance evaluation of circulating vertical conveyor systems (CVCSs). CVCSs are bulk queues of transportation type. These material handling systems feature generally distributed inter-arrival times, which can be longer than the bulk service time. This leads to interdependencies between the number of arrivals in consecutive service intervals and the number of loads in the queue. We propose a new discrete-time approach for the steady-state analysis of such bulk service queues of transportation type with general arrival and service processes and finite server and limited queue capacities. The approach is based on a finite Markov chain that generates complete probability distributions for the key performance measures, including the queue length, waiting time and departing batch size. The proposed approach is exact in the cases of discrete-time slots, e.g. as in communication systems. We investigate the discretisation error that arises if the approach is used as an approximation for the continuous time using a numerical comparison to a discrete-event simulation. Moreover, we examine the impact of arrival stream variability on the system performance and compare the positive effects of a higher frequency of server visits with the effects arising from larger pickup capacities.     

Finite waiting space bulk queueing systems

Summary This paper extends earlier work on the stationary queue length distribution of a bulk service system with finite waiting space by considering two queueing systems. The first system incorporates the feature of batch arrivals with group service; it has compound Poisson input, general service times and a single server with variable batch capacity. The second system has individually arriving customers with Erlangian interarrival time distribution, general service times and a single server with variable batch capacity.The financial support of the National Research Council of Canada, under Research Grants No. 3-644-189-60; NRC-A5639 and No. 3-641-189-10; NRC-A2796, is acknowledged.     

Quality control for a detected an appropriate queue from K-independent M/M/C/N queueing models

In this paper, we consider a system of K-independent Markovian queues such that each one of them has a Poisson arrival process and exponential service time. We assume that every server has some characteristics such as the speed of the service performance or the service cost. To find an appropriate queue, which meets customer needs for the service performance, we present a new approach that gives a suitable decision to choose an appropriate queue from our system. This allows the customer to deal with minimum cost and faster server under steady state. We solve an interesting discrete stochastic optimization problem where the paid cost by the customer is bounded by a Gaussian distribution. Using these hypotheses, we perform a simulation study by generating the paid cost random values and choosing the minimum value between them. This minimum cost gives the highest service rate, which is used to obtain the optimum values of the system effectiveness measures.     

Analysis of finite-buffer state-dependent bulk queues

In this paper, we consider a general state-dependent finite-buffer bulk queue in which the rates and batch sizes of arrivals and services are allowed to depend on the number of customers in queue and service batch sizes. Such queueing systems have rich applications in manufacturing, service operations, computer and telecommunication systems. Interesting examples include batch oven processes in the aircraft and semiconductor industry; serving of passengers by elevators, shuttle buses, and ferries; and congestion control mechanisms to regulate transmission rates in packet-switched communication networks. We develop a unifying method to study the performance of this general class of finite-buffer state-dependent bulk queueing systems. For this purpose, we use semi-regenerative analysis to develop a numerically stable method for calculating the limiting probability distribution of the queue length process. Based on the limiting probabilities, we present various performance measures for evaluating admission control and batch service policies, such as the loss probability for an arriving group of customers and for individual customers within a group. We demonstrate our method by means of numerical examples.     

M~x/M/N可修排队系统

本文研究了顾客批量到达且服务台忙时与闲时故障率不同的多服务台可修排队系统,推导出了系统的稳态平衡方程以及稳态概率值的求解思路.由于N≥2时手工计算的复杂性,使用Mathematica软件编程实现了稳态概率值的求取,并最终得到了系统有效服务台数的稳态分布、稳态队长的母函数以及平均队长等重要的系统指标.     

Performance behaviour of IEEE 802.11 distributed coordination function

The authors present an extensive investigation of the performance of the IEEE 802.11 medium access control (MAC) protocol, with respect to throughput and delay. For the protocol analysis, a new model, which describes the protocol's behaviour to a great extent by incorporating and extending the existing models, is proposed. The authors also present a detailed analysis of the end-to-end delay through the study of the MAC delay and the queueing delay. The authors use the Z-transform of backoff duration to obtain the mean value, the variance and the probability distribution of the MAC delay. For the queueing analysis, first the authors consider an M/G/l queue in order to provide a first look at the queueing delay. Second, the authors modify the input process of the queue so that the packet arrival process is described by an ON- OFF model, which expresses the bursty nature of traffic. In the investigations, data rates of 1, 5.5 and 11 Mbps are assumed to highlight the effect of the bit rate on network performance for both Basic and request-to-send/ clear-to-send access mechanisms. The throughput and delay analyses are validated by simulating the distributed coordination function, whereas the models are compared with the existing models based on their results. The accuracy of the analyses was found to be quite satisfactory.     

Heuristic analysis of closed queueing networks

In this paper we consider closed queueing networks having M single server queueing stations with arbitrary interconnections and general service time distributions. Here we propose an iterative approximation procedure, based on a decomposition approximation. Numerical results are reported to demonstrate the accuracy of the method. We also discuss the sensitivity of the results to the initial guess for the server utilizations.     

基于 Min($N,D,V$)——策略和单重休假的 $M/G/1$ 排队系统队长分布的瞬态和稳态解

本文主要研究服务员单重休假且在休假时间中根据 Min($N,D,V$)--控制策略可立即中断休假的 $M/G/1$ 排队系统．运用全概率分解技术和拉普拉斯变换工具，讨论在任意初始状态条件下队长的瞬态和稳态性质，得到了队长分布瞬态解的拉普拉斯变换表达式．在此基础上，直接获得了便于作数值计算的队长分布稳态解的递推表达式．进一步，给出了稳态队长的随机分解结构、附加队长分布的显示表达式，以及在一些特殊情形下的相应结果．最后，通过数值实例考察了附加队长分布对系统参数的敏感性，分析参数不同取值对系统运行性能的影响．     

The efficiency and economics of small heterogeneous labour limited queueing systems

This paper presents an evaluation of heterogeneous labour patterns in small, labour limited queueing systems. Three heterogeneous labour patterns, a homogeneous labour force and two labour assignment rules are examined. The experimental systems consist of three machine centres in parallel, each with its own queue. The arrival process is Poisson, and the queue priority rule is first-come-first-served. Each machine centre contains one machine, and the service times are exponentially distributed. The number of labourers is two. The experimental model is a GERTS QR stochastic network simulator. The evaluation focuses upon the relative merits of the various labourer efficiency patterns and offers an economic interpretation of the experimental results.