A discrete-time retrial queueing model with one server

This paper presents a one-server queueing model with retrials in discrete-time. The number of primary jobs arriving in a time slot follows a general probability distribution and the different numbers of primary arrivals in consecutive time slots are mutually independent. Each job requires from the server a generally distributed number of slots for its service, and the service times of the different jobs are independent. Jobs arriving in a slot can start their service only at the beginning of the next slot. When upon arrival jobs find the server busy all incoming jobs are sent into orbit. When upon arrival in a slot jobs find the server idle, then one of the incoming jobs (randomly chosen) in that slot starts its service at the beginning of the next slot, whereas the other incoming jobs in that slot, if any, are sent into orbit. During each slot jobs in the orbit try to re-enter the system individually, independent of each other, with a given retrial probability.     

A two-stage queueing network with MAP inputs and buffer sharing

In this paper, we study a two-stage tandem queueing network with MAP inputs and buffer sharing. The two stages share the same buffer. By using Markov process, we give an exact analysis of the queueing network. Since the customer arrival is not a Poisson process, the PASTA (Poisson Arrivals See Time Averages) property does not hold. A matrix filtration technique is proposed to derive the probability distribution of queue length at arrivals. Our objective is to investigate how the buffer sharing policy is mitigate the tradeoff between the probability that an arriving customer is lost and the probability that the first-stage server is blocked. The numerical results show that buffer sharing policy is more flexible, especially when the inputs have large variant and are correlated.     

Analysis of a statistical multiplexer with generalized periodic sources

We provide solution techniques for the analysis of multiplexers with periodic arrival streams, which accurately account for the effects of active and idle periods and of gradual arrival. In the models considered in this paper, it is assumed that each source alternates (periodically) between active and idle periods of fixed durations. Incoming packets are transmitted on the network link and excess information is stored in the multiplexing buffer when the aggregate input rate exceeds the capacity of the link. We are interested in the probability distribution of the buffer content for a given network link speed as a function of the number of sources and their characteristics, i.e., rate and duration of idle and active periods. We derive this distribution from two models: discrete time and continuous time systems. Discrete time systems operate in a slotted fashion, with a slot defining the base unit for data generation and transmission. In particular, in each slot the link is capable of transmitting one data unit and conversely an active source generates one data unit in that time. The continuous time model of the paper falls in the category of fluid models. Compared to previous works we allow a more general model for the periodic packet arrival process of each source. In discrete time, this means that the active period of a source can now extend over several consecutive slots instead of a single slot as in previous models. In continuous time, packet arrivals are not required to be instantaneous, but rather the data generation process can now take place over the entire duration of the active period. In both cases, these generalizations allow us to account for the progressive arrival of source data as a function of both the source speed and the amount of data it generates in an active period.This work was done while at the IBM T.J. Watson Research Center.This work was done while at the IBM T.J. Watson Research Center.Part of the work was done while visiting the IBM T.J. Watson Research Center.     

Discrete NT-policy single server queue with Markovian arrival process and phase type service

We consider a discrete time single server queueing system in which arrivals are governed by the Markovian arrival process. During a service period, all customers are served exhaustively. The server goes on vacation as soon as he/she completes service and the system is empty. Termination of the vacation period is controlled by two threshold parameters N and T, i.e. the server terminates his/her vacation as soon as the number waiting reaches N or the waiting time of the leading customer reaches T units. The steady state probability vector is shown to be of matrix-geometric type. The average queue length and the probability that the server is on vacation (or idle) are obtained. We also derive the steady state distribution of the waiting time at arrivals and show that the vacation period distribution is of phase type.     

The performance measures and randomized optimization for an unreliable server M/G/1 vacation system

This paper examines an M^[x]/G/1 queueing system with a randomized vacation policy and at most J vacations. Whenever the system is empty, the server immediately takes a vacation. If there is at least one customer found waiting in the queue upon returning from a vacation, the server will be immediately activated for service. Otherwise, if no customers are waiting for service at the end of a vacation, the server either remains idle with probability p or leaves for another vacation with probability 1 − p. This pattern continues until the number of vacations taken reaches J. If the system is empty by the end of the Jth vacation, the server becomes idle in the system. Whenever one or more customers arrive at server idle state, the server immediately starts providing service for the arrivals. Assume that the server may meet an unpredictable breakdown according to a Poisson process and the repair time has a general distribution. For such a system, we derive the distributions of important system characteristics, such as system size distribution at a random epoch and at a departure epoch, system size distribution at busy period initiation epoch, the distributions of idle period, busy period, etc. Finally, a cost model is developed to determine the joint suitable parameters (p^∗, J^∗) at a minimum cost, and some numerical examples are presented for illustrative purpose.     

