共查询到20条相似文献,搜索用时 15 毫秒
1.
We provide an approximate analysis of the transient sojourn time for a processor sharing queue with time varying arrival and
service rates, where the load can vary over time, including periods of overload. Using the same asymptotic technique as uniform
acceleration as demonstrated in [12] and [13], we obtain fluid and diffusion limits for the sojourn time of the Mt/Mt/1 processor-sharing queue. Our analysis is enabled by the introduction of a “virtual customer” which differs from the notion
of a “tagged customer” in that the former has no effect on the processing time of the other customers in the system. Our analysis
generalizes to non-exponential service and interarrival times, when the fluid and diffusion limits for the queueing process
are known. 相似文献
2.
M/G/1 type queueing systems whose arrival rate is a function of an independent continuous time Markov chain are considered.
We suggest a simple analytical approach which allows rigorous mathematical analysis of the stationary characteristics under
heavy traffic. Their asymptotic behaviour is described in terms of characteristics of the modulating process (defined as a
solution of a set of linear algebraic equations). The analysis is based on certain “semi-explicit” formulas for the performance
characteristics.
This research was supported by INTAS under grant No. 96-0828. 相似文献
3.
We consider an infinite-server queue, where the arrival and service rates are both governed by a semi-Markov process that
is independent of all other aspects of the queue. In particular, we derive a system of equations that are satisfied by various
“parts” of the generating function of the steady-state queue-length, while assuming that all arrivals bring an amount of work
to the system that is either Erlang or hyperexponentially distributed. These equations are then used to show how to derive
all moments of the steady-state queue-length. We then conclude by showing how these results can be slightly extended, and
used, along with a transient version of Little’s law, to generate rigorous approximations of the steady-state queue-length
in the case that the amount of work brought by a given arrival is of an arbitrary distribution.
相似文献
4.
Organizational simulations have been used in business, manufacturing, and engineering design tasks to gain insight into organizational process bottlenecks, and to improve the quality and efficiency of processes within these industries. As market pressures demand increased efficiencies within the health care industry, organizational simulation techniques could provide similar insight into the design of better medical care processes, or protocols, in medical organizations. To simulate the process of medical care within a specific organization however, requires models that can represent (1) unpredictable patient responses to care, (2) the flexibility needed to adapt to different patients, and (3) different preferences of health care professionals and the implicit preferences contained within the protocol. Using previous work on simulation in the Virtual Design Team (VDT), and an example protocol drawn from an existing protocol in bone marrow transplantation, we describe extensions to the VDT information-processing representation that will allow us to simulate the performance characteristics of a medical protocol used within a medical organization. Our representational extensions capture the uncertainty of medical care for patients, the activity flexibility within the organization, and the preferences of health care professionals that will make information-processing organizational simulations in the medical domain possible. We believe our representation will provide a robust simulation tool box that can be used to investigate the performance of specific medical protocols within different hospital settings, and explore organizational theory within the health care industry. 相似文献
5.
The paper develops the mathematics of the heavy traffic approach to the control and optimal control problem for multiplexing
systems, where there are many mutually independent sources which feed into a single channel via a multiplexer (or of networks
composed of such subsystems). Due to the widely varying bit rates over all sources, control over admission, bandwidth, etc.,
is needed to assure good performance. Optimal control and heavy traffic analysis has been shown to yield systems with greatly
improved performance. Indeed, the heavy traffic approach covers many cases of great current interest, and provides a useful
and practical approach to problems of analysis and control arising in modern high speed telecommunications. Past works on
the heavy traffic approach to the multiplexing problem concentrated on the uncontrolled system or on the use of the heavy
traffic limit control problem for applications, and did not provide details of the proofs. This is done in the current paper.
The basic control problem for the physical system is hard, and the heavy traffic approach provides much simplification. Owing
to the presence of the control, as well as to the fact that the cost function of main interest is “ergodic”, the problem cannot
be fully treated with “classical” methods of heavy traffic analysis for queueing networks. A basic result is that the optimal
average costs per unit time for the physical problem converge to the optimal cost per unit time for the limit stationary process
as the number of sources and the time interval goes to infinity. This convergence is both in the mean and pathwise senses.
Furthermore, a “nice” nearly optimal control for the limit system provides nearly optimal values for the physical system,
under heavy traffic, in both a mean and pathwise sense.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
6.
We study the behavior of the random arrival rule in claims problems with a large number of claimants. We assume that the amount
to divide is not too “small” compared with total claims, and each claim is not too “large” compared with any other positive
claims. Then, the random arrival rule behaves like the proportional rule as the number of claimants increases.
We are grateful to Yuki Funaki, William Thomson, and three referees for their comments. This work was supported by the Brain
Korea 21 Project in 2003 相似文献
7.
AN M/G/1 RETRIAL QUEUE WITH SECOND MULTI-OPTIONAL SERVICE, FEEDBACK AND UNRELIABLE SERVER 总被引:2,自引:0,他引:2
Li Jianghua Wang Jinting 《高校应用数学学报(英文版)》2006,21(3):252-262
An M/G/1 retrial queue with two-phase service and feedback is studied in this paper, where the server is subject to starting failures and breakdowns during service. Primary customers get in the system according to a Poisson process, and they will receive service immediately if the server is available upon arrival. Otherwise, they will enter a retrial orbit and are queued in the orbit in accordance with a first-come-first-served (FCFS) discipline. Customers are allowed to balk and renege at particular times. All customers demand the first “essential” service, whereas only some of them demand the second “multi-optional” service. It is assumed that the retrial time, service time and repair time of the server are all arbitrarily distributed. The necessary and sufficient condition for the system stability is derived. Using a supplementary variable method, the steady-state solutions for some queueing and reliability measures of the system are obtained. 相似文献
8.
Design of a production system with a feedback buffer 总被引:1,自引:0,他引:1
In this paper, we deal with an M/G/1 Bernoulli feedback queue and apply it to the design of a production system. New arrivals enter a “main queue” before processing.
Processed items leave the system with probability 1-p or are fed back with probability p into an intermediate finite “feedback queue”. As soon as the feedback queue is fully occupied, the items in the feedback
queue are released, all at a time, into the main queue for another processing. Using transform methods, various performance
measures are derived such as the joint distribution of the number of items in each queue and the dispatching rate. We then
derive the optimal buffer size which minimizes the overall operating cost under a cost structure.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
9.
This paper will briefly examine how Al Qaeda evolved from an insurgency assistance group to a terrorist network of sophistication
and global reach. It argues that Al Qaeda filled the needs of Islamist insurgencies and then developed into a complex system
of networks by co-opting other groups, hijacking their agendas and transforming their ideologies during the late 1990s to
the present. Al Qaeda thus has global and local aspects. Locally-oriented “associate” organizations may have somewhat variant
structures and will vary in their goals, targets, and ideology. In some ways, these groups are more vulnerable to discovery
by local authorities and disruption. They tend to lack the training, professionalism, education and capacity to ensure strict
security measures and discipline within their own ranks. They lack resources such as weaponry and human social capital, such
as experience or specific kinds of knowledge that Al Qaeda has been able to provide. Because they are only loosely coupled
to the parent organization, both parent and “child” network receive “force multiplier” benefits while minimizing risks and
costs. 相似文献
10.
This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing
networks and networks with interacting components or populations. The focus is on determining when these processes have product
form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions
of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The
main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product
form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such
a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson
arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally
balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of
networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form.
We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals
and departures. The study ends by describing how the results extend to networks with multi-class transitions.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
11.
A bulk-arrival single server queueing system with second multi-optional service and unreliable server is studied in this paper. Customers arrive in batches according to a homogeneous Poisson process, all customers demand the first "essential" service, whereas only some of them demand the second "multi-optional" service. The first service time and the second service all have general distribution and they are independent. We assume that the server has a service-phase dependent, exponentially distributed life time as well as a servicephase dependent, generally distributed repair time. Using a supplementary variable method, we obtain the transient and the steady-state solutions for both queueing and reliability measures of interest. 相似文献
12.
This paper considers a scheduling problem occurring in a specialized service system with parallel servers. In the system,
customers are divided into the “ordinary” and “special” categories according to their service needs. Ordinary customers can
be served by any server, while special customers can be served only by the flexible servers. We assume that the service time
for any ordinary customer is the same and all special customers have another common service time. We analyze three classes
of service policies used in practice, namely, policies with priority, policies without priority and mixed policies. The worst-case
performance ratios are obtained for all of these service policies. 相似文献
13.
Konstantin Avrachenkov Patrick Brown Natalia Osipova 《Annals of Operations Research》2009,170(1):21-39
We analyze the Two Level Processor Sharing (TLPS) scheduling discipline with the hyper-exponential job size distribution and
with the Poisson arrival process. TLPS is a convenient model to study the benefit of the file size based differentiation in
TCP/IP networks. In the case of the hyper-exponential job size distribution with two phases, we find a closed form analytic
expression for the expected sojourn time and an approximation for the optimal value of the threshold that minimizes the expected
sojourn time. In the case of the hyper-exponential job size distribution with more than two phases, we derive a tight upper
bound for the expected sojourn time conditioned on the job size. We show that when the variance of the job size distribution
increases, the gain in system performance increases and the sensitivity to the choice of the threshold near its optimal value
decreases.
The work was supported by France Telecom R&D Grant “Modélisation et Gestion du Trafic Réseaux Internet” no. 46129414. 相似文献
14.
In this paper, we show the use of Multivariate Time Series models, Markov Random Fields and Bayesian methodologies to solve
an applied ophthalmological problem related to the study of glaucoma. Glaucoma is a very serious and widely extended eye disease
characterized by a gradual decrease in the intensity of the patient’s sight. It is not, however, homogeneous over all the
visual field, and starts at one or several sites and gradually spreads to nearby sites. Measurement of the patient’s “seeing
threshold” at different points in the visual field is an important diagnostic tool for glaucoma and other diseases. It results
in a map with 52 numerical values, each of which represents the level of intensity perceived by the patient at that site,
and ranges from 0 (complete blindness) to 35 (exceptional vision). Additionally a “defect status” variable can be attached
at each site in the visual field. This variable would indicate whether the site is normal or defective. Using Bayesian methodologies,
the “defect status” process can be regarded as a parameter of the probability distribution of the thresholds and can be estimated
as the maximum of its posterior distribution. The stochastic model assumed for the observed “threshold”, given the “defect
status”, is a first order autoregressive integrated model (VARI(1,1)) in time, with first order homogeneous spatial correlation.
The defect status is modeled by using a Spatiotemporal Autologistic Model with non-homogeneous spatial dependence. This dependence
assumes that the propagation of the lesions follows the directions taken by the nerve fibers. MCMC methods are used to jointly
estimate the defect status, and parameters and hyperparameters of the model. 相似文献
15.
J. Sztrik 《Journal of Mathematical Sciences》2000,99(4):1476-1484
This paper deals with a first-come, first-served (FCFS) queueing model to analyze the asymptotic behavior of a heterogeneous
finite-source communication system with a single processor. Each source and the processor are assumed to operate in independent
random environments, allowing the arrival and service processes to be Markov-modulated ones. Each message is characterized
by its own exponentially distributed source and processing time with parameter, depending on the state of the corresponding
environment, that is, the arrival and service rates are subject to random fluctuations. Assuming that the arrival rates of
the messages are many times greater than their service rates (“fast” arrival), it is shown that the time to the first system
failure converges in distribution, under appropriate norming, to an exponentially distributed random variable. Some simple
examples are considered to illustrate the effectiveness of the method proposed by comparing the approximate results to the
exact ones.
Supported by the Hungarian National Foundation for Scientific Research (grant No. OTKA T14974/95).
Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part II. 相似文献
16.
This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine
for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory
levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate.
Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to
one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot
start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity
have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first
case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates
so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem.
The paper describes the implementation of the method, compares its results to various heuristic methods and provides some
insights towards actual applications. 相似文献
17.
This paper addresses the problem of scheduling activities in projects with stochastic activity durations. The aim is to determine
for each activity a gate—a time before it the activity cannot begin. Setting these gates is analogous to setting inventory
levels in the news vendor problem. The resources required for each activity are scheduled to arrive according to its gate.
Since activities’ durations are stochastic, the start and finish time of each activity is uncertain. This fact may lead to
one of two outcomes: (1) an activity is ready to start its processing as all its predecessors have finished, but it cannot
start because the resources required for it were scheduled to arrive at a later time. (2) The resources required for the activity
have arrived and are ready to be used but the activity is not ready to start because of precedence constraints. In the first
case we will incur a “holding” cost while in the second case, we will incur a “shortage” cost. Our objective is to set gates
so as to minimize the sum of the expected holding and shortage costs. We employ the Cross-Entropy method to solve the problem.
The paper describes the implementation of the method, compares its results to various heuristic methods and provides some
insights towards actual applications. 相似文献
18.
Vyacheslav M Abramov 《Annals of Operations Research》2006,141(1):19-50
The paper studies a multiserver retrial queueing system withm servers. Arrival process is a point process with strictly stationary and ergodic increments. A customer arriving to the system
occupies one of the free servers. If upon arrival all servers are busy, then the customer goes to the secondary queue, orbit,
and after some random time retries more and more to occupy a server. A service time of each customer is exponentially distributed
random variable with parameter μ1. A time between retrials is exponentially distributed with parameter μ2 for each customer. Using a martingale approach the paper provides an analysis of this system. The paper establishes the stability
condition and studies a behavior of the limiting queue-length distributions as μ2 increases to infinity. As μ2→∞, the paper also proves the convergence of appropriate queue-length distributions to those of the associated “usual” multiserver
queueing system without retrials. An algorithm for numerical solution of the equations, associated with the limiting queue-length
distribution of retrial systems, is provided.
AMS 2000 Subject classifications: 60K25 60H30. 相似文献
19.
Many service systems are appointment-driven. In such systems, customers make an appointment and join an external queue (also
referred to as the “waiting list”). At the appointed date, the customer arrives at the service facility, joins an internal
queue and receives service during a service session. After service, the customer leaves the system. Important measures of
interest include the size of the waiting list, the waiting time at the service facility and server overtime. These performance
measures may support strategic decision making concerning server capacity (e.g. how often, when and for how long should a
server be online). We develop a new model to assess these performance measures. The model is a combination of a vacation queueing
system and an appointment system. 相似文献
20.
Mark Jerrum 《Combinatorica》2006,26(6):733-742
The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following
examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially
to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance
of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases
of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is
likely to be computationally intractable.
* The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and
Physical Sciences Research Council. 相似文献