A stochastic recirculation system with random access

A model for a stochastic recirculation system with randomly accessed multiple heterogeneous servers, no waiting rooms, and exponentially-distributed service times is provided. In this system the units are assigned to one of the servers upon arrival by random mechanism. Units which find all servers busy recirculate and combine with the incoming arrivals and join those already in the system to initiate the next cycle. The equilibrium behavior of the internal and external stochastic processes of the system is analyzed using a two parameter approximation. A simulation model is also developed and its behavior is compared against the analytical model at the steady state. The model with randomly-accessed servers is compared to a single server model already established in the literature. The performance of the model is then examined for a wide range of parameter values to obtain conclusions about its optimal performances.     

Two-phase queueing system with unreliable servers under heavy load

We consider a two-phase queueing system with unreliable servers and a finite number of places in a buffer between phases. The servers work synchronously at phases. The ergodicity condition is obtained and the work of the system is studied under heavy traffic assumptions.     

Maximizing throughput in finite-source parallel queue systems

Motivated by the dispatching of trucks to shovels in surface mines, we study optimal routing in a Markovian finite-source, multi-server queueing system with heterogeneous servers, each with a separate queue. We formulate the problem of routing customers to servers to maximize the system throughput as a Markov Decision Process. When the servers are homogeneous, we demonstrate that the Shortest Queue policy is optimal, and when the servers are heterogeneous, we partially characterize the optimal policy and present a near-optimal and simple-to-implement policy. We use the model to illustrate the substantial benefits of pooling, by comparing it to the permanent assignment of customers to servers.     

PH/M/c可修排队系统

研究了一个修理工和c个服务台的可修排队系统.假设顾客的到达过程为PH更新过程,服务台在忙时与闲时具有不同的故障率.顾客的服务时间、服务台的寿命以及服务台的修理时间均服从指数分布.通过建立系统的拟生灭过程,得到了系统稳态分布存在的充要条件.利用矩阵几何解方法,给出了系统的稳态队长.在此基础上,得到了系统的某些排队论和可靠性指标.     

Convexity properties of the overflow in an ordered-entry system with heterogeneous servers

The overflow probability in an Erlang loss system is known to be decreasing convex in the number of servers. Here we consider the GI/M/m loss system with ordered entry and heterogeneous servers. We show that adding a sequence of servers with non-increasing (non-decreasing) service rates will yield a decreasing convex (log-concave) sequence of overflow probabilities. An optimal server allocation problem is solved as a direct application of these results.     

A blind policy for equalizing cumulative idleness

We consider a system with a single queue and multiple server pools of heterogeneous exponential servers. The system operates under a policy that always routes a job to the pool with longest cumulative idleness among pools with available servers, in an attempt to achieve fairness toward servers. It is easy to find examples of a system with a fixed number of servers, for which fairness is not achieved by this policy in any reasonable sense. Our main result shows that in the many-server regime of Halfin and Whitt, the policy does attain equalization of cumulative idleness, and that the equalization time, defined within any given precision level, remains bounded in the limit. An important feature of this policy is that it acts ‘blindly’, in that it requires no information on the service or arrival rates.     

Workforce cross-training decisions in field service systems with two job types

When job types are heterogeneous in a multi-server service system, pooling servers to reduce system delay requires cross-training. Managers should balance a reduction in customer waiting time with high service costs and possibly reduced server efficiency due to cross-training. In a field service system with two job types and a fixed number of servers, the determination of the mix of dedicated and cross-trained servers is a critical managerial decision. We were motivated by a real field service situation to study a model where the objective is to minimize the sum of the average service costs and the customer delay costs per unit time. We use simulation to investigate the impact of various system parameters such as the number of servers, server utilization, and server efficiency on the optimal workforce mix.     

Optimal assignment of servers to tasks when collaboration is inefficient

Consider a Markovian system of two stations in tandem with finite intermediate buffer and two servers. The servers are heterogeneous, flexible, and more efficient when they work on their own than when they collaborate. We determine how the servers should be assigned dynamically to the stations with the goal of maximizing the system throughput. We show that the optimal policy depends on whether or not one server is dominant (i.e., faster at both stations) and on the magnitude of the efficiency loss of collaborating servers. In particular, if one server is dominant then he must divide his time between the two stations, and we identify the threshold policy the dominant server should use; otherwise each server should focus on the station where he is the faster server. In all cases, servers only collaborate to avoid idleness when the first station is blocked or the second station is starved, and we determine when collaboration is preferable to idleness as a function of the efficiency loss of collaborating servers.     

The BMAP/PH/N retrial queue with Markovian flow of breakdowns

We consider a multi-server retrial queue with the Batch Markovian Arrival Process (BMAP). The servers are identical and independent of each other. The service time distribution of a customer by a server is of the phase (PH) type. If a group of primary calls meets idle servers the primary calls occupy the corresponding number of servers. If the number of idle servers is insufficient the rest of calls go to the orbit of unlimited size and repeat their attempts to get service after exponential amount of time independently of each other. Busy servers are subject to breakdowns and repairs. The common flow of breakdowns is the MAP. An event of this flow causes a failure of any busy server with equal probability. When a server fails the repair period starts immediately. This period has PH type distribution and does not depend on the repair time of other broken-down servers and the service time of customers occupying the working servers. A customer whose service was interrupted goes to the orbit with some probability and leaves the system with the supplementary probability. We derive the ergodicity condition and calculate the stationary distribution and the main performance characteristics of the system. Illustrative numerical examples are presented.     