延迟控制休假的M／M／1排队系统

本文研究带有延迟休假的 Ｍ／Ｍ／１排队系统,服务员在空闲了一段时间（称做延迟时间）后才正式开始休假,每次休假的时间长度有指数分布．若一次休假结束时系统中的顾客数目低于某一水平Ｋ,则服务员开始另一次休假;否则转为投入服务,这时系统开始一个新的忙期。对于延迟时间有指数分布和是确定的情形分别求得系统的稳态分布的精确表示及某些性能指标．文章还讨论了系统优化问题,给出使得单位时间平均总成本最小的Ｋ值．证明在泊松到达的情形最优延迟时间是０（无延迟）或无穷（无休假）     

Optimal parking of idle elevators under myopic and state-dependent policies

In this paper we discuss the problem of optimally parking single and multiple idle elevators under light-traffic conditions. The problem is analyzed from the point of view of the elevator owner whose objective is to minimize the expected total cost of parking and dispatching the elevator (which includes the cost incurred for waiting passengers). We first consider the case of a single elevator and analyze a (commonly used but suboptimal) state-independent myopic policy that always positions the idle elevator at the same floor. Building on the results obtained for the myopic policy, we then show that the optimal non-myopic (state-dependent) policy calls for dispatching the idle elevator to the state-dependent median of a weight distribution. Next, we consider the more difficult case of two elevators and develop an expression for the expected dispatching distance function. We show that the objective function for the myopic policy is non-convex. The non-myopic policy is found to be dependent on the state of the two idle elevators. We compute the optimal state-dependent policy for two elevators using the results developed for the myopic policy. Next, we examine the case of multiple elevators and provide a general recursive formula to find the expected dispatching distance functions. Finally, we generalize the previous models by incorporating a fixed cost for parking the idle elevators that results in a two-sided optimal policy with different regions. Every policy that we introduce and analyze is illustrated by an example. The paper concludes with a short summary and suggestions for future research.     

A two-class discrete-time queueing model with two dedicated servers and global FCFS service discipline

This paper considers a simple discrete-time queueing model with two types (classes) of customers (types 1 and 2) each having their own dedicated server (servers A and B resp.). New customers enter the system according to a general independent arrival process, i.e., the total numbers of arrivals during consecutive time slots are i.i.d. random variables with arbitrary distribution. Service times are deterministically equal to 1 slot each. The system uses a “global FCFS” service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their types. As a consequence of the “global FCFS” rule, customers of one type may be blocked by customers of the other type, in that they may be unable to reach their dedicated server even at times when this server is idle, i.e., the system is basically non-workconserving. One major aim of the paper is to estimate the negative impact of this phenomenon on the queueing performance of the system, in terms of the achievable throughput, the system occupancy, the idle probability of each server and the delay. As it is clear that customers of different types hinder each other more as they tend to arrive in the system more clustered according to class, the degree of “class clustering” in the arrival process is explicitly modeled in the paper and its very direct impact on the performance measures is revealed. The motivation of our work are systems where this kind of blocking is encountered, such as input-queueing network switches or road splits.     

基于Markov更新过程的城市交通网络级联失效评价模型

根据路段单元状态与其功能之间的关系,给出了路段单元状态的‘失效—非失效’二态表示方法,进一步根据网络中路段单元之间的连接关系,提出了道路交通网络‘级联失效’态的定义及识别方法;利用更新理论及Markov链相关理论,分析了道路交通网络级联失效态—非级联失效态持续时间随机变化的概率分布规律,给出了对假想分布的未知参数进行估计及对假想分布进行假设检验的方法,并提出了以失效次数及转移概率为主要评价参数的交通网络级联失效评价模型。以一个实际路网为例,对模型进行了标定,将标定好的模型评价结果与实际观察结果进行了比对,结果显示模型具有较好的实用性。     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

A linear model for surface mining haul truck allocation incorporating shovel idle probabilities

We present models of trucks and shovels in oil sand surface mines. The models are formulated to minimize the number of trucks for a given set of shovels, subject to throughput and ore grade constraints. We quantify and validate the nonlinear relation between a shovel’s idle probability (which determines the shovel’s productivity) and the number of trucks assigned to the shovel via a simple approximation, based on the theory of finite source queues. We use linearization to incorporate this expression into linear integer programs. We assume in our integer programs that each shovel is assigned a single truck size but we outline how one could account for multiple truck sizes per shovel in an approximate fashion. The linearization of shovel idle probabilities allows us to formulate more accurate truck allocation models that are easily solvable for realistic-sized problems.     

