Decomposability in queues with background states

A symmetric queue is known to have a nice property, the so-called insensitivity. In this paper, we generalize this for a single node queue with Poisson arrivals and background state, which changes at completion instants of lifetimes as well as at the arrival and departure instants. We study this problem by using the decomposability property of the joint stationary distribution of the queue length and supplementary variables, which implies the insensitivity. We formulate a Markov process representing the state of the queue as an RGSMP (reallocatable generalized semi-Markov process), and give necessary and sufficient conditions for the decomposability. We then establish general criteria to be sufficient for the queue to possess the property. Various symmetric-like queues with background states, including continuous time versions of moving server queues, are shown to have the decomposability.This author is partially supported by NEC C&C Laboratories.     

Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing

We consider characterizations of departure functions in Markovian queueing networks with batch movements and state-dependent routing in discrete-time and in continuous-time. For this purpose, the notion of structure-reversibility is introduced, which means that the time-reversed dynamics of a queueing network corresponds with the same type of queueing network. The notion is useful to derive a traffic equation. We also introduce a multi-source model, which means that there are different types of outside sources, to capture a wider range of applications. Characterizations of the departure functions are obtained for any routing mechanism of customers satisfying a recurrent condition. These results give a unified view to queueing network models with linear traffic equations. Furthermore, they enable us to consider new examples as well as show limited usages of this kind of queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exact Analysis of the State-Dependent Polling Model

We consider a polling model in which a number of queues are served, in cyclic order, by a single server. Each queue has its own distinct Poisson arrival stream, service time, and switchover time (the server's travel time from that queue to the next) distribution. A setup time is incurred if the polled queue has one or more customers present. This is the polling model with State-Dependent service (the SD model). The SD model is inherently complex; hence, it has often been approximated by the much simpler model with State-Independent service (the SI model) in which the server always sets up for a service at the polled queue, regardless of whether it has customers or not. We provide an exact analysis of the SD model and obtain the probability generating function of the joint queue length distribution at a polling epoch, from which the moments of the waiting times at the various queues are obtained. A number of numerical examples are presented, to reveal conditions under which the SD model could perform worse than the corresponding SI model or, alternately, conditions under which the SD model performs better than a corresponding model in which all setup times are zero. We also present expressions for a variant of the SD model, namely, the SD model with a patient server.     

Pricing under quality of service uncertainty: Market segmentation via statistical QoS guarantees

This article examines how performance-contingent pricing schemes with long-term statistical performance guarantees can be applied to many IT services. We study two forms of performance-contingent pricing, with rebate proportional to failure rate and fixed rebate for below-threshold performance. We show that threshold-performance contingency pricing can increase both profits and fairness (customers who receive higher benefits pay higher effective price) relative to standard pricing. But an even better solution is to offer a menu of performance guarantees: this can increase the firm’s profit and segment the market. Only service providers whose performance level is sufficiently better than the industry standard can benefit from this pricing mechanism.     

On the finite-source G/M/r queue

The aim of the present paper is to give the main characteristics of the finite-source $\text{G}\text{/}\text{M}\text{/r}$ queue in equilibrium. Here unit i stays in the source for a random time having general distribution function F_i(x) with density f_i(x). The service times of all units are assumed to be identically and exponentially distributed random variables with means 1/μ. It is shown that the solution to this $\text{G}\text{/}\text{M}\text{/r}$ model is similar in most important respects to that for the M/M/r model.     

A critically loaded multirate link with trunk reservation

We consider a loss system model of interest in telecommunications. There is a single service facility with N servers and no waiting room. There are K types of customers, with type ί customers requiring A _ί servers simultaneously. Arrival processes are Poisson and service times are exponential. An arriving type ί customer is accepted only if there are Rί(⩾A_ί ) idle servers. We examine the asymptotic behavior of the above system in the regime known as critical loading where both N and the offered load are large and almost equal. We also assume that R ₁,..., R _K-1 remain bounded, while R _K ^N ←∞ and R _K ^N /√N ← 0 as N ← ∞. Our main result is that the K dimensional “queue length” process converges, under the appropriate normalization, to a particular K dimensional diffusion. We show that a related system with preemption has the same limit process. For the associated optimization problem where accepted customers pay, we show that our trunk reservation policy is asymptotically optimal when the parameters satisfy a certain relation. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the estimation of mixing coefficients for a multiphase service system

We consider a multiphase service system with a Poisson input flow. Its intensity depends on the number of customers under service. The stationary distribution for this system can be found in an explicit form. We study the rate of convergence to this stationary distribution as well as the bounds for some mixing coefficients. Coupling arguments and Liapunov's function approach form the basis of considerations. This revised version was published online in June 2006 with corrections to the Cover Date.     

考虑多阶段决策信息集结的新算法及其应用

针对多阶段区间信息集结与决策问题,提出一种考虑最小化集结矩阵与阶段区间矩阵之间距离的新方法,寻求更趋近帕累托最优的集结结果,使最终评价值更符合多阶段评价的目标。 首先,根据多阶段专家评价值将区间信息转化为二维坐标点,并将其映射到二维坐标系中。然后,构建区间信息离差最小化集结模型,并基于植物模拟生长算法(PGSA）进行群体判断信息的集结,再通过合成各方案的属性评价值,给出各决策方案的综合评价值并进行排序,进而给出最优决策方案。最后,以物流服务商的多阶段绩效评价为例,验证了该方法的合理性和有效性。     

Gated Polling Systems with Lévy Inflow and Inter-Dependent Switchover Times: A Dynamical-Systems Approach

We study asymmetric polling systems where: (i) the incoming workflow processes follow general Lévy-subordinator statistics; and, (ii) the server attends the channels according to the gated service regime, and incurs random inter-dependentswitchover times when moving from one channel to the other. The analysis follows a dynamical-systems approach: a stochastic Poincaré map, governing the one-cycle dynamics of the polling system is introduced, and its statistical characteristics are studied. Explicit formulae regarding the evolution of the mean, covariance, and Laplace transform of the Poincaré map are derived. The forward orbit of the maps transform – a nonlinear deterministic dynamical system in Laplace space – fully characterizes the stochastic dynamics of the polling system. This enables us to explore the long-term behavior of the system: we prove convergence to a (unique) steady-state equilibrium, prove the equilibrium is stationary, and compute its statistical characteristics.     

随机服务时间下异质患者门诊预约调度优化

考虑随机服务时间与行为特征互不相同的异质患者,建立随机混合整数规划模型对门诊预约调度问题展开研究。首先在给定服务顺序的假设下求解了两个患者的预约调度问题;在此基础上,设计启发式算法对多个患者预约方案和服务顺序同时进行优化。数值结果表明:当患者服务时间为独立同分布的随机变量时,患者预约时间间隔呈现先增加后减少的圆顶形状;当患者服务时间服从不同分布时,通过与样本平均近似方法对比,验证了启发式算法的计算效率和有效性。