共查询到20条相似文献,搜索用时 0 毫秒
1.
A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation Bi, B
i
*
(s)
service time of a customer at queue i and its LST
- bi, bi
(2)
mean and second moment of Bi
- Ri, R
i
*
(s)
duration of switch-over period from queue i and its LST
- ri, ri
mean and second moment of Ri
- r, r(2)
mean and second moment of
i
N
=1Ri
- i
external arrival rate of type-i customers
- i
total arrival rate into queue i
- i
utilization of queue i; i=i
-
system utilization
i
N
=1i
- c=E[C]
the expected cycle length
- X
i
j
number of customers in queue j when queue i is polled
- Xi=X
i
i
number of customers residing in queue i when it is polled
- fi(j)
- X
i
*
number of customers residing in queue i at an arbitrary moment
- Yi
the duration of a service period of queue i
- Wi,Ti
the waiting time and sojourn time of an arbitary customer at queue i
- F*(z1, z2,..., zN)
GF of number of customers present at the queues at arbitrary moments
- Fi(z1, z2,..., zN)
GF of number of customers present at the queues at polling instants of queue i
- ¯Fi(z1, z2,...,zN)
GF of number of customers present at the queues at switching instants of queue i
- Vi(z1, z2,..., zN)
GF of number of customers present at the queues at service initiation instants at queue i
- ¯Vi(z1,z2,...,zN)
GF of number of customers present at the queues at service completion instants at queue i
The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories. 相似文献
2.
The present paper deals with the problem of calculating mean delays in polling systems with either exhaustive or gated service.
We develop a mean value analysis (MVA) to compute these delay figures. The merits of MVA are in its intrinsic simplicity and
its intuitively appealing derivation. As a consequence, MVA may be applied, both in an exact and approximate manner, to a
large variety of models. 相似文献
3.
In this paper we consider large deviations and admission control problems for a discrete-time Markovian polling system. The
system consists of two-parallel queues and multiple heterogeneous servers. The arrival process of each queue is a superposition
of mutually independent Markovian on/off processes, and the multiple servers serve independently the two queues according
to the so called Bernoulli service schedule. Using the large deviations techniques, we derive upper and lower bounds of the
overflow probabilities, and then we present an admission control criterion by which different Quality of Service (QoS) requirements for the two queues are guaranteed. 相似文献
4.
Laurent Massoulié 《Queueing Systems》1995,21(1-2):67-95
A stationary regime for polling systems with general ergodic (G/G) arrival processes at each station is constructed. Mutual independence of the arrival processes is not required. It is shown that the stationary workload so constructed is minimal in the stochastic ordering sense. In the model considered the server switches from station to station in a Markovian fashion, and a specific service policy is applied to each queue. Our hypotheses cover the purely gated, thea-limited, the binomial-gated and other policies. As a by-product we obtain sufficient conditions for the stationary regime of aG/G/1/ queue with multiple server vacations (see Doshi [11]) to be ergodic.Work presented at the INRIA/ORSA Conference on Applied Probability in Engineering, Computer and Communication Sciences, Paris, June 16–18, 1993. 相似文献
5.
We consider a multi-access communication channel such as a centrally-controlled polling system, a distributed token-based ring, or a bus network. A message priority-based polling procedure is used to control the access to the channel. This procedure requires the server to have no advance information concerning the number of messages resident at a station prior to its visit to the station. Messages arriving at each station belong to one of two priority classes: class-1 (high priority) and class-2 (low priority). Class-1 messages are served under an exhaustive service discipline, while class-2 messages are served under a limited service discipline. Class-1 messages have non-preemptive priority over class-2 messages resident at the same station. Using a fully symmetric system model, an exact expression for the sum of the mean waiting times of class-1 and class-2 messages is first derived. Upper and lower bounds for the mean message waiting times for each individual message class are then obtained.This work was supported by NFS Grant No. NCR-8914690, Pacific-Bell and MICRO Grant No. 90-135 and US West Contract No. D890701. 相似文献
6.
A. A. BorovkovR. Schassberger 《Stochastic Processes and their Applications》1994,50(2):253-262
The polling network considered here consists of a finite collection of stations visited successively by a single server who is following a Markovian routing scheme. At every visit of a station a positive random number of the customers present at the start of the visit are served, whereupon the server takes a positive random time to walk to the station to be visited next. The network receives arrivals of customer groups at Poisson instants, and all customers wait until served, whereupon they depart from the network. Necessary and sufficient conditions are derived for the server to be able to cope with the traffic. For the proof a multidimensional imbedded Markov chain is studied. 相似文献
7.
Vinod Sharma 《Queueing Systems》1994,16(1-2):115-137
The stability of a polling system with exhaustive service and a finite number of users, each with infinite buffers is considered. The arrival process is more general than a Poisson process and the system is not slotted. Stochastic continuity of the stationary distributions, rates of convergence and functional limit theorems for the queue length and waiting time processes have also been proved. The results extend to the gated service discipline. 相似文献
8.
The present paper deals with the problem of calculating queue length distributions in a polling model with (exhaustive) k-limited service under the assumption of general arrival, service and setup distributions. The interest for this model is
fueled by an application in the field of logistics. Knowledge of the queue length distributions is needed to operate the system
properly. The multi-queue polling system is decomposed into single-queue vacation systems with k-limited service and state-dependent vacations, for which the vacation distributions are computed in an iterative approximate
manner. These vacation models are analyzed via matrix-analytic techniques. The accuracy of the approximation scheme is verified
by means of an extensive simulation study. The developed approximation turns out to be accurate, robust and computationally
efficient.
This research is supported by the Technology Foundation STW, applied science division of NWO and the technology programme
of the Dutch Ministry of Economic Affairs. 相似文献
9.
F. Avram 《Operations Research Letters》2006,34(3):339-348
This paper deals with two M/M/1 queues served by a single server with threshold switching. Our main goal is to solve the Poisson equation and, as a result, give expressions for the long-run expected average cost of holding units and switching actions of the server, and the bias vector. 相似文献
10.
R. D. van der Mei 《Queueing Systems》2007,57(1):29-46
For a broad class of polling models the evolution of the system at specific embedded polling instants is known to constitute
a multi-type branching process (MTBP) with immigration. In this paper it is shown that for this class of polling models the
vector that describes the state of the system at these polling instants, say X=(X
1,…,X
M
), satisfies the following heavy-traffic behavior (under mild assumptions):
where γ is a known M-dimensional vector, Γ(α,μ) has a gamma-distribution with known parameters α and μ, and where ρ is the load of the system. This general and powerful result is shown to lead to exact—and in many cases even closed-form—expressions
for the Laplace-Stieltjes Transform (LST) of the complete asymptotic queue-length and waiting-time distributions for a broad
class of branching-type polling models that includes many well-studied polling models policies as special cases. The results
generalize and unify many known results on the waiting times in polling systems in heavy traffic, and moreover, lead to new
exact results for classical polling models that have not been observed before. To demonstrate the usefulness of the results,
we derive closed-form expressions for the LST of the waiting-time distributions for models with cyclic globally-gated polling
regimes, and for cyclic polling models with general branching-type service policies. As a by-product, our results lead to
a number of asymptotic insensitivity properties, providing new fundamental insights in the behavior of polling models.
Part of this research has been funded by the Dutch BSIK/BRICKS project. 相似文献
(1) |
11.
Jan A. Weststrate Rob D. van der Mei 《Mathematical Methods of Operations Research》1994,40(3):289-303
This paper deals with waiting times in a two-queue polling system in which one queue is served according to the Bernoulli service discipline and the other one attains exhaustive service. Exact results are derived for the LST's of the waiting time distributions via an iteration scheme. Based on those results the mean waiting times are expressed in the system parameters. 相似文献
12.
In this paper, we propose an ordinal optimization theory based algorithm to solve the optimization problem of G/G/1/K polling
system with k-limited service discipline for a good enough solution using limited computation time. We assume that the arrival rates do
not deteriorate visibly within a very short period. Our approach consists of two stages. In the first stage, we employ a typical
genetic algorithm to select N=1024 roughly good solutions from the huge discrete solution space Ω using an offline trained artificial neural network as
a surrogate model for fitness evaluation. The second stage consists of several substages to select estimated good enough solutions
from the previous N, and the solution obtained in the last substage is the good enough solution that we seek. Using numerous tests, we demonstrate:
(i) the computational efficiency of our algorithm in the aspect that we can apply our algorithm in real-time based on the
arrival rate assumption; (ii) the superiority of the good enough solution, which achieves drastic objective value reduction
in comparison with other existing service disciplines. We provide a performance analysis for our algorithm based on the derived
models. The results show that the good enough solution that we obtained is among the best 3.31×10−6% in the solution space with probability 0.99.
This research work was supported in part by the National Science Council of Taiwan, ROC, Grant NSC95-2221-E-009-099-MY2. 相似文献
13.
A Markov polling system with infinitely many stations is studied. The topic is the ergodicity of the infinite-dimensional
process of queue lengths. For the infinite-dimensional process, the usual type of ergodicity cannot prevail in general and
we introduce a modified concept of ergodicity, namely, weak ergodicity. It means the convergence of finite-dimensional distributions
of the process. We give necessary and sufficient conditions for weak ergodicity. Also, the “usual” ergodicity of the system
is studied, as well as convergence of functionals which are continuous in some norm.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
14.
We introduce a generalized criterion for the stability of Markovian queueing systems in terms of stochastic fluid limits.
We consider an example in which this criterion may be applied: a polling system with two stations and two heterogeneous servers.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
15.
Exact analysis of asymmetric random polling systems with single buffers and correlated input process
We introduce a simple approach for modeling and analyzing asymmetric random polling systems with single buffers and correlated input process. We consider two variations of single buffers system: the conventional system and the buffer relaxation system. In the conventional system, at most one customer may be resided in any queue at any time. In the buffer relaxation system, a buffer becomes available to new customers as soon as the current customer is being served. Previous studies concentrate on conventional single buffer system with independent Poisson process input process. It has been shown that the asymmetric system requires the solution ofm 2
m
–1) linear equations; and the symmetric system requires the solution of 2
m–1–1 linear equations, wherem is the number of stations in the system. For both the conventional system and the buffer relaxation system, we give the exact solution to the more general case and show that our analysis requires the solution of 2
m
–1 linear equations. For the symmetric case, we obtain explicit expressions for several performance measures of the system. These performance measures include the mean and second moment of the cycle time, loss probability, throughput, and the expected delay observed by a customer. 相似文献
16.
The LIFO service discipline maximizes throughput for certain queuing systems with delay-dependent customer behavior. To study the effects of priorities in such a system, we obtain delay distributions for each customer class of a K-class, single server system with nonpreemptive priorities and LIFO within each queue. 相似文献
17.
Typical formulations of thep-median problem on a network assume discrete nodal demands. However, for many problems, demands are better represented by continuous functions along the links, in addition to nodal demands. For such problems, optimal server locations need not occur at nodes, so that algorithms of the kind developed for the discrete demand case can not be used. In this paper we show how the 2-median of a tree network with continuous link demands can be found using an algorithm based on sequential location and allocation. We show that the algorithm will converge to a local minimum and then present a procedure for finding the global minimum solution. 相似文献
18.
The three node Jackson queueing network is the simplest acyclic network in which in equilibrium the sojourn times of a customer at each of the nodes are dependent. We show that assuming the individual sojourn times are independent provides a good approximation to the total sojourn time. This is done by simulating the network and showing that the sojourn times generally pass a Kolmogorov-Smirnov test as having come from the approximating distribution. Since the sum of dependent random variables may have the same distribution as the sum of independent random variables with the same marginal distributions, it is conceivable that our approximation is exact. However, we numerically compute upper and lower bounds for the distribution of the total sojourn time; these bounds are so close that the approximating distribution lies outside of the bounds. Thus, the bounds are accurate enough to distinguish between the two distributions even though the Kolmogorov-Smirnov test generally cannot. 相似文献
19.
Ángela Jiménez‐Casas Aníbal Rodríguez‐Bernal 《Mathematical Methods in the Applied Sciences》2017,40(11):3982-4000
Starting form basic principles, we obtain mathematical models that describe the traffic of material objects in a network represented by a graph. We analyze existence, uniqueness, and positivity of solutions for some implicit models. Also, some linear models and their equilibria are analyzed. Copyright © 2017 John Wiley & Sons, Ltd. 相似文献
20.
We give a closed-form expression for the discounted weighted queue length and switching costs of a two-class single-server queueing model under a preemptive priority rule. These expressions are used to do a single step of policy iteration in a polling model with a dynamically controlled switching rule, starting from the preemptive priority rule. Numerical experiments show that this leads to a policy that performs well. 相似文献