A NEW CHARACTERIZATION OF THE BINOMIAL SEQUENCE

ＡＮＥＷＣＨＡＲＡＣＴＥＲＩＺＡＴＩＯＮＯＦＴＨＥＢＩＮＯＭＩＡＬＳＥＱＵＥＮＣＥ￥ＣＨＥＮＧＳＨＩＸＵＥＡｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ａｎｅｗｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆｔｈｅｂｉｎｏｍｉａｌｓｅｑｕｅｎｃｅａｎｄｉｔｓｅｑｕｉ...     

First crossing time,overshoot and Appell–Hessenberg type functions

We consider a general insurance risk model with extended flexibility under which claims arrive according to a point process with independent increments, their amounts may have any joint distribution and the premium income is accumulated following any non-decreasing, possibly discontinuous, real valued function. Point processes with independent increments are in general non-stationary, allowing for an arbitrary (possibly discontinuous) claim arrival cumulative intensity function which is appealing for insurance applications. Under these general assumptions, we derive a closed form expression for the joint distribution of the time to ruin and the deficit at ruin, which is remarkable, since as we show, it involves a new interesting class of what we call Appell–Hessenberg type functions. The latter are shown to coincide with the classical Appell polynomials in the Poisson case and to yield a new class of the so called Appell–Hessenberg factorial polynomials in the case of negative binomial claim arrivals. Corollaries of our main result generalize previous ruin formulas e.g. those obtained for the case of stationary Poisson claim arrivals.     

Poisson过程作为更新过程的若干新的特征刻画

本文将给出Poisson过程作为更新过程的一系列新的特征刻画．这些刻画是借助于更新过程中所有关键量的条件概率分布或条件期望来表述的．所给的条件是至任一指定时刻发生的抵达敷为已知．     

Channels in cellular systems: To borrow or not to borrow...

This note develops an analytic model to answer the question whether it is advantageous to borrow a channel in cellular mobile communications systems. Such questions arise dynamically, whenever there is a pending call which will be blocked unless a channel is borrowed. The expected number of calls which will be blocked in the donor cells is calculated assuming that the channel is borrowed and held for the call holding duration. The resulting borrowing rule is simple — the channel should not be borrowed if this number is more than one and borrowed otherwise. If there is an option of borrowing from one of several donor groups, then the donor group which suffers the minimum number of expected blocked calls should be borrowed from. This approach provides a simple practical solution to a rather complicated problem. The results apply to any layout of cells. Channels could have been assigned to the cells via any method and not all channels may be borrowable.     

Quasi-reversible multiclass queues with order independent departure rates

This paper introduces a new class of queues which are quasi-reversible and therefore preserve product form distribution when connected in multinode networks. The essential feature leading to the quasi-reversibility of these queues is the fact that the total departure rate in any queue state is independent of the order of the customers in the queue. We call such queues order independent (OI) queues. The OI class includes a significant part of Kelly's class of symmetric queues, although it does not cover the whole class. A distinguishing feature of the OI class is that, among others, it includes the MSCCC and MSHCC queues but not the LCFS queue. This demonstrates a certain generality of the class of OI queues and shows that the quasi-reversibility of the OI queues derives from causes other than symmetry principles. Finally, we examine OI queues where arrivals to the queue are lost when the number of customers in the queue equals an upper bound. We obtain the stationary distribution for the OI loss queue by normalizing the stationary probabilities of the corresponding OI queue without losses. A teletraffic application for the OI loss queue is presented.     

Waiting times in queues with relative priorities

This paper determines the mean waiting times for a single server multi-class queueing model with Poisson arrivals and relative priorities. If the server becomes idle, the probability that the next job is from class-i is proportional to the product between the number of class-i jobs present and their priority parameter.     

Perishable Inventory System at Service Facilities with N Policy

Abstract

This article presents a perishable stochastic inventory system under continuous review at a service facility in which the waiting hall for customers is of finite size M. The service starts only when the customer level reaches N (< M), once the server has become idle for want of customers. The maximum storage capacity is fixed as S. It is assumed that demand for the commodity is of unit size. The arrivals of customers to the service station form a Poisson process with parameter λ. The individual customer is issued a demanded item after a random service time, which is distributed as negative exponential. The items of inventory have exponential life times. It is also assumed that lead time for the reorders is distributed as exponential and is independent of the service time distribution. The demands that occur during stock out periods are lost.The joint probability distribution of the number of customers in the system and the inventory levels is obtained in steady state case. Some measures of system performance in the steady state are derived. The results are illustrated with numerical examples.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.