Call center operation model as a <Emphasis Type="Italic">MAP/PH/N/R−N</Emphasis> system with impatient customers

We analyze a multiserver queueing system with a finite buffer and impatient customers. The arrival customer flow is assumed to be Markovian. Service times of each server are phase-type distributed. If all servers are busy and a new arrival occurs, it enters the buffer with a probability depending on the total number of customers in the system and waits for service, or leaves the system with the complementary probability. A waiting customer may become impatient and abandon the system. We give an algorithm for finding the stationary distribution of system states and derive formulas for basic performance characteristics. We find Laplace-Stieltjes transforms for sojourn and waiting times. Numeric examples are given.     

Trace Machines for Observing Continuous-Time Markov Chains

In this paper, we study several linear-time equivalences (Markovian trace equivalence, failure and ready trace equivalence) for continuous-time Markov chains that refer to the probabilities for timed execution paths. Our focus is on testing scenarios by means of push-button experiments with appropriate trace machines and a discussion of the connections between the equivalences. For Markovian trace equivalence, we provide alternative characterizations, including one that abstracts away from the time instances where actions are observed, but just reports on the average sojourn times in the states. This result is used for a reduction of the question whether two finite-state continuous-time Markov chains are Markovian trace equivalent to the probabilistic trace equivalence problem for discrete-time Markov chains (and the latter is known to be solvable in polynomial time).     

MMAP|M|N queueing system with impatient heterogeneous customers as a model of a contact center

A multi-server queueing system with infinite buffer and impatient heterogeneous customers as a model of a contact center that processes incoming calls (priority customers) and e-mail requests (non-priority customers) is investigated. The arrival flow is described by a Marked Markovian Arrival Process (MMAP). The service time of priority and non-priority customers by a server has an exponential distribution with different parameters. The steady state distribution of the system is analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transforms of the sojourn and waiting time distribution are derived. The problem of optimal choice of the number of contact center agents under the constraint that the average waiting time of e-mail requests does not exceed a predefined value is numerically solved.     

Help desk center operating model as a two-phase queueing system

We consider a two-phase queueing system with a Markovian arrival flow as an operating model for a help desk center. The first phase is a multiserver system with a finite buffer and impatient customers. After getting service in the first phase, a customer either enters the second phase with an infinite buffer or quits the system. Service times at the first and second stages have phase-type distributions with different parameters. We obtain an existence condition for a stationary regime of the system. An algorithm for computing stationary probabilities and basic performance characteristics of the system is presented. Laplace-Stieltjes transforms for the distributions of sojourn and waiting times in the first and second phases are found. Results of numerical experiments are presented. Optimization problem for the system operation is solved numerically.     

从UML到GSPN的转换和性能分析方法

UML模型一般不能直接进行性能分析,需要利用模型转换的方法将其转换成其他分析模型,比如排队论、随机进程代数或者随机Petri网等模型。利用Eclipse平台上的Papyrus建立3种类型的UML模型(用例图、部署图和活动图)来对系统进行建模,并利用MARTE规范添加一些性能相关的信息;然后利用ATL实现UML模型到广义随机Petri网(GSPN)模型的转换,并使用XStream将上一步得到的GSPN模型转换成分析工具所支持的格式;最后利用基于GSPN的性能分析方法进行系统性能分析。同时给出了一系列性能指标的计算方法,如利用率、吞吐量、平均等待请求的数目以及响应时间等,可以考察系统性能的多个方面,方便系统设计和开发人员对系统性能进行分析和优化。     

Predicting departure times in multi-stage queueing systems

We develop an approximation model for the state-dependent sojourn time distribution of customers or orders in a multi-stage, multi-server queueing system, when interarrival and service times can take on general distributions. The model can be used to make probabilistic statements about the departure time of a customer or order, given the number and location of customers currently in process or waiting, and these probabilities can be recomputed while waiting at any point during the sojourn time. The model uses phase-type distributions and a new method to estimate the remaining processing times of customers in service when the sojourn time distribution is computed.     

GSPN models of bridged LAN configurations

Communication systems comprising several local area networks (LANs) interconnected by bridges are modeled with Generalized Stochastic Petri Nets (GSPNs). GSPN models are developed at different levels of detail, progressively abstracting from the detailed behavior of real systems, and exploiting symmetries present in simple interconnected LAN topologies by “folding” the detailed GSPN models. The numerical results obtained from the solution of GSPN models are validated against results of very detailed simulation experiments, and found in good agreement, even for the most abstract GSPN models. Advantages and drawbacks of the GSPN modeling approach are discussed at the end of the paper.     

On queueing systems with a fractional number of devices

