Search

Some discrepancies in an earlier paper describing a bulk service queuing situation with customer balking or reneging are pointed out. Necessary modifications to make the model more valid are incorporated in a reformulation and an approach for developing the state-time probabilities of the system is suggested. [ABSTRACT FROM AUTHOR]

This paper discusses the following model: (i) Arriving customers are accepted in the system in a time interval [t[sub0], t'] and are rejected with compensation after time t'; (ii) the server runs at the cost rate r[sub0] in a time interval [t[sub0], T], t[sub0]≤t' ≤ T, and runs at the increased cost rate r[sub1](r[sub1] > r[sub0]) after the closing time T, until the system becomes empty after time t'. The time t' is called the rejection time. The paper finds the optimal rejection time, that is, the rejection time that minimizes the expected total cost. It can be shown that in certain cases the optimal rejection time can be determined by a nonlinear equation. Numerical examples are given for an M/M/1 queuing system, and the more generalized model is briefly discussed. [ABSTRACT FROM AUTHOR]

This paper provides the solution to the problem of the distribution of busy periods of the single-channel queue characterized by a time-dependent Poisson-distributed arrival rate and a general class of holding times. The notation is chosen in such a fashion that the main body of computations and mathematical analysis is identical with what was required in the solution of the general queuing equations considered in a previous paper which should be read first [4]. The solution of the problem for winch the traffic intensity is constant and the holding time distribution is Pearson type III is derived in closed form in terms of the Ink functions introduced previously. [ABSTRACT FROM AUTHOR]

In this paper the authors study the queues that build up in a minor stream of traffic waiting to cross or merge with a major stream The criterion for joining or crossing is that a gap between veincles in the major stream be greater than or equal to some constant value Several authors have studied the case where bulk service is provided for the minor stream queue with the appearance of each gap, in this paper the authors emphasize the higher flow rate situations where one car in the minor stream queue is released in a first-come first-serve fashinon with the appearance of a gap It is assumed that the minor stream is Poisson-fed while the intervehicle headways inq the major stream are arbitrary but identically and independently distributed random variables. [ABSTRACT FROM AUTHOR]

In "Capacity Analysis of Sequential Zone Picking Systems" by van der Gaast, De Koster, Adan, and Resing, a capacity model for sequential zone picking systems is developed. These systems are popular internal transport and order-picking systems in practice. The major disadvantage of such systems is congestion and blocking under heavy use, leading to long order throughput times. To reduce blocking and congestion, most systems use the block-and-recirculate protocol to dynamically manage workload. In their paper, the various elements of the system are modeled as a multiclass block-and-recirculate queueing network with capacity constraints on subnetworks. Because of this blocking protocol, the stationary distribution of the queueing network is highly intractable. The authors propose an approximation method based on jump-over blocking that allows realistically sized systems to be efficiently analyzed and can be used in the design phase of sequential zone picking systems. The results show that the relative error in the system throughput is typically less than 1% compared with simulation. This paper develops a capacity model for sequential zone picking systems. These systems are popular internal transport and order-picking systems because of their scalability, flexibility, high-throughput ability, and fit for use for a wide range of products and order profiles. The major disadvantage of such systems is congestion and blocking under heavy use, leading to long order throughput times. To reduce blocking and congestion, most systems use the block-and-recirculate protocol to dynamically manage workload. In this paper, the various elements of the system, such as conveyor lanes and pick zones, are modeled as a multiclass block-and-recirculate queueing network with capacity constraints on subnetworks. Because of this blocking protocol, the stationary distribution of the queueing network is highly intractable. We propose an approximation method based on jump-over blocking. Multiclass jump-over queueing networks admit a product-form stationary distribution and can be efficiently evaluated by mean value analysis and Norton's theorem. This method can be applied during the design phase of sequential zone picking systems to determine the number of segments, number and length of zones, buffer capacities, and storage allocation of products to zones to meet performance targets. For a wide range of parameters, the results show that the relative error in the system throughput is typically less than 1% compared with simulation. [ABSTRACT FROM AUTHOR]

In this paper we investigate the output process of the M/D/1 queuing system. We derive expressions for the distributions and first two moments, in both steady-state and transient conditions, of the following random variables: (1) the time until the nth departure measured from a departure epoch, To, (2) the time between the n--1st and nth departures after To, and (3) the number of departures in (T[sub 0], T[sub 0]+t]. Further we study the autocorrelation functions of random variables (1) and (2) in the steady state. [ABSTRACT FROM AUTHOR]

This paper considers a preemptive priority and a nonpreemptive priority queuing model in the steady state. Each model assumes two priority levels, a single-service channel, no queue-length limit, and negative exponential interarrival-time and service-time distributions. The paper develops a set of computationally efficient recursion formulas that allow exact calculation of the state probabilities. In the nonpreemptive-priority case, this is the first time that a complete solution for the equilibrium-state probabilities has been obtained. [ABSTRACT FROM AUTHOR]

This paper presents results in the ergodic theory of Markov chains that are useful in certain cases where the well known theory d Form and PAlm is not applicable. The paper gives the background leading to the results describes their significance, proves two theorems, and presents an example. The conditions for ergodicity are based on the notion of conditional single transition displacement of a Markov chain due to Pakes. [ABSTRACT FROM AUTHOR]

In this paper Kendall's technique of the embedded Markov chain[5] is applied to a queuing system `with general independent input and a wide class of service-time distributions The matrix of transition probabilities is found to be formally identical `with that discussed in our earlier study,[9] which will be taken as read in the present paper Using the results of reference 9 we can write down the equilibrium distribution of waiting-times for customers in the more general system in terms of the roots of a transcendental equation An example is considered that arose in Bailey's study of hospital systems[1] [ABSTRACT FROM AUTHOR]

This article presents a comment on the article "A queuing Model for Unitized Cargo Generation," by A. Novaes and E. Frankel, published in the January-February, 1966 issue of the journal "Operations Research." It describes a model in which customers balk with a probability depending on a function of the queue size. This note attempts to rectify the inaccuracies of their article. The same notation as theirs is adopted here to ease recognition of the differences.

Presents several letters to the editor commenting on issues related to distribution theory of economics. Comments on the article "The Remaining Busy Period for a Single Server Queue With Poisson Input;" Discussion on non-optimality of planned replacement in intervals of decreasing failure rate; Assumptions on a known failure distribution F(t) with failure rate q(t).

This paper considers a special queue situation, one in which a single facility serves two major priority classes of customers. Within each class, there are several levels of priorities. The first class has the higher priority. On arrival, a customer of the first class immediately replaces any customer of lower priority being sewed. The second class has the lower priority, as compared to the first class. On its arrival, a customer of the second class cannot interrupt the current service of a lower priority customer in the system; it must wait until the service is completed. The first class is the preemptive priority, and the second class is the nonpreemptive priority. This paper formulates a theoretical solution for this queuing system, which has a wide range of application in the computer industry. The real-time control program under the multiprogramming environment is an analog of this priority queuing model. [ABSTRACT FROM AUTHOR]

A system consisting of two buffers, each with independent fluid sources, is considered in this paper. Due to ease of implementation, the output capacities for the two buffers depend on the workload of only one of the buffers that is measured. A threshold-based policy is considered to dynamically assign output capacities for both buffers. Marginal workload distributions for the two buffers need to be evaluated for this policy. The key contribution of this paper is the performance analysis to derive the workload distribution in the two buffers. In addition, the paper also provides some guidelines to choose the output capacities for the two buffers as well as a mathematical program to determine an optimal threshold to dynamically switch between output capacities. Further, various applications of such systems to computer-communication networks are discussed. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of a single-stage hybrid production system that makes multiple types of products, some of which are made to-order while others are made to-stock. The analysis begins with a formal heavy traffic limit theorem of the production system, which is modeled as a mixed queueing network. Taking insights from the limit theorem, the analysis continues with the development of an approximation procedure. Numerical experiments indicate that this procedure provides good estimates for performance measures such as fill rates and average inventory levels. [ABSTRACT FROM AUTHOR]

This paper studies a queueing system with two groups of servers, each with a separate queue, and with arriving customers routed irrevocably to one of the two queues. One natural policy for muting arriving customers is to send them to the queue with the shortest expected delay. Although this shortest delay muting policy (SDR) is known to be optimal if each server group has one server and the service time distribution has nondecreasing failure rate, little is known about the general multiserver case, even with exponential service times. In this paper we show, using a theoretical upper bound, that an optimal policy would produce delays that are almost identical to what would result from combining the two groups. In addition, our simulation results show that SDR performs nearly optimally in every case considered. [ABSTRACT FROM AUTHOR]

Light traffic results about delay in queue are obtained for r single-channel queues in tandem with Poisson arrivals where the r service times of the same customer at different stations have an arbitrary joint distribution. By light traffic, we mean asymptotic behavior as server utilization approaches zero. A detailed analysis of delay at the second station is presented for r = 2. An expression for expected delay is obtained for r = 3. Methods developed for these purposes may be used for arbitrary r > 3. For arbitrary r, an expression for expected delay is obtained in the special case where the r service times of the same customer are equal. For exponential service, a simple closed form expression is obtained. For r = 2, it is shown that when service times are positively quandrant dependent, expected delay is greater than when service times are independent. In some cases, the ratio between expected delays in the dependent and independent cases is very large, particularly when r is large. This agrees with and generalizes published results in several papers and conflicts with results in one paper. An explanation for this conflict is given. [ABSTRACT FROM AUTHOR]

This note gives a rigorous proof of the queuing formula L=λW, using as hypotheses only that the limiting averages, λ and W, exist and are finite. The proof is related to one given in a previous paper by the author that used a discounted analogue and Tauberian theorems. The proof in the present paper, however, is direct and avoids the use of transforms. Some comments are offered on the relation between the proof and the heuristic arguments for L= λW commonly encountered in the literature. [ABSTRACT FROM AUTHOR]

This paper considers a special queue situation, one in which a single facility serves two major priority classes of customers. Within each class, there are several levels of priorities. The first class has the higher priority. On arrival, a customer of the first class immediately replaces any customer of lower priority being served. The second class has the lower priority, as compared to the first class. On its arrival, a customer of the second class cannot interrupt the current service of a lower priority customer in the system; it must wait until the service is completed. The first class is the preemptive priority, and the second class is the nonpreemptive priority. This paper formulates a theoretical solution for this queuing system, which !urn a wide range of application in the computer industry. The real-time control program under the multiprogramming environment is an analog of this priority queuing model. [ABSTRACT FROM AUTHOR]

This paper presents methods for computing point and interval estimates of descriptors of simulated queuing systems. The methods, which rely on the renewal process representation of certain processes, extend the results of CRANE and IGLEHART, and the author. In particular, the paper shows that computation of three sample quantities suffices to generate point and interval estimates for twelve system descriptors. [ABSTRACT FROM AUTHOR]

This paper discusses a class of queuing models in which the service time of a customer at a single-server facility is dependent on the amount that customer has spent queuing for service. A complete investigation is carried out in the particular case of exponential service times with the parameter having a step-function dependency on the waiting time. The stationary waiting-time distribution is investigated for the queue discipline by which customers are served in order of arrival. This class of model is particularly suited for applications wherein customer or item deterioration occurs during waiting, or where the server wishes to provide a more appropriate level of service to counter the negative effects of customer impatience and loss of good will. [ABSTRACT FROM AUTHOR]

The well known formula L= λW relates the time-average number in queue to the expected wait in queue of a customer. This paper specializes a more general formula, denoted by H= λG, in order to obtain relations between moments of L and W other than the first. The basic queue considered is G/G/k with stationary input. The special case where the arrival times form a renewal process and the more special case where they are a Poisson process are also discussed. [ABSTRACT FROM AUTHOR]

This paper studies a priority queuing model in which the processing times of jobs are known upon arrival and preemption without loss of time or processing already accomplished is possible. Jobs are classified into K types according to their lengths, priority is assigned to them according to type and the length of processing remaining, and the paper obtains the expected conditional response times for jobs of each type. [ABSTRACT FROM AUTHOR]

The mean length of a queue is normally estimated by a suitable mean of oh. served values. In order to determine the minimum sample size consistent with some required precision, it is necessary to know the standard error of the sample mean used. Since the observations ire dependent, this standard error is usually greater than the standard error for independent observations, so that a larger sample size is required, This paper derives expressions for the standard errors of some suitable estimators in the cue of finite Markov queues, and examines the efficiencies of these estimators. [ABSTRACT FROM AUTHOR]

In order to discuss scheduling algorithms for time-sharing computer systems, this paper analyzes the M/G/1 queue under the well known round-robin (RR) discipline. Three models are considered: the constant-quantum RR model, the processor-shared (or zero-quantum RR) model, and the variable-quantum RR model. The paper proposes an effective calculating method for obtaining the expected response time under an arbitrary processing-time distribution with overhead. By the theoretical analysis, one can show how the response time is affected by the scheduling and processing-time distributions, as is demonstrated by some typical examples. [ABSTRACT FROM AUTHOR]

This paper compares the waiting times of customers under three priority rules: the order-of-arrival rule, the shortest processing time (within a generation) first, and the longest processing time (within a generation) first. In particular, the covariance matrix of the trivariate distribution of the equilibrium waiting times is obtained explicitly. [ABSTRACT FROM AUTHOR]

This paper finds sufficient conditions for the ergodicity and recurrence of irreducible and aperiodic Markov chains. They extend some of the ones commonly used. The paper also indicates their use in discussing a certain class of queuing problem with state dependent service times. [ABSTRACT FROM AUTHOR]

A fundamental question m long-range planning for the logistic support of an ocean area is the size and location of bases. The present paper proposes a measure of effectiveness, called the 'logistic effectiveness,' for a given set of bases supporting the region. This is done by a maximizing process. Then the sizes of the bases are varied, subject to a budgetary constraint, and an 'optimal base structure' found. For small numbers of bases, for instance three bases, the calculations may be done by hand. Two numerical examples are presented. The paper is intended as a contribution to theory and not for immediate practical application. [ABSTRACT FROM AUTHOR]

This paper starts by observing that any queuing system can be viewed as two symmetric queues, one of customers in line for service, and one of idle clerks, awaiting customers Usually at least one of the queues (the idle clerks) has a finite limit, but examples, such as passengers and taxis at a taxi stand, exist where both queues are unlimited In such cases, if arrival and service rates are independent of queue length, at least one of the queues is unstable and grows indefinitely as time passes In practice there has to be some factor that limits queue length, and a possible mechanism is to assume that both passengers and taxis become impatient and will leave if, after some fixed amount of time, they have not been 'serviced ' The equations governing such a system are developed and steady-state solutions are found It is shown that steady-state solutions always exist for both queues, the means and variances (which are finite) are given In the last part of the paper an application to inventory theory is suggested Here the backlog of orders corresponds to the queue of customers, and items in stock to the idle clerks It is assumed that orders not filled in a certain time are cancelled and that items are perishable and cannot be sold if stocked too long. [ABSTRACT FROM AUTHOR]

This article presents information about various books. Some of the books include: "An Introduction to Equilibrium Thermodynamics," by Robert P. Bauman, "Decision and Control: The Meaning of Operational Research and Management Cybernetics," by Stafford Beer, "A Bibliography of Critical Path Methods," by J. Farmer, "Applied Boolean Algebra: An Elementary Introduction," 2nd ed., by Franz E. Hohn, "Manpower Planning: Operational Research and Personnel Research," edited by W.N. Jessop, and "Applied Queuing Theory," by Alec M. Lee.

This paper proposes a simulation-based optimization (SO) method that enables the efficient use of complex stochastic urban traffic simulators to address various transportation problems. It presents a metamodel that integrates information from a simulator with an analytical queueing network model. The proposed metamodel combines a general-purpose component (a quadratic polynomial), which provides a detailed local approximation, with a physical component (the analytical queueing network model), which provides tractable analytical and global information. This combination leads to an SO framework that is computationally efficient and suitable for complex problems with very tight computational budgets. We integrate this metamodel within a derivative-free trust region algorithm. We evaluate the performance of this method considering a traffic signal control problem for the Swiss city of Lausanne, different demand scenarios, and tight computational budgets. The method leads to well-performing signal plans. It leads to reduced, as well as more reliable, average travel times. [ABSTRACT FROM AUTHOR]

In this paper a novel variational inequality (VI) formulation of the dynamic user optimal (DUO) route choice problem is proposed using the concept of approach proportion. An approach proportion represents the proportion of travelers that select a turning or through movement when leaving a node. Approach proportions contain travelers' route information so that the realistic effects of physical queues can be captured in a formulation when a physical-queue traffic flow model is adopted, and so that route enumeration and path-set generation can be avoided in the solution procedure. In addition, the simple structure of the approach proportion representation allows us to decompose the constraint set for solving large-scale DUO route choice problems. This paper also discusses the existence and uniqueness of the solutions to the VI problem and develops a solution algorithm based on the extragradient method to solve the proposed VI problem. This solution algorithm makes use of the decomposition property of the constraint set and is convergent if the travel time functions are pseudomonotone and Lipschitz continuous. It is not necessary to know the Lipschitz constant of the travel time functions in advance. Finally, numerical examples are given to demonstrate the properties of the proposed model and the performance of the solution algorithm. [ABSTRACT FROM AUTHOR]

In this paper we consider a single-server queue fed by K independent renewal arrival streams, each representing a different job class. Jobs are processed in a FIFO fashion, regardless of class. The total amount of work arriving to the system exceeds the server's capacity. That is, the nominal traffic intensity of the system is assumed to be greater than one. Jobs arriving to the system grow impatient and abandon the queue after a random amount of time if service has not yet begun. Interarrival, service, and abandonment times are assumed to be generally distributed and class specific. We approximate this system using both fluid and diffusion limits. To this end, we consider a sequence of systems indexed by n in which the arrival and service rates are proportional to n; the abandonment distribution remains fixed across the sequence. In our first main result, we show that in the limit as n tends to infinity, the virtual waiting time process converges to a limiting deterministic process. This limit may be characterized as the solution to a first-order ordinary differential equation (ODE). Specific examples are then presented for which the ODE may be explicitly solved. In our second main result, we refine the deterministic fluid approximation by showing that the fluid-centered and diffusion-scaled virtual waiting time process weakly converges to an Ornstein-Uhlenbeck process whose drift and infinitesimal variance both vary over time. This process may also be solved for explicitly, thus yielding approximations to the transient as well as steady-state behavior of the virtual waiting time process. [ABSTRACT FROM AUTHOR]

This paper proves a long-standing conjecture regarding the optimal design of the M/M/s queue. The classical Erlang delay formula is shown to be a convex function of the number of servers when the server utilization is held constant. This means that when the server utilization is held constant, the marginal decrease in the probability that all servers are busy in the M/M/s queue brought about by the addition of two extra servers is always less than twice the decrease brought about by the addition of one extra server. As a consequence, a method of marginal analysis yields the optimal number of servers that minimize the waiting and service costs when the server utilization is held constant. In addition, it is shown that the expected number of customers in the queue and in the system, as well as the expected waiting time and sojourn in the M/M/s queue, are convex in the number of servers when the server utilization is held constant. These results are useful in design studies involving capacity planning in service operations. The classical Erlang loss formula is also shown to be a convex function of the number of servers when the server utilization is held constant. [ABSTRACT FROM AUTHOR]

In two-moment decomposition approximations of queueing networks, the arrival process is modeled as a renewal process, and each station is approximated as a GI/G/1 queue whose mean waiting time is approximated based on the first two moments of the interarrival times and the service times. The departure process is also approximated as a renewal process even though the autocorrelation of this process may significantly affect the performance of the subsequent queue depending on the traffic intensity. When the departure process is split into substreams by Markovian random routing, the split processes typically are modeled as independent renewal processes even though they are correlated with each other. This cross correlation might also have a serious impact on the queueing performance. In this paper, we propose an approach for modeling both the cross correlation and the autocorrelation by a three-moment four-parameter decomposition approximation of queueing networks. The arrival process is modeled as a nonrenewal process by a two-state Markov-modulated Poisson process, viz., MMPP(2). The cross correlation between randomly split streams is accounted for in the second and third moments of the merged process by the innovations method. The main contribution of the present research is that both the cross correlation and the autocorrelation can be modeled in parametric decomposition approximations of queueing networks by integrating the MMPP(2) approximation of the arrival/departure process and the innovations method. We also present numerical results that strongly support our refinements. [ABSTRACT FROM AUTHOR]

Cross-selling is becoming an increasingly prevalent practice in call centers, due, in part, to its unique capability to allow firms to dynamically segment their callers and customize their product offerings accordingly. This paper considers a call center with cross-selling capability that serves a pool of customers that are differentiated in terms of their revenue potential and delay sensitivity. It studies the operational decisions of staffing, call routing, and cross-selling under various forms of customer segmentation. It derives near-optimal controls in each of the settings analyzed, and characterizes the impact of a more refined customer segmentation on the structure of these policies and the center's profitability. [ABSTRACT FROM AUTHOR]

Many primary care offices and other medical practices regularly experience long backlogs for appointments. These backlogs are exacerbated by a significant level of last-minute cancellations or "no-shows," which have the effect of wasting capacity. In this paper, we conceptualize such an appointment system as a single-server queueing system in which customers who are about to enter service have a state-dependent probability of not being served and may rejoin the queue. We derive stationary distributions of the queue size, assuming both deterministic as well as exponential service times, and compare the performance metrics to the results of a simulation of the appointment system. Our results demonstrate the usefulness of the queueing models in providing guidance on identifying patient panel sizes for medical practices that are trying to implement a policy of "advanced access." [ABSTRACT FROM AUTHOR]

This paper considers a multiproduct, single-server production system where both setup times and costs are incurred whenever the server changes product. The system is make-to-order with a per unit backlogging cost. The objective is to minimize the long-run average cost per unit time. Using a fluid model, we provide a closed-form lower bound on system performance. This bound is also shown to provide a lower bound for stochastic systems when scheduling is local or static, but is only an approximation when scheduling is global or dynamic. The fluid bound suggests both local and global scheduling heuristics, which are tested for the stochastic system via a simulation study. [ABSTRACT FROM AUTHOR]

Traditional research on routing in queueing systems usually ignores service quality related factors. In this paper, we analyze the routing problem in a system where customers call back when their problems are not completely resolved by the customer service representatives (CSRs). We introduce the concept of call resolution probability, and we argue that it constitutes a good proxy for call quality. For each call, both the call resolution probability (p) and the average service time (1/μ) are CSR dependent. We use a Markov decision process formulation to obtain analytical results and insights about the optimal routing policy that minimizes the average total time of call resolution, including callbacks. In particular, we provide sufficient conditions under which it is optimal to route to the CSR with the highest call resolution rate (pμ) among those available. We also develop efficient heuristics that can be easily implemented in practice. [ABSTRACT FROM AUTHOR]

In 1964, Kleinrock proposed a queueing discipline for a single-server queue in which customers from different classes accumulate priority as linear functions of their waiting time. At the instant that a server becomes free, it selects the waiting customer with the highest accumulated priority, provided that the queue is nonempty. He developed a recursion for calculating the expected waiting time for each class. In 2014, Stanford, Taylor, and Ziedins reconsidered this queue, which they termed the accumulating priority queue (APQ), and derived the waiting time distribution for each class. Kleinrock and Finkelstein in 1967 also studied an accumulating priority system in which customers' priorities increase as a power-law function of their waiting time. They established that it is possible to associate a particular linear APQ with such a power-law APQ, so that the expected waiting times of customers from all classes are preserved. In this paper, we extend their analysis to characterise the class of nonlinear APQs for which an equivalent linear APQ can be found, in the sense that, for identical sample paths of the arrival and service processes, the ordering of all customers is identical at all times in both the linear and nonlinear systems. [ABSTRACT FROM AUTHOR]

Redundancy is an important strategy for reducing response time in multi-server distributed queueing systems. This strategy has been used in a variety of settings, but only recently have researchers begun analytical studies. The idea behind redundancy is that customers can greatly reduce response time by waiting in multiple queues at the same time, thereby experiencing the minimum time across queues. Redundancy has been shown to produce significant response time improvements in applications ranging from organ transplant waitlists to Google's BigTable service. However, despite the growing body of theoretical and empirical work on the benefits of redundancy, there is little work addressing the questions of how many copies one needs to make to achieve a response time benefit, and the magnitude of the potential gains. In this paper we propose a theoretical model and dispatching policy to evaluate these questions. Our system consists of k servers, each with its own queue. We introduce the Redundancy- d policy, under which each incoming job makes copies at a constant number of servers, d, chosen at random. Under the assumption that a job's service times are exponential and independent across servers, we derive the first exact expressions for mean response time in Redundancy- d systems with any finite number of servers, as well as expressions for the distribution of response time which are exact as the number of servers approaches infinity. Using our analysis, we show that mean response time decreases as d increases, and that the biggest marginal response time improvement comes from having each job wait in only d = 2 queues. The e-companion is available at . [ABSTRACT FROM AUTHOR]

This paper considers the nonpreemptive priority queue with MAP (Markovian Arrival Process) arrivals. Since MAP is weakly dense in the class of stationary point processes, it is a fairly general arrival process. Service times of customers of each priority class are independent and identically distributed according to a general distribution function that may differ among priority classes. Using both the generating function technique and the matrix analytic method, we derive various formulas for the marginal queue length distribution of each class. Further, we provide the delay cycle analysis of the waiting time distribution of each class and characterize its Laplace-Stieltjes transform. [ABSTRACT FROM AUTHOR]

Power-tail distributions are those for which the reliability function is of the form x[sup-alpha] for large x. Although they look well behaved, they have the singular properly that E(X[supl] = infinity for all l greater than or equal to alpha. Thus it is possible to have a distribution with an infinite variance, or even an infinite mean. As pathological as these distributions seem to be, they occur everywhere in nature, from the CPU time used by jobs on main-frame computers to sizes of files stored on discs, earthquakes. or even health insurance claims. Recently, traffic on the "electronic super highway" was revealed to be of this type, too.In this paper we first describe these distributions in detail and show their suitability to model self-similar behavior, e.g., of the traffic stated above. Then we show how these distributions can occur m computer system environments and develop a so-called truncated analytical model that in the limit is power-tail. We study and compare the effects on system performance of a GI/M/1 model both for the truncated and the limit case, and demonstrate the usefulness of these approaches particularly for Markov modeling with LAQT (Linear Algebraic Approach to Queueing Theory, Lipsky 1992) techniques. [ABSTRACT FROM AUTHOR]

This paper explores a natural generalization of the classic tandem-queue model, designed specifically to represent make-to-stock production processes. In such systems, intermediate and finished goods can be produced and stored in advance of demand. We consider the simplest version of the model, where demand is a Poisson process, and the unit production times are exponentially distributed. We propose and test a tractable approximation scheme. The approximation appears to be quite accurate. [ABSTRACT FROM AUTHOR]

Motivated by a factory scheduling problem, we consider the problem of input control, subject to a specified product mix, and priority sequencing in a two-station muiticlass queueing network with general service time distributions and a general routing structure. The objective is to minimize the long-run expected average number of customers in the system subject to a constraint on the long-run expected average output rate. Under balanced heavy loading conditions, this scheduling problem is approximated by a control problem involving Brownian motion. A reformulation of this Brownian control problem was solved exactly in 1990 by L. M. Wein. In the present paper, this solution is interpreted in terms of the queueing network model in order to obtain an effective scheduling rule. The resulting sequencing policy dynamically prioritizes customers according to reduced costs calculated from a linear program. The input rule is a workload regulating input policy, where a customer is injected into the system whenever the expected total amount of work in the system for the two stations falls within a prescribed region. An example is presented that illustrates the procedure and demonstrates its effectiveness. [ABSTRACT FROM AUTHOR]

Many data switching systems have processors with arrival streams of regularly spaced tasks (e.g., individual bytes) requiring attention (e.g., directing the bytes to the appropriate outgoing line). In many of these systems the processor might also be required to handle other jobs (small maintenance routines or secondary tasks that await service in one or more other queues) as well. From the point of view of the primary queue of tasks, the processor ceases its service and takes a vacation. The performance of such a system is determined in part by the processor service schedule. In this paper, we define and analyze a model for investigating the waiting time probability distribution at the primary queue in terms of the primary task arrival rate, the service time distribution for the primary tasks, the probability distribution of the vacation duration, and the processor's service schedule. In addition, we discuss two characteristics of systems of this type that may have important design implications: (i) the steady-state waiting time probability distribution might be dependent upon the initial state of the system; and (ii) the waiting time might not decrease if the service time of the system decreases. [ABSTRACT FROM AUTHOR]

This paper develops a general framework for analyzing a wide class of vehicle dispatching strategies for bulk arrival, bulk service queues. We provide a simple derivation of the queue length transform for the embedded Markov chain, and present a new computational procedure for finding the moments of the queue length distribution. Extensive computational tests demonstrate that the new procedure is significantly faster and more stable than the standard method, from the literature, that requires solving a set of simultaneous linear equations. We give formulas for the mean and variance of the length of the queue for the general case of compound Poisson arrivals, random batch capacities, general service times and a general control strategy. [ABSTRACT FROM AUTHOR]

This paper shows that in the M/D/oo queueing system with service time S, the optimal way to estimate the expected number in the system is by sampling the system at time 0, S, 2S, ... , /cS. In this way, the best unbiased estimate from a sampling interval of length T = kS can be obtained. [ABSTRACT FROM AUTHOR]

This paper examines a class of M/G/S queuing reward systems with heterogeneous servers and heterogeneous customers. With the help of two simple results, we show that the policy that maximizes average reward per unit time over an infinite horizon possesses a certain structured form, which for several examples is quite intuitive and for others is not so intuitive. We also show that when the policy improvement method is used to find the optimal policy, only policies with the structured form need be considered, an obvious computational simplification. Computational results are discussed briefly. [ABSTRACT FROM AUTHOR]

In this paper we continue our study of efficient estimators for simulated queuing systems. We previously showed that it is more efficient to estimate the fiat moments of all the usual measures of performance from an estimate of mean wait in queue than to estimate them directly. Here we derive same new conservation equations that are them used to obtain efficient estimators of the variances of the usual measures of performance. We also introduce an estimator that is more efficient than the usual estimator for the probability that an arriving customer is blocked. [ABSTRACT FROM AUTHOR]

This paper considers two service stages in tandem with infinite queue capacity in front of each stage. There is a single server who performs the service in both stages by switching from one stage to the other when the number of customers in the active stage reaches the value zero. The arrival process is assumed to be Poisson and the service processes are independent renewal processes. The state probabilities are obtained in the steady-state case. In addition (for the steady-state case), the Laplace-Stieltjes transform is obtained for the time a customer waits until the beginning of service in each stage, for the busy period of the server, and for the busy period of each stage. [ABSTRACT FROM AUTHOR]