共查询到20条相似文献,搜索用时 0 毫秒
1.
This paper studies a scheduling control problem for a single-server multiclass queueing network in heavy traffic, operating in a changing environment. The changing environment is modeled as a finite-state Markov process that modulates the arrival and service rates in the system. Various cases are considered: fast changing environment, fixed environment, and slowly changing environment. In all cases, the arrival rates are environment dependent, whereas the service rates are environment dependent when the environment Markov process is changing fast, and are assumed to be constant in the other two cases. In each of the cases, using weak convergence analysis, in particular functional limit theorems for Poisson processes and ergodic Markov processes, it is shown that an appropriate “averaged” version of the classical \(c\mu \) -policy (the priority policy that favors classes with higher values of the product of holding cost \(c\) and service rate \(\mu \) ) is asymptotically optimal for an infinite horizon discounted cost criterion. 相似文献
2.
State space collapse with application to heavy traffic limits for multiclass queueing networks 总被引:3,自引:0,他引:3
Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks
for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration
of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO)
queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply
our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks,
we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these
solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson
[4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO
networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams
[41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the
solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority
disciplines.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
3.
4.
We study a single server queueing model with admission control and retrials. In the heavy traffic limit, the main queue and retrial queue lengths jointly converge to a degenerate two-dimensional diffusion process. When this model is considered with holding and rejection costs, formal limits lead to a free boundary curve that determines a threshold on the main queue length as a function of the retrial queue length, above which arrivals must be rejected. However, it is known to be a notoriously difficult problem to characterize this curve. We aim instead at optimizing the threshold on the main queue length independently of the retrial queue length. Our main result shows that in the small and large retrial rate limits, this problem is governed by the Harrison–Taksar free boundary problem, which is a Bellman equation in which the free boundary consists of a single point. We derive the asymptotically optimal buffer size in these two extreme cases, as the scaling parameter and the retrial rate approach their limits. 相似文献
5.
This study characterizes the behavior of large queue lengths in heavy traffic. We show that the distribution of the maximum
queue length in a random time interval for a queueing systems in heavy traffic converges to a novel extreme value distribution.
We also study the processes that record the times that the queue length exceeds a high level and the cumulative time the queue
is above the level. We show that these processes converge in distribution to compound Poisson processes.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
6.
We introduce a multiclass single-server queueing system in which the arrival rates depend on the current job in service. The system is characterized by a matrix of arrival rates in lieu of a vector of arrival rates. Our proposed model departs from existing state-dependent queueing models in which the parameters depend primarily on the number of jobs in the system rather than on the job in service. We formulate the queueing model and its corresponding fluid model and proceed to obtain necessary and sufficient conditions for stability via fluid models. Utilizing the natural connection with the multitype Galton–Watson processes, the Laplace–Stieltjes transform of busy periods in the system is given. We conclude with tail asymptotics for the busy period for heavy-tailed service time distributions for the regularly varying case. 相似文献
7.
Che Soong Kim 《Operations Research Letters》2006,34(5):548-556
A controlled single-server retrial queueing system is investigated. Customers arrive according to batch Markovian arrival process. The system has several operation modes which are controlled by means of a threshold strategy. The stationary distribution is calculated. Optimization problem is considered and a numerical example is presented. 相似文献
8.
《Optimization》2012,61(4):587-599
A method of generating probability distributions of the number of customers served in a busy period of a steady state single-server queueing system with univariate and multivariate inputs is described. A few moments in terms of the moments of the input distributions are derived. Some applications of the busy period distributions to such areas as branching processes, traffic flows, first passage problems, ballot theorems and waiting time distributions are briefly mentioned. 相似文献
9.
Anatolii A. Puhalskii 《Mathematical Methods of Operations Research》2013,78(1):119-148
The focus of this paper is on the asymptotics of large-time numbers of customers in time-periodic Markovian many-server queues with customer abandonment in heavy traffic. Limit theorems are obtained for the periodic number-of-customers processes under the fluid and diffusion scalings. Other results concern limits for general time-dependent queues and for time-homogeneous queues in steady state. 相似文献
10.
Equilibrium balking strategies in the observable single-server queue with breakdowns and repairs 总被引:1,自引:0,他引:1
We consider the Markovian single-server queue that alternates between on and off periods. Upon arriving, the customers observe the queue length and decide whether to join or balk. We derive equilibrium threshold balking strategies in two cases, according to the information for the server’s state. 相似文献
11.
Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
12.
Queueing Systems - Empirical studies have shown that traffic in communication networks exhibits long-range dependence. Cumulative network traffic is often thought to be well modelled by a... 相似文献
13.
We treat the GI/M/1 queue with a processor-sharing server, in the heavy traffic case. Using perturbation methods, we construct asymptotic expansions for the conditional sojourn time distribution of a tagged customer conditioned on the tagged customer's service time. The resulting approximation is simple in form and involves only the first three moments of the interarrival time distribution. 相似文献
14.
Shuangfeng Ma Xiuli Xu Huining Wang 《Journal of Applied Mathematics and Computing》2018,56(1-2):351-366
A discrete time Geo/Geo/1 queue with (m, N)-policy is considered in this paper. There are three operation periods being considered: high speed, low speed service periods and idle periods. With double thresholds policy, the server begins to take a working vacation when the number of customers is below m after a service and there is one customer in the system at least. What’s more, if the system becomes empty after a service, the server will take an ordinary vacation. Otherwise, high speed service continues if the number of customers still exceeds m after a service. At the vacation completion instant, servers resume their service if the quantity of customers exceeds N. Vacations can also be interrupted when the system accumulate customers more than the prefixed threshold. Using the quasi birth-death process and matrix-geometric solution methods, we derive the stationary queue length distribution and some system characteristics of interest. Based on these, we apply the queue to a virtual channel switching system and present various numerical experiments for the system. Finally, numerical results are offered to illustrate the optimal (m, N)-policy to minimize cost function and obtain practical consequence on the operation of double thresholds policy. 相似文献
15.
The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback. 相似文献
16.
We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1 queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies. 相似文献
17.
Recently telecommunication networks have been designed in order to transfer all types of information services such as voice, data and video. Next generation wireless networks has been developed to integrate the existing technologies and to support comprehensive services. As the traffics of diverse services have properties of timecorrelation and burstiness, unpredictable statistical fluctuation of traffic streams may cause congestion. To suggest a congestion control scheme which controls arrival rates according to the queue length, we consider an MMPP/G/1/K queue with queue length dependent arrival rates. The effect of system parameters on performance measures also is explained with the numerical examples. 相似文献
18.
We consider the long-range dependent cumulative traffic generated by the superposition of constant rate fluid sources having exponentially distributed intra start times and Pareto distributed durations with finite mean and infinite variance. We prove a sample path moderate deviation principle when the session intensity is increased and the processes are centered and scaled appropriately. The governing rate function is known from large deviation principles for the tail probabilities of fractional Brownian motion. We derive logarithmic tail asymptotics for associated queue length processes when the traffic loads an infinite buffer with constant service rate. The moderate deviation approximation of steady-state queue length tail probabilities is compared to those obtained by computer simulations. 相似文献
19.
In this paper we present a second-order nonlinear dynamical system modelling the interactions of trees and damaging insects in a forest. With this model we discuss the influence of acidic deposition, an increase of which can cause sudden insect infestations and the collapse of the forest ecosystem. The analysis is carried out by finding the bifurcations of the system and by proving that under suitable conditions, such bifurcations can be catastrophic. The conditions for bifurcation can be explicitly given, and this facilitates the biological interpretation of the results. 相似文献
20.
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) |