Refine
Year of publication
Document Type
- Article (18)
- ZIB-Report (17)
- In Proceedings (3)
Language
- English (38)
Is part of the Bibliography
- no (38)
Keywords
- sojourn time (5)
- state-dependent processor sharing (4)
- waiting time (3)
- M/GI/m-PS (2)
- busy period (2)
- factorial moments (2)
- freed carried traffic (2)
- impatient customers (2)
- moments (2)
- occupancy distribution (2)
Institute
- Mathematical Optimization (26)
- ZIB Allgemein (12)
The paper deals with the workload and busy period for the M/GI/1
system under FCFS discipline, where the customers may become
impatient during their waiting for service with generally
distributed maximal waiting times and also during their service
with generally distributed maximal service times depending
on the time waited for service. This general impatience mechanism,
originally introduced by Kovalenko (1961) and considered
by Daley (1965), too, covers the special cases of impatience
on waiting times as well as impatience on sojourn times,
for which Boxma et al. (2010), (2011) gave new results
and outlined special cases recently. Our unified approach
bases on the vector process of workload and busy time.
Explicit representations for the LSTs of workload and
busy period are given in case of phase-type distributed
impatience.
The paper deals with the workload and busy period for the M/GI/1 system under FCFS discipline, where the customers may become impatient during their waiting for service with generally distributed maximal waiting times and also during their service with generally distributed maximal service times depending on the time waited for service. This general impatience mechanism, originally introduced by Kovalenko (1961) and considered by Daley (1965), too, covers the special cases of impatience on waiting times as well as impatience on sojourn times, for which Boxma et al. (2010), (2011) gave new results and outlined special cases recently. Our unified approach bases on the vector process of workload and busy time. Explicit representations for the LSTs of workload and busy period are given in case of phase-type distributed impatience.
We consider a system where the arrivals form a Poisson process and the required service times of the requests are exponentially distributed. According to the generalized processor sharing discipline, each request in the system receives a fraction of the capacity of one processor which depends on the actual number of requests in the system. We derive systems of ordinary differential equations for the LST and for the moments of the conditional waiting time of a request with given required service time as well as a stable and fast recursive algorithm for the LST of the second moment of the conditional waiting time, which in particular yields the second moment of the unconditional waiting time. Moreover, asymptotically tight upper bounds for the moments of the conditional waiting time are given. The presented numerical results for the first two moments of the sojourn times in the $M/M/m-PS$ system show that the proposed algorithms work well.
On the Two-Class M/M/1 System under Preemptive Resume and Impatience of the Prioritized Customers
(2002)
The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times but finite expectation. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing results recently obtained by Choi et al. in case of deterministic maximal waiting times. For deterministic maximal waiting times partially new explicit formulae are given.
On the two-class $M/M/1$ system under preemptive resume and impatience of the prioritized customers
(2004)
We consider a multi-queue multi-server system with $n$ servers (processors) and $m$ queues. At the system there arrives a stationary and ergodic stream of $m$ different types of requests with service requirements which are served according to the following $k$-limited head of the line processor sharing discipline: The first $k$ requests at the head of the $m$ queues are served in processor sharing by the $n$ processors, where each request may receive at most the capacity of one processor. By means of sample path analysis and Loynes' monotonicity method, a stationary and ergodic state process is constructed, and a necessary as well as a sufficient condition for the stability of the $m$ separate queues are given, which are tight within the class of all stationary ergodic inputs. These conditions lead to tight necessary and sufficient conditions for the whole system, also in case of permanent customers, generalizing an earlier result by the authors for the case of $n$=$k$=1.
We consider a single server system consisting of $n$ queues with different types of customers (Poisson streams) and $k$ permanent customers. The permanent customers and those at the head of the queues are served in processor-sharing by the service facility (head-of-the-line processor-sharing). The stability condition and a pseudo work conservation law will be given for arbitrary service time distributions; for exponential service times a pseudo conservation law for the mean sojourn times can be derived. In case of two queues and exponential service times, the generating function of the stationary distribution satisfies a functional equation being a Riemann-Hilbert problem which can be reduced to a Dirichlet problem for a circle. The solution yields the mean sojourn times as an elliptic integral, which can be computed numerically very efficiently. In case $n\ge 2$ a numerical algorithm for computing the performance measures is presented, which is efficient for $n=2,3$. Since for $n\ge 4$ an exact analytical or/and numerical treatment is too complex a heuristic approximation for the mean sojourn times of the different types of customers is given, which in case of a (complete) symmetric system is exact. The numerical and simulation results show that, over a wide range of parameters, the approximation works well.
In circuit switching networks call streams are characterized by their mean and peakedness (two-moment method). The $GI/M/C/0$ system is used to model a single link, where the $GI$-stream is determined by fitting moments appropriately. For the moments of the overflow traffic of a $GI/M/C/0$ system there are efficient numerical algorithms available. However, for the moments of the freed carried traffic, defined as the moments of a virtual link of infinite capacity to which the process of calls accepted by the link (carried arrival process) is virtually directed and where the virtual calls get fresh exponential i.i.d.\ holding times, only complex numerical algorithms are available. This is the reason why the concept of the freed carried traffic is not used rigorously. The main result of this paper is an efficient algorithm for computing the moments of the freed carried traffic, in particular an explicit formula for its peakedness. This result offers a unified handling of both overflow and carried traffics in networks. Furthermore, some refined characteristics for the overflow and freed carried streams are derived.
The paper is concerned with the analysis of an $s$ server queueing system in which the calls become impatient and leave the system if their waiting time exceeds their own patience. The individual patience times are assumed to be i.i.d.\ and arbitrary distributed. The arrival and service rate may depend on the number of calls in the system and in service, respectively. For this system, denoted by $M(n)/M(m)/s+GI$, where $m=\min(n,s)$ is the number of busy servers in the system, we derive a system of integral equations for the vector of the residual patience times of the waiting calls and their original maximal patience times. By solving these equations explicitly we get the stability condition and, for the steady state of the system, the occupancy distribution and various waiting time distributions. As an application of the \mbox{$M(n)/M(m)/s+GI$} system we give a performance analysis of an Automatic Call Distributor system (ACD system) of finite capacity with outbound calls and impatient inbound calls, especially in case of patience times being the minimum of constant and exponentially distributed times.
We consider a system with Poisson arrivals and i.i.d. service times. The requests are served according to the state-dependent processor sharing discipline, where each request receives a service capacity which depends on the actual number of requests in the system. The linear systems of PDEs describing the residual and attained sojourn times coincide for this system, which provides time reversibility including sojourn times for this system, and their minimal non negative solution gives the LST of the sojourn time $V(\tau)$ of a request with required service time $\tau$. For the case that the service time distribution is exponential in a neighborhood of zero, we derive a linear system of ODEs, whose minimal non negative solution gives the LST of $V(\tau)$, and which yields linear systems of ODEs for the moments of $V(\tau)$ in the considered neighborhood of zero. Numerical results are presented for the variance of $V(\tau)$. In case of an M/GI/2-PS system, the LST of $V(\tau)$ is given in terms of the solution of a convolution equation in the considered neighborhood of zero. For bounded from below service times, surprisingly simple expressions for the LST and variance of $V(\tau)$ in this neighborhood of zero are derived, which yield in particular the LST and variance of $V(\tau)$ in M/D/2-PS.
We deal with an infinite-server system where the
service speed is governed by a stationary and ergodic
process with countably many states. Applying a random
time transformation such that the service speed
becomes one, the sojourn time of a class of virtual
requests with given required service time is equal
in distribution to an additive functional defined
via a stationary version of the time-changed process.
Thus bounds for the expectation of functions of additive
functionals yield bounds for the expectation
of functions of virtual sojourn times, in particular
bounds for fractional moments and the distribution
function. Interpreting the $GI(n)/GI(n)/\infty$ system or
equivalently the $GI(n)/GI$ system under state-dependent
processor sharing as an infinite-server system with
random states given by the number $n$ of requests
in the system provides results for sojourn times
of virtual requests. In case of $M(n)/GI(n)/\infty$,
the sojourn times of arriving and added requests are
equal in distribution to sojourn times of virtual
requests in modified systems, which yields many results
for the sojourn times of arriving and added requests.
In case of integer moments, the bounds generalize
earlier results for $M/GI(n)/\infty$. In particular,
the mean sojourn times of arriving and added requests
in $M(n)/GI(n)/\infty$ are proportional to the required
service time, generalizing Cohen's famous result
for $M/GI(n)/\infty$.
We consider a $s$-server system with two FCFS queues, where the arrival rates at the queues and the service rate may depend on the number $n$ of customers being in service or in the first queue, but the service rate is assumed to be constant for $n>s$. The customers in the first queue are impatient. If the offered waiting time exceeds a random maximal waiting time $I$, then the customer leaves the first queue after time $I$. If $I$ is less than a given deterministic time then he leaves the system else he transits to the end of the second queue. The customers in the first queue have priority. The service of a customer from the second queue will be started if the first queue is empty and more than a given number of servers become idle. For the model being a generalization of the $M(n)/M(n)/s\!+\!GI$ system balance conditions for the density of the stationary state process are derived yielding the stability conditions and the probabilities that precisely $n$ customers are in service or in the first queue. For obtaining performance measures for the second queue a system approximation basing on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server. For an important special case a stochastic decomposition is derived illuminating the connection to the dynamics of the $M(n)/M(n)/s\!+\!GI$ system.