Queueing systems with several servers and a special discipline whereby demands are successively received by servers until the servicing is completed are considered. Among these systems, there are such systems whose characteristics constantly depend on a certain positive parameter. Given integer values of the latter, the waiting probability and average sojourn time coincide with those calculated using the Erlang C formula. Therefore, these systems can be considered as generalizations of the classical M/M/s system to a fractional number of servers.     

Response times in a two-node queueing network with feedback

The study presented in this paper is motivated by the performance analysis of response times in distributed information systems, where transactions are handled by iterative server and database actions. We model system response times as sojourn times in a two-node open queueing network with a processor sharing (PS) node and a first-come-first-served (FCFS) node. External customers arrive at the PS node according to a Poisson process. After departing from the PS node a customer proceeds to the FCFS node with probability p, and with probability 1−p the customer departs from the system. After a visit to the FCFS node, customers are fed back to the PS node. The service requirements at both nodes are exponentially distributed. The model is a Jackson network, admitting a product-from solution for the joint number of customers at the nodes, immediately leading to a closed-form expression for the mean sojourn times in steady-state. The variance of the sojourn times, however, does not admit an exact expression—the complexity is caused by the possibility of overtaking. In this paper we propose a methodology for deriving simple, explicit and fast-to-evaluate approximations for the variance of the sojourn times. Numerical results demonstrate that the approximations are very accurate in most model instances.     

Waiting time distribution of a queueing system with postservice activity

In this paper, we consider a queueing system with postservice activity. During the time when the server is engaged in the postservice activity (wrap-up time), the waiting customer, if any, cannot receive his or her service. This type of queueing system has been used to model automatic call distribution (ACD) systems. We consider the waiting time distribution of the queueing system. Using the Markovian point process that can be expressed by the so-called Markovian arrival process (MAP), we derive the waiting time distribution in terms of the representing matrices of a particular MAP. Then we apply the Baker-Hausdorff lemma to the matrices and derive the conditional waiting time distribution in closed form by exploiting the specific structure of the matrices. As a byproduct, we give an explicit solution of the number of arrivals for the MAP.     

Sojourn times in fluid queues with independent and dependent input and output processes

Markov Fluid Queues (MFQs) are the continuous counterparts of quasi birth–death processes, where infinitesimally small jobs (fluid drops) are arriving and are being served according to rates modulated by a continuous time Markov chain. The fluid drops are served according to the First-Come–First-Served (FCFS) discipline. The queue length process of MFQs can be analyzed by efficient numerical methods developed for Markovian fluid models. In this paper, however, we are focusing on the sojourn time distribution of the fluid drops.In the first part of the paper we derive the phase-type representation of the sojourn time when the input and output processes of the queue are dependent. In the second part we investigate the case when the input and output processes are independent. Based on the age process analysis of the fluid drops, we provide smaller phase-type representations for the sojourn time than the one for dependent input and output processes.     

Discrete-time single-server finite-buffer queues under discrete Markovian arrival process with vacations

This paper treats a discrete-time single-server finite-buffer exhaustive (single- and multiple-) vacation queueing system with discrete-time Markovian arrival process (D-MAP). The service and vacation times are generally distributed random variables and their durations are integral multiples of a slot duration. We obtain the queue-length distributions at departure, service completion, vacation termination, arbitrary and prearrival epochs. Several performance measures such as probability of blocking, average queue-length and the fraction of time the server is busy have been discussed. Finally, the analysis of actual waiting time under the first-come-first-served discipline is also carried out.     

实时离散事件系统的动态反馈控制

本文研究了一类含确定性状态时间的实时离散事件系统的动态反馈控制问题.基于一定 语言的实时可控性的概念,证明了对给定实时离散事件系统G,存在完备监控器φ使L(φ/ Gr)=K的充分必要条件是K是闭及实时可控的,并得到了有关实时监控问题解存在的充要 条件.     

An example of modeling and evaluation of a concurrent program usingcolored stochastic Petri nets: Lamport's fast mutual exclusion algorithm

A colored generalized stochastic Petri net (CGSPN) model was used to study the correctness and performance of the Lamport concurrent algorithm to solve the mutual exclusion problem on machines lacking an atomic test and set instruction. In particular, a parametric formal proof of liveness is developed based on the structure and initial state of the model. The performance evaluation is based on a Markovian analysis that exploits the symmetries of the model to reduce the cost of the numerical solution. Both kinds of analysis are supported by efficient algorithms. The potential of the GSPN modeling technique is illustrated on an academic but nontrivial example of an application from distributed systems     

一种基于请求大小的固态盘I／O调度算法