The <Emphasis Type="Italic">M/G/k</Emphasis> Blocking System with Heterogeneous Servers

This paper considers the M/G/k blocking system under the assumption of servers whose service time distributions differ. Such a system has k servers each with a (possibly) different service time distribution, whose customers arrive in accordance with a Poisson process. They are served, unless all the servers are occupied. In this case they leave and do not return later (i.e. they are "blocked"). A generalization of the Erlang B-formula is given and it is shown that the latter is valid in the case of heterogeneous servers too, provided that all servers have equal mean service times. In the form of an appendix, the Engset formula also is generalized under the above assumption.     

Performance analysis of a constrained resource sharing system

We consider a queueing system where the servers are arranged in a circle, and each arriving customer requires a pair of resources that is shared by its server with the respective neighbors on either side. If either resource is being used, the customer is denied service. Customers arrive at each server according to independent Poisson processes, and lengths of service times at each server have an exponential distribution. We derive a closed-form formula for the expected fraction of busy servers at any time in terms of the number of servers and the utilization factor (defined as the arrival rate times the mean service-time duration). This allows us to evaluate system performance when these parameters are varied, and to determine whether denying service to arrivals at alternate servers improves performance. We relate the system to Dijkstra's dining philosophers problem, which is an abstraction for resource sharing in an operating system. This revised version was published online in June 2006 with corrections to the Cover Date.     

A scheduling problem for several parallel servers

In this paper, we study a scheduling problem of jobs from two different queues on several parallel servers. Jobs have exponentially distributed processing times, and incur costs per unit of time, until they leave the system, and there are no arrivals to the system at any time. The objective is to find the optimal strategy, i.e., to allocate the servers to the queues, such that the expected holding costs are minimized. We give a sufficient condition for which it is always optimal to allocate the servers only to jobs of a certain queue. Finally, the case of two servers is completely solved.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

Analysis of job assignment with batch arrivals among heterogeneous servers

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.     

Optimal resource allocation for multiqueue systems with a shared server pool

We study optimal allocation of servers for a system with multiple service facilities and with a shared pool of servers. Each service facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker can dynamically allocate servers to each facility, where adding more servers results in faster processing speeds but against higher utilization costs. The objective is to dynamically allocate the servers over the different facilities such that the sojourn-time constraints are met at minimal costs. This situation occurs frequently in practice, for example, in Grid systems for real-time image processing (iris scans, fingerprints). We model this problem as a Markov decision process and derive structural properties of the relative value function. These properties, which are hard to derive for multidimensional systems, give a full characterization of the optimal policy. We demonstrate the effectiveness of these policies by extensive numerical experiments.     

Computation of the steady state distribution for multi-server retrial queues with phase type service process

We consider a multi-server retrial queueing system with the Batch Markovian Arrival Process and phase type service time distribution. Such a general queueing system suits for modeling and decision making in many real life objects including modern wireless communication networks. Behavior of such a system is described by the level dependent multi-dimensional Markov chain. Blocks of the generator of this chain, which is the block structured matrix of infinite size, can have large size if the number of servers is large and distribution of service time is not exponential. Due to this fact, the existing in literature algorithms allow to compute key performance measures of such a system only for a small number of servers. Here we describe the algorithm that allows to compute the stationary distribution of the system for larger number of servers and numerically illustrate its advantage. Importance of taking into account correlation in the arrival process is numerically demonstrated.     

On the order of tandem queues

We consider the optimal order of servers in a tandem queueing system withm stages, an unlimited supply of customers in front of the first stage, and a service buffer of size 1 but no intermediate storage buffers between the first and second stages. Service times depend on the servers but not the customers, and the blocking mechanism at the first two stages is manufacturing blocking. Using a new characterization of reversed hazard rate order, we show that if the service times for two servers are comparable in the reversed hazard rate sense, then the departure process is stochastically earlier if the slower server is first and the faster server is second than if the reverse is true. This strengthens earlier results that considered individual departure times marginally. We show similar results for the last two stages and for other blocking mechanisms. We also show that although individual departure times for a system with servers in a given order are stochastically identical to those when the order of servers is reversed, this reversibility property does not hold for the entire departure process.     

Analysis of GI/M/n/n queueing system with ordered entry and no waiting line

This paper deals with a multi-server, finite-capacity queuing system with recurrent input and no waiting line. The interarrival times are arbitrarily distributed whereas service times are exponentially distributed. Moreover, the servers are heterogeneous and independent of each other. Arriving customers choose the server with the lowest index number among the empty servers. When all servers are busy at a time of an arrival, that arrival must leave the system without being served. The semi-Markov process method is used to describe this model and embedded Markov chain of the process is obtained. Furthermore, the Laplace–Stieltjes transform of the distribution of interoverflow times is derived which is the main objective of the paper. Finally, it is offered a new formulation for the loss probability which provides more efficient and rapid calculation is proposed.     

带有部分工作休假和休假中断的M/M/c排队

考虑了一个带有部分工作休假和休假中断的多服务台M/M/c排队.在休假期,d(d相似文献   

The effect of non-linear delay costs on workforce mix

This paper formulates a simple model to examine the appropriate mix of dedicated and flexible maintenance technicians (servers) required when total delay cost is a non-linear function of mean delay time. The primary decision variable is the number of flexible servers needed to minimize system-related costs. Non-linear delay costs appear to significantly increase the level of cross-training required compared with previous research using a linear cost function, which showed that a small proportion of flexible servers was sufficient. This has important implications for service system designers in regard to the amount of cross-training that might be appropriate.