对于同类型的I／O请求,基于闪存固态盘的请求响应时间与请求大小基本呈线性比例关系,并且固态盘的读写性能具有非对称性。针对该特性,提出一种基于请求大小的固态盘I／O调度（SIOS）算法,从I／O请求平均响应时间的角度提高固态盘设备的I／O性能。根据读写性能的非对称性,对读写请求进行分组并且优先处理读请求。在此基础上首先处理等待队列中的小请求,从而减少队列中请求的平均等待时间。采用SLC和MLC2种类型的固态盘进行实验,在5种测试负载的驱动下与Linux系统中的3种调度算法进行比较,对于SLC固态盘,SIOS平均响应时间分别减少18．4％、25．8％、14．9％、14．5％和13．1％,而对于MLC固态盘,平均响应时间分别减少16．9％、24．4％、13．1％、13．0％和13．7％,结果表明,SIOS能有效减少I／O请求的平均响应时间,提高固态盘存储系统的I／O性能。     

Studying the queue length in a single-server queuing system with unreliable server

The unreliable queuing system was studied in both the nonstationary and stationary modes. It was assumed that a Poisson flow of customers arrives to the system; the times of customer servicing and restoration of the server (servicing system) are random variables with arbitrary distributions; the flow of stable failures makes up the restoration process; the interfailure intervals are distributed hyperexponentially; and the waiting and sojourn times as well as the queue length are not limited.Translated from Avtomatika i Telemekhanika, No. 1, 2005, pp. 72–81.Original Russian Text Copyright © 2005 by Mikadze, Khocholava.This paper was recommended for publication by V.V. Rykov, a member of the Editorial Board     

A combined queueing network and stochastic Petri-net approach for evaluating the performability of fault-tolerant computer systems

In this paper the performability analysis of fault-tolerant computer systems using a hierarchical decomposition technique is presented. A special class of queueing network (QN) models, the so-called BCMP [4], and generalized stochastic Petri nets (GSPN) [1] which are often used to separately model performance and reliability respectively, have been combined in order to preserve the best modelling features of both.

A conceptual model is decomposed into GSPN and BCMP submodels, which are solved in isolation. Then, the remaining GSPN portion of the model is aggregated with flow-equivalents of BCMP models, in order to compute performability measures. The substitutes of BCMP models are presented by means of simple GSPN constructs, thereby preserving the 1st and 2nd moments of the throughput. A simple example of a data communication system where failed transmissions are corrected, is presented.     

Optimal balking strategies in single-server queues with general service and vacation times

In many service systems arising in OR/MS applications, the servers may be temporarily unavailable, a fact that affects the sojourn time of a customer and his willingness to join. Several studies that explore the balking behavior of customers in Markovian models with vacations have recently appeared in the literature. In the present paper, we study the balking behavior of customers in the single-server queue with generally distributed service and vacation times. Arriving customers decide whether to enter the system or balk, based on a linear reward-cost structure that incorporates their desire for service, as well as their unwillingness to wait. We identify equilibrium strategies and socially optimal strategies under two distinct information assumptions. Specifically, in a first case, the customers make individual decisions without knowing the system state. In a second case, they are informed about the server’s current status. We examine the influence of the information level on the customers’ strategic response and we compare the resulting equilibrium and socially optimal strategies.     

Optimal Hysteresis Control for an Unreliable BMAP/SM/1 System with Two Operation Modes

Optimal hysteresis control strategies are designed for single-server queueing systems with waiting, batch Markov flow, semi-Markovian service, and two operation modes. Operation modes are changed not instantaneously and the failures of the server in idle states occur in a Markovian flow.     

Sojourn time distributions and time scale separation results for multiclass state-dependent processor sharing systems with a finite service pool and exponential service requirements

The paper addresses multiclass processor sharing systems with general state-dependent service rates, exponential service requirements and a finite service pool. By considering the amount of service received by a permanent customer and associating this service with the evolution of a Markov Reward process, the sojourn time distribution is formulated in terms of a matrix exponential expression. When the service rates are balanced, this expression can be diagonalized. Tail asymptotics are also discussed. The matrix exponential expression is subsequently exploited towards the study of time scale separation regimes. Unlike the standard practice of assuming a distinct time scale per class, the paper groups more realistically all customer classes in two time scales. Provably tight approximations, of a known, small degree of error, are developed for the sojourn time distribution of a given class (with either fast or slow dynamics), in terms of reduced models containing only the customer classes operating in the same time scale. The approximation for the fast classes gives rise to further characterization of the tail behavior. Additionally, the paper studies another, more specialized variant of the time scale separation regime, in which the service rates take a special form that leads to even simpler approximations. Finally, it is shown that the essence of the main results applies also to the more general setting of service requirement distributions with Markovian phase-type form.