Search

The article presents the author's response to commentary regarding his management science paper "Critical Ratio Scheduling: An Experimental Analysis." He contends that the crux of his research was meant to evaluate the effectiveness of methods employed in the industry. The methods interpreted involved the use of job history data for estimation purposes. He explains that the queue time estimates were correctly used in the evaluation to estimate one portion of the shop time remaining also known as the queue waiting time.

The technique of perturbation analysis has recently been introduced as an efficient way to compute parameter sensitivities for discrete event systems. Thus far, the statistical properties of perturbation analysis have been validated mainly through experiments. This paper considers, for an M/G/1 queueing system, the sensitivity of mean system time of a customer to a parameter of the arrival or service distribution. It shows analytically that (i) the steady state value of the perturbation analysis estimate of this sensitivity is unbiased, and (ii) a perturbation analysis algorithm implemented on a single sample path of the system gives asymptotically unbiased and strongly consistent estimates of this sensitivity. (No previous knowledge of peturbation analysis is assumed, so the paper also serves to introduce this technique to the unfamiliar reader.) Numerical extensions to GI/G/1 queues, and applications to optimization problems, are also illustrated. [ABSTRACT FROM AUTHOR]

Yardstick competition is a regulatory scheme for local monopolists (e.g., hospitals), where the monopolist's reimbursement is linked to performance relative to other equivalent monopolists. This regulatory scheme is known to provide cost-reduction incentives and serves as the theoretical underpinning behind the hospital prospective reimbursement system used throughout the developed world. This paper uses a game-theoretic queueing model to investigate how yardstick competition performs in service systems (e.g., hospital emergency departments), where in addition to incentivizing cost reduction the regulator wants to incentivize waiting time reduction. We first show that the form of cost-based yardstick competition used in practice results in inefficiently long waiting times. We then demonstrate how yardstick competition can be appropriately modified to achieve the dual goal of cost and waiting-time reduction. In particular, we show that full efficiency (first-best) can be restored if the regulator makes the providers' reimbursement contingent on their service rates and is also able to charge a provider-specific "toll" to consumers. More important, if such a toll is not feasible, as may be the case in healthcare, we show that there exists an alternative and particularly simple yardstick-competition scheme, which depends on the average waiting time only, that can significantly improve system efficiency (second-best). This scheme is easier to implement because it does not require the regulator to have detailed knowledge of the queueing discipline. We conclude with a numerical investigation that provides insights on the practical implementation of yardstick competition for hospital emergency departments, and we also present a series of modelling extensions. The e-companion is available at https://doi.org/10.1287/mnsc.2018.3089. [ABSTRACT FROM AUTHOR]

In this paper, we study systems that allocate different types of scarce resources to heterogeneous allocatees based on predetermined priority rules—the U.S. deceased-donor kidney allocation system or the public housing program. We tackle the problem of estimating the wait time of an allocatee who possesses incomplete system information with regard, for example, to his relative priority, other allocatees' preferences, and resource availability. We model such systems as multiclass, multiserver queuing systems that are potentially unstable or in transient regime. We propose a novel robust optimization solution methodology that builds on the assignment problem. For first-come, first-served systems, our approach yields a mixed-integer programming formulation. For the important case where there is a hierarchy in the resource types, we strengthen our formulation through a drastic variable reduction and also propose a highly scalable heuristic, involving only the solution of a convex optimization problem (usually a second-order cone problem). We back the heuristic with an approximation guarantee that becomes tighter for larger problem sizes. We illustrate the generalizability of our approach by studying systems that operate under different priority rules, such as class priority. Numerical studies demonstrate that our approach outperforms simulation. We showcase how our methodology can be applied to assist patients in the U.S. deceased-donor kidney waitlist. We calibrate our model using historical data to estimate patients' wait times based on their kidney quality preferences, blood type, location, and rank in the waitlist. This paper was accepted by Yinyu Ye, optimization. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of job shops with a dispatch area and a machine shop, where operational controls are exercised at the dispatch area as well as at the machine shop. For such dynamic job shops with these two levels of control, there are three categories of models. They are (1) pseudo-static, (2) pure dynamic, and (3) pseudo-dynamic. In this paper approximate queueing models are developed for pure dynamic and pseudo-dynamic job shops; open queueing network models and controlled arrival single stage queueing models, respectively. The accuracy of the open queueing network models and their use are illustrated. An example indicative of the possible accuracy of the controlled arrival single stage queueing models is also given. [ABSTRACT FROM AUTHOR]

Queueing systems with interruptions serve as models for a variety of situations occurring in every day life. Usually, for each type of interruption, a separate queueing analysis is required. In this paper we present a single queueing model which can be used to analyze many such systems. The model is in the form of an approximation that is based upon several parameters, which reflect the particular queueing system under consideration. Applications to queueing systems with priorities and breakdowns are given in the paper. [ABSTRACT FROM AUTHOR]

Using the technique employed by the author in an earlier paper, the existence of an optimal stationary policy that can be obtained from the usual functional equation is again established in the presence of a bound (not necessarily polynomial) on the one-period reward of a semi-Markov decision process. This is done for both the discounted and the average cost case. In addition to allowing an uncountable state space, the law of motion of the system is rather general in that we permit any state to be reached in a single transition. There is, however, a bound on a weighted moment of the next state reached. Finally, we indicate the applicability of these results. [ABSTRACT FROM AUTHOR]

This paper studies the role of consistency as a signaling device. We propose a two-period model that highlights the informativeness of consistency as a signal of skills and allows for the analysis of consequences for behavior. In a simple principal-agent experiment, we test the basic intuition of the model. We show that consistency is indeed associated with skills. Consequently, consistency is valued by others, inducing people to act consistently. Data, as supplemental material, are available at . This paper was accepted by Uri Gneezy, behavioral economics. [ABSTRACT FROM AUTHOR]

The authors respond to commentary on their book, "Fundamentals of Queueing Theory." The commentary exists in the form of the article "On the Merits of an Approximation to the Busy Period of the GI / G / 1 Queue," by V. Ramaswami and David M. Lucantoni, published in the March 1, 1979 issue of the journal "Management Science." The authors disagree with Ramaswami's and Lucantoni's assertion that the findings in their book are absurd. Also noted are a number of expected deviations pointed out by the commentary.

Trace-driven (or correlated inspection) simulation means that the simulated and the real systems have some common inputs (say, historical arrival times) so that the two systems' outputs are cross-correlated. To validate such a simulation, this paper focuses on the difference between the average simulated and real responses. To evaluate this validation statistic, the paper develops a novel bootstrap technique--based on replicated runs. This validation statistic and the bootstrap technique are evaluated in extensive Monte Carlo experiments with specific single-server queues. These experiments show acceptable Type-I and Type-II error probabilities. [ABSTRACT FROM AUTHOR]

Utilizing a cyclic queue system, this paper investigates the effect of variance on a multi-item production facility. The variance of setup time, service rate and arrival rate is shown to have a powerful and sometimes paradoxical influence. Reduction in setup time, for example, is usually presumed to reduce inventory. We demonstrate that inventory can blow up if setup time is cut. Another paradoxical effect of variance is on processing rate. Speeding up the processing rate should reduce the material waiting to be processed. Again we show that the opposite can hold. Other properties of variance are examined, such as its relationship to KAIZEN and Just-In-Time production practices, and especially its property of impairing capacity. [ABSTRACT FROM AUTHOR]

In many manufacturing problems, the total lead time taken to manufacture a product is an important consideration. Long lead times impose costs due to higher work-in-process inventory, increased uncertainty about requirements, larger safety stocks and poorer performance to due dates. Traditional lot sizing models ignore lead time related costs, although there are systematic relationships between lot sizes and lead times. This paper examines these relationships and their implications for lot sizing and work-in-process inventories, for batch manufacturing shops with queues. [ABSTRACT FROM AUTHOR]

This paper extends recent work on finding the stochastic queue median (SQM) on a network. The SQM is the optimal location of a single mobile server, when idle, who travels to customers in response to requests for service. Customer demands are limited to the nodes of the network and their requests for service arrive according to a time homogeneous Poisson process, independently from each node. When a service request finds the server busy with a previous customer, it is entered into an M/G/1 queue that is depleted in a first-in, first-out (FIFO) manner. The SQM is the point on the network at which the sum of mean queueing delay and mean travel time is minimized. In this paper the transportation network is restricted to be a tree. By discovering and exploiting convex properties of the objective function and related functions, an efficient finite-step algorithm is found for locating the SQM on a tree. [ABSTRACT FROM AUTHOR]

This paper is concerned with queueing systems of several service stations in series in which each station may consist of multi-servers. An infinite number of customers always waits in front of the first station, and each customer passes through all of the stations in sequence. There is only a finite number of waiting positions between any two adjacent stations. The service time for a customer at any station is assumed to be a random variable, the distribution of which may depend on the station. In this mode of operation the servers at any station will at any time be busy, idle, or blocked. This blocking system is said to be C-reversible if the capacity remains invariant under reversal of the system. The reversed system is obtained by reversing the original stations' order, that is, every customer in the reversed system passes through the original stations in the reverse order. It has already been proved that C-reversibility holds for any blocking system in which each station consists of either a single server of nondeterministic service times or multi-servers of deterministic service times, and that the blocking system has a stronger property than C-reversibility. In this paper we show that two-station blocking systems with multi-server stations of nondeterministic service times are C-reversible, but this property can no longer be extended to three or more station blocking systems with multi-server stations of nondeterministic service times. We also show for the case of multi-server stations of nondeterministic service times that the stronger property which revolves invariance of distribution does not hold even for two-station blocking systems. [ABSTRACT FROM AUTHOR]

In a companion paper we developed a unified scheme for using poststratified sampling and control variables to improve the efficiency of regenerative queueing simulations. We adapted these variance reduction techniques to the estimation methods of replication analysis and regenerative analysis by exploiting the asymptotic joint normality of certain standardized concomitant variables that are defined on each input process sampled during a queueing simulation. In this paper we present an experimental evaluation of the reductions in point-estimator variance and confidence-interval width that can be achieved with each procedure in several closed and mixed machine-repair systems. For the analytically tractable model, nominal and actual confidence-interval coverage probabilities are also compared. Poststratification generally produced variance reductions ranging from 10% to 40% and confidence-interval reductions between 1% and 20%. The control-variates schemes yielded variance reductions ranging from 20% to 90% and confidence-interval reductions between 10% and 70%. In some instances where small sample sizes were used, the poststratification schemes produced confidence-interval width increases between 1% and 10%. With a small number of regenerative cycles, some loss of confidence-interval coverage was observed with both poststratified and controlled regenerative analysis. When larger sample sizes were used, all of the estimation schemes yielded fairly consistent efficiency gains. [ABSTRACT FROM AUTHOR]

This paper deals with the M/G/m queueing system with group arrivals. Using a diffusion approximation, we present approximate formulae for the steady-state distribution of the number of customers in the system. From this distribution, approximate formulae for some queueing characteristics such as the delay probability and the mean queue length are derived. In order to check the accuracy of the approximate formulae, they are numerically tested on some special cases. [ABSTRACT FROM AUTHOR]

Officers in police patrol cars operate in a complex stochastic environment. In addition to handling dispatcher-assigned calls for service from the public, they patrol to pose a threat of apprehension to would-be offenders and undertake certain on-site interventions to help improve general public safety. The on-site work, often highly discretionary, is called patrol-initiated activity. It includes issuing tickets for traffic violations, building checks, car checks, pedestrian checks and assisting motorists. In many cities patrol-initiated activities and calls for service consume comparable amounts of officers' time. In this paper we develop a spatially-oriented queueing-type model of a police patrol force that allows each of N patrol cars to be in one of three states: (1) busy, on a call for service; (2) busy, on a patrol-initiated activity; (3) free, on patrol. Designed for computer solution, the model yields N nonlinear equations whose unknowns are the workloads of the N patrol cars. Other performance measures of patrol can be computed easily in terms of the workloads. The incorporation of patrol-initiated activities represents an improvement over previous OR/MS models, and could result in more informed police management decisions regarding patrol beat design, workload smoothing among officers, and reduction of neighborhood-specific inequities in police accessibility. The methods of this paper are potentially applicable to other urban services, including taxi and maintenance operations. [ABSTRACT FROM AUTHOR]

This paper develops two distinct models for studying inventory systems with continuous production and perishable items. The perishable items have a deterministic usable life after which they must be outdated. For each of the models, analytical expressions derived from queueing theory, are found for the steady-state distribution of system inventory. Knowledge of this steady-state behavior may be used for evaluation of system performance, and for consideration of alternatives for improving system performance. Both models assume that inventory is replenished by a continuous production process. The first model, assuming continuous inventory units, has Poisson demand requests with the size of each request distributed as an exponential random variable. The second model has Poisson demand requests with all demands being for a single unit. The analysis for both models exploits the similarity of the inventory system with a single-server queueing system. [ABSTRACT FROM AUTHOR]

We study a queue with N servers, who may break down and require repair at a facility, which has c repair crews. Under exponential assumptions, this model has an algorithmically tractable solution. It is then in fact a particular case of the M/M/N queue in a Markovian environment. The purpose of this paper is twofold. As a novel methodological contribution, the stationary distributions of various waiting times are discussed. Although fairly involved, these distributions may be computed by classical numerical methods. The second and primary purpose is to demonstrate the utility of interactive computation in answering questions on the behavior, design and control of certain service systems. By numerical examples, we shall show that during periods when most servers are down, large build-ups may occur which affect the queue adversely for a long time afterwards. We also find that such build-ups are aggravated by reducing the number of repair crews, but may be attenuated by reducing the arrival rates during periods when the service has deteriorated. Potential applications are in manpower planning, as in a typing pool where persons may be absent and in determining the size of a battery of machines, where machines may be inoperative due to maintenance and repair. More generally, this paper draws attention to qualitative behavior of queues with randomly varying service rates. Such queues may exhibit substantial and long-lived fluctuations, which are not always apparent from simulation runs and which are also typically not present in the more classical queueing models. [ABSTRACT FROM AUTHOR]

This report is a sequel to our review paper, Lemoine [50], on the equilibrium analysis of networks of queues. In this paper we review some weak convergence results for networks of queues, which include heavy traffic limit theorems for open networks and asymptotic results for large closed Markovian systems which are generalizations of the classical repairman problem. These weak convergence results justify certain approximation schemes for processes of interest. We also discuss some important open problems in the area of weak convergence results for networks of queues, [ABSTRACT FROM AUTHOR]

Queueing network models abound in applications, but despite their importance many of the results for these models, both classical and recent, are not well known. The intent of this paper is to provide an overview of available equilibrium results for "general Jackson systems," that is, queueing network models of the sort introduced in the classical papers of Jackson [20], [21]. In addition, we discuss methodology which has been employed to obtain the equilibrium results and we call attention to some important open problems. Detailed discussions are limited to a small group of papers which seem important to us, and there is considerable emphasis on recent work appearing in the applied probability literature. The list of references does include, however, work not reviewed here, along with other survey and background material. [ABSTRACT FROM AUTHOR]

Queueing problems in which a customer having received a unit of service, returns to the waiting line, under some decision rule, to receive another unit of service occur often in applications. Inspection procedures provide such a framework for units that must be reworked. A large class of such problems appears in computer modelling under the name of round-robin models and foreground-background models. In the present paper, such a system is referred to as a queue with instantaneous feedback. Throughout the text it is assumed that there are two independent Poisson arrival processes giving two types of customers. Each type of customer has its own service time distribution. The decision to feedback (to receive another unit of service) or not is based on the type of customer completing service. Conditions for the existence of a steady slate queue length are found and some joint and marginal distribution of these queue lengths are given. Moreover it is shown that several earlier results in queueing and computer modelling can be obtained simply from the results given here. A particular case of the foreground-background model in computer systems analysis serves as an example. [ABSTRACT FROM AUTHOR]

This paper considers the problem of finding optimal stock levels for an inventory system with Poisson demands, arbitrary replacement time distribution, and emergency handling of shortages at a premium cost. The ordering policy is assumed to be of the (S - 1, S) type, i.e., a replacement item is ordered as soon as a unit of stock is used. A criterion for selecting the optimal stock level is formulated by minimizing the expected cost per unit time in steady state. Based on the fact that the probability of shortage for this model is given by the Erlang loss formula, it is possible to derive an approximate stocking level formula, which appears to be accurate over a wide range of parameter values. Comparisons with other related models and determination of achieved service levels are also discussed. [ABSTRACT FROM AUTHOR]

The previous papers in this series developed a methodology for obtaining from certain simulations confidence intervals for parameters associated with the steady-state distribution. This methodology required the simulations to contain an embedded renewal process at whose epochs the simulation started from scratch. The present paper contains four approximation techniques for obtaining confidence intervals when the simulation does not contain the required renewal process. [ABSTRACT FROM AUTHOR]

The D-policy is defined as a control policy which turns the server on when the total work to be done reaches the value D. This paper corrects the expression derived in an earlier paper for the expected cost per unit time. Consequently, the D-policy is shown to be superior to the Heyman, Yadin-Naor N-policy (which turns the server on when the queue size reaches the value N) for the service time distributions distributed as exponential, with decreasing failure rates and for some cases with increasing failure rates. [ABSTRACT FROM AUTHOR]

This paper relates to a queueing system with Poisson input and exponential service time, service taking place in batches under a 'general bulk service rule'. (A batch will contain no fewer than 'a' and no more than 'b' units.) The object of this paper is to study the waiting time distribution of such a bulk service system under steady state and also to indicate how the moments of the distribution can be obtained. [ABSTRACT FROM AUTHOR]

Classical queueing theory has typically focused on customers, and server availability has been taken for granted. However, data accessibility and the emergence of complex service systems, for example, call centers, revealed the need to stochastically model the complex behavior of servers. In this work, we propose a new model that accommodates such behavior; we call it Erlang-S, where "S" stands for servers. Our model assumes a pool of present servers, some of whom are available to serve customers from the queue while others are not, and the process of becoming available or unavailable is modeled explicitly. Our focus here is on applying the model to real systems, specifically call centers. Estimating the parameters of the new model from call-center data is challenging because reality is observed discretely in time as opposed to its continuous evolution. We therefore use an expectation-maximization algorithm that computes the expected number of relevant quantities given the discrete-time data. Erlang-S differs from the Erlang-A model, which has been commonly used for modeling call centers: the latter model assumes that all agents who are present are, in fact, available for service. When comparing predictions of the two models against call-center data, we find that Erlang-A generally overestimates queue length and consequently also the fraction of abandonment, and Erlang-S predicts reality more closely and usefully. Our conclusion is that it is important to model explicitly server dynamics to obtain accurate and valuable models of complex service systems. This paper was accepted by Gad Allon, stochastic models and simulation. [ABSTRACT FROM AUTHOR]

Queueing Theory has been attacked on two fronts. Some theoreticians say that Queueing Theory is closed. Some practitioners feel that there is very little in it for use. In view of this, it seems that after six decades of development it is time for stock taking. It is hoped that a discussion of the problems, achievements and the shortcomings of Queueing Theory will be helpful for both theorists and practitioners by putting things in proper perspective. This paper reviews some of the major strides taken by Queueing Theory with respect to its three constituent problems: (i) Behavioral, (ii) Statistical, and (iii) Operational. If one looks at the general picture of the developments in these area it is hard not to conclude that, in spite of the practitioners' accusations, the systems studied have become more and more realistic over the years. This review makes an attempt to bring this out. An extensive bibliography which is directive in nature rather than exhaustive should be helpful to an interested researcher or a practitioner in identifying the articles of his interest. A discussion of the future of Queueing Theory concludes the paper. [ABSTRACT FROM AUTHOR]

This paper analyzes a waiting line system that is motivated by the operations of border-crossing stations between the United States and Canada. There are two main conflicting goals in such a system: high security level, which often leads to a longer line; and good customer service, which requires a shorter line. Thus, unlike other queueing systems, maintaining the average queue length within a certain range is the primary objective. This is achieved using a staffing policy, called "congestion-based staffing," or CBS, where the number of servers (inspection booths) is adjusted according to the queue length during a planning period. We first present an exact benchmark model of Markovian type based on the matrix-geometric solution. For practical CBS policies, we develop a set of closed-form formulas for the major performance measures based on regenerative cycle analysis and fluid limit approximation. Numerical examples show that these approximation formulas are simple, accurate, and robust for practitioners to use in designing CBS policies. [ABSTRACT FROM AUTHOR]

This paper considers a profit-maximizing make-to-order manufacturer that offers multiple products to a market of price and delay sensitive users, using a model that captures three aspects of particular interest: first, the joint use of dynamic pricing and lead-time quotation controls to manage demand; second, the presence of a dual sourcing mode that can expedite orders at a cost; and third, the interaction of the aforementioned demand controls with the operational decisions of sequencing and expediting that the firm must employ to optimize revenues and satisfy the quoted lead times. Using an approximating diffusion control problem we derive near-optimal dynamic pricing, lead-time quotation, sequencing, and expediting policies that provide structural insights and lead to practically implementable recommendations. A set of numerical results illustrates the value of joint pricing and lead-time control policies. [ABSTRACT FROM AUTHOR]

Any buyer that depends on suppliers for the delivery of a service or the production of a make-to-order component should pay close attention to the suppliers' service or delivery lead times. This paper studies a queueing model in which two strategic servers choose their capacities/processing rates and faster service is costly. The buyer allocates demand to the servers based on their performance; the faster a server works, the more demand the server is allocated. The buyer's objective is to minimize the average lead time received from the servers. There are two important attributes to consider in the design of an allocation policy: the degree to which the allocation policy effectively utilizes the servers' capacities and the strength of the incentives the allocation policy provides for the servers to work quickly. Previous research suggests that there exists a trade-off between efficiency and incentives, i.e., in the choice between two allocation policies a buyer may prefer the less efficient one because it provides stronger incentives. We find considerable variation in the performance of allocation policies: Some intuitively reasonable policies generate essentially no competition among servers to work quickly, whereas others generate too much competition, thereby causing some servers to refuse to work with the buyer. Nevertheless, the trade-off between efficiency and incentives need not exist: It is possible to design an allocation policy that is efficient and also induces the servers to work quickly. We conclude that performance-based allocation can be an effective procurement strategy for a buyer as long as the buyer explicitly accounts for the servers' strategic behavior. [ABSTRACT FROM AUTHOR]

Most performance evaluation models in the operations management literature implicitly assume that tasks possess standardized completion criteria. However, in many systems, particularly service and professional work, judgment is frequently required to determine how much time to allocate to a task. In this paper, we show that introducing discretion in task completion adds a fourth variability buffer, quality, to the well-known buffers of capacity, inventory and time. To gain insight into the managerial implications of this difference, we model the work of one- and two-worker systems with discretionary task completion as controlled queues. After characterizing the optimal control policy and identifying some practical heuristics, we use this model to examine the differences between discretionary and nondiscretionary work. We show that in systems with discretionary task completion, (i) adding capacity may actually increase congestion, and (ii) task variability in service time can improve system performance. This implies that it may be suboptimal to expect shorter delays as a result of a capacity increase, and that task variability reduction may not be an appropriate goal in systems with discretionary task completion. We also find that the benefit of queue pooling is smaller in systems with discretionary task completion than in systems with nondiscretionary task completion. [ABSTRACT FROM AUTHOR]

This paper studies a queuing model in which a buyer sources a good or service from a single supplier chosen from a pool of suppliers. The buyer seeks to minimize the sum of her procurement and operating costs, the latter of which depends on the supplier's lead time. The selected supplier can regulate his lead time, but faster lead times are costly. Although the buyer selects the supplier to source from (possibly via an auction) and dictates the contractual terms, the buyer's bargaining power is limited by asymmetric information: The buyer only has an estimate of the suppliers' costs, while the suppliers know their costs precisely. We identify a procurement mechanism that minimizes the buyer's total cost (procurement plus operating). This mechanism is not simple: It is a numerically derived nonlinear menu of contracts. Therefore, we study several simpler mechanisms: e.g., one that charges a late fee and one that specifies a fixed lead-time requirement (no menus, no nonlinear functions). We find that simple mechanisms are nearly optimal (generally within 1% of optimal) because asymmetric information conveys significant protection to the supplier, i.e., the supplier is able to retain most of the benefit of having a lower cost. Renegotiation is another concern with the optimal mechanism: Because it does not minimize the supply chain's cost, the firms can be both better off if they throw away the contract and start over. Interestingly, we find that the potential gain from renegotiation is relatively small with either the optimal or our simple mechanisms. We conclude that our simple mechanisms are quite attractive along all relevant dimensions: buyer's performance, supply chain performance, simplicity, and robustness to renegotiation. [ABSTRACT FROM AUTHOR]

Reducing congestion is a primary concern in the design and analysis of queueing networks, especially in systems where sources of randomness are characterized by high variability. This paper considers a multiserver first-come, first-served (FCFS) queueing model where we arrange servers in two stations in series. All arrivals join the first service center, where they receive a maximum of T units of service. Arrivals with service requirements that exceed the threshold T join the second queue, where they receive their remaining service. For a variety of heavy tail service time distributions, characterized by large coefficient of variations, analytical and numerical comparisons show that our scheme provides better system performance than the standard parallel multiserver model in the sense of reducing the mean delay per customer in heavy traffic systems. Our model is likely to be useful in systems where high variability is a cause for degradation and where numerous service interruptions are not desired. [ABSTRACT FROM AUTHOR]

We address the modeling and analysis of abandonments from a queue that is invisible to its occupants. Such queues arise in remote service systems, notably the Internet and telephone call centers; hence, we refer to them as tele-queues. A basic premise of this paper is that customers adapt their patience (modeled by an abandonment-time distribution) to their service expectations, in particular to their anticipated waiting time. We present empirical support for that hypothesis, and propose an M/M/m-based model that incorporates adaptive customer behavior. In our model, customer patience depends on the mean waiting time in the queue. We characterize the resulting system equilibrium (namely, the operating point in steady state), and establish its existence and uniqueness when changes in customer patience are bounded by the corresponding changes in their anticipated waiting time. The feasibility of multiple system equilibria is illustrated when this condition is violated. Finally, a dynamic learning model is proposed where customer expectations regarding their waiting time are formed through accumulated experience. We demonstrate, via simulation, convergence to the theoretically anticipated equilibrium, while addressing certain issues related to censored-sampling that arise because of abandonments. [ABSTRACT FROM AUTHOR]

To optimize large-scale queuing systems configurations, OR professionals typically use discrete event simulation packages to examine in detail the movement of entities through such systems, assuming stochastic but fixed arrival patterns. Demand aspects are, however, routinely ignored as few attempts are made to capture the feedback effect of queue performance on the arrival process. Econometricians, on the other hand, use a simultaneous equations estimation approach relying on past data, but they typically disregard the technological insights provided by simulation. This paper combines both tools to study the ailing port system of Calcutta, India, and concludes that raising prices will improve both economic and engineering performances. Microeconomic models of shipowner behavior are constructed to explain the nature of the empirical findings. Finally, full-equilibrium demand elasticities are calculated using the dual prices from an appropriate nonlinear program, which are then compared to the benchmark value expected of profit-maximizing behavior. [ABSTRACT FROM AUTHOR]

This paper provides a proof of the symmetrical allocation property (SAP), conjectured in an earlier work on the workload allocation problem for a manufacturing flow line system. The system consists of N single-Erlang servers in series having a common interstation buffer capacity. SAP says a symmetric workload allocation exists among the optimal solutions. We first show the reciprocal of the throughput is increasing and jointly convex, not component-wisely, in workloads. Then we apply the line reversibility property to obtain an alternative optimal allocation symmetric for any optimal workload allocation that is asymmetric. A sufficient condition for SAP to hold is also given, which relaxes the hypothesizing assumptions on the service-time distribution and interstation buffer capacities. [ABSTRACT FROM AUTHOR]

The first in, first out (FIFO) queue discipline respects the order of arrivals, but is not efficient when customers have heterogeneous waiting costs. Priority queues, in which customers with higher waiting costs are served first, are more efficient but usually involve undesirable queue-jumping behaviors that violate bumped customers' property rights over their waiting spots. To have the best of both worlds, we propose time-trading mechanisms, in which customers who are privately informed about their waiting costs mutually agree on the ordering in the queue by trading positions. If a customer ever moves back in the queue, she will receive an appropriate monetary compensation. Customers can always decide not to participate in trading and retain their positions as if they are being served FIFO. We design the optimal mechanisms for the social planner, the service provider, and an intermediary who might mediate the trading platform. Both the social planner's and the service provider's optimal mechanisms involve a flat admission fee and an auction that implements strict priority. If a revenue-maximizing intermediary operates the trading platform, it should charge a trade participation fee and implement an auction with some trade restrictions. Therefore, customers are not strictly prioritized. However, relative to a FIFO system, the intermediary delivers value to the social planner by improving efficiency, and to the service provider by increasing its revenue. This paper was accepted by Noah Gans, stochastic models and simulation. [ABSTRACT FROM AUTHOR]

Cloud computing providers must constantly hold many idle compute instances available (e.g., for maintenance or for users with long-term contracts). A natural idea, which should intuitively increase the provider's profit, is to sell these idle instances on a secondary market, for example, via a preemptible spot market. However, this ignores possible "market cannibalization" effects that may occur in equilibrium as well as the additional costs the provider experiences due to preemptions. To study the viability of offering a spot market, we model the provider's profit optimization problem by combining queuing theory and game theory to analyze the equilibria of the resulting queuing system. Our main result is an easy-to-check condition under which a provider can simultaneously achieve a profit increase and create a Pareto improvement for the users by offering a spot market (using idle resources) alongside a fixed-price market. Finally, we illustrate our results numerically to demonstrate the effects that the provider's costs and her strategy have on her profit. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. [ABSTRACT FROM AUTHOR]

This paper investigates the possibility of predicting each customer's waiting time in queue before starting service in a multiserver service system with the first-come first-served service discipline, such as a telephone call center. A predicted waiting-time distribution or an appropriate summary statistic such as the mean or the 90th percentile may be communicated to the customer upon arrival and possibly thereafter in order to improve customer satisfaction. The predicted waiting-time distribution may also be used by the service provider to better manage the service system, e.g., to help decide when to add additional service agents. The possibility of making reliable predictions is enhanced by exploiting information about system state, including the number of customers in the system ahead of the current customer. Additional information beyond the number of customers in the system may be obtained by classifying customers and the service agents to which they are assigned. For nonexponential service times, the elapsed service times of customers in service can often be used to advantage to compute conditional-remaining-service-time distributions. Approximations are proposed to convert the distributions of remaining service times into the distribution of the desired customer waiting time. The analysis reveals the advantage from exploiting additional information. [ABSTRACT FROM AUTHOR]

Consider a data communication network owned and operated by a single organization. The network has an infinite number of small users and is managed by a system manager (SM) whose objective is to maximize the net value of the system as a whole. The objective of this paper is to study pricing mechanisms that induce the optimal arrival rates when the SM has no full knowledge of the demand in advance. We investigate the system behavior under three alternative dynamic pricing rules and users' expectations models, and characterize the equilibrium and its stability conditions. [ABSTRACT FROM AUTHOR]

Many real-world situations involve queueing systems in which customers wait for service for a limited time only and leave the system if service has not begun within that time. This paper considers a multiserver queueing system with impatient customers, where the customers arrive according to a Poisson process and the service requirements have a general distribution. A simple and insightful solution is presented for the loss probability. The solution is exact for exponential services and is an excellent heuristic for general service times. [ABSTRACT FROM AUTHOR]

This paper investigates the effect upon performance in a service system, such as a telephone call center, of giving waiting customers state information. In particular, the paper studies two M/M/s/r queueing models with balking and reneging. For simplicity, it is assumed that each customer is willing to wait a fixed time before beginning service. However, customers differ, so the delay tolerances for successive customers are random. In particular, it is assumed that the delay tolerance of each customer is zero with probability beta, and is exponentially distributed with mean alpha[sup-1] conditional on the delay tolerance being positive. Let N be the number of customers found by an arrival. In Model 1, no state information is provided, so that if N is greater than or equal to s, the customer balks with probability beta; if the customer enters the system, he reneges after an exponentially distributed time with mean alpha[sup-1] if he has not begun service by that time. In Model 2, if N = s + k is greater than or equal to s, then the customer is told the system state k and the remaining service times of all customers in the system, so that he balks with probability beta + (1 - beta)(1 - q[subk]), where q[subk] = P(T > S[subk]), T is exponentially distributed with mean alpha[sup-1], S[subk] is the sum of k + 1 independent exponential random variables each with mean (s mu)[sup-1], and mu[sup-1] is the mean service time. In Model 2, all reneging is replaced by balking. The number of customers in the system for Model 1 is shown to be larger than that for Model 2 in the likelihood-ratio stochastic ordering. Thus, customers are more likely to be blocked in Model I and are more likely to be served without waiting in Model 2. Algorithms are also developed for computing important performance measures in these, and more general, birth-and-death models. [ABSTRACT FROM AUTHOR]

This paper considers the pricing problem of a service facility when services are jointly produced by the customers and the facility. Building on the work of Mendelson (1985), we model the facility as a GI/GI/1 queue with customer-chosen service rates and linear delay costs. We show that the service rates chosen by the customers, based on their self-interest, are always suboptimal for the facility due to congestion externalities. We derive optimal incentive-compatible pricing schemes that can achieve optimal arrival rates and induce customers to choose optimal service rates. For the case of systemwide net-value maximization, we show that the optimal incentive-compatible pricing scheme consists of a variable fee that is proportional to the actual service time and a fixed rebate that is equal to a customer's expected delay cost in the queue. For the case of profit maximization of the facility, we show that the optimal pricing scheme again consists of a fixed fee and a variable fee. One insight from our analysis is that it may be appropriate for a service facility to reimburse each customer for his actual delay cost in the queue. [ABSTRACT FROM AUTHOR]

In this paper we consider a loss system where the arrivals can be classified into different groups according to their arrival rate and expected service time. While the standard admission policy consists of rejecting only those customers who arrive when all servers are busy, we address the problem of finding the optimal static admission policy (with respect to a given reward structure) when customers can be discriminated according to the group they belong to, thus customers of some groups might be automatically rejected (even if some servers remain idle) in order to enhance the global efficiency of the system. The optimality of a cmu-rule is shown, from which finite-time algorithms for the one- and two-server cases are derived. [ABSTRACT FROM AUTHOR]

A simple and effective way to exploit parallel processors in discrete event simulations is to run multiple independent replications, in parallel, on multiple processors and to average the results at the end of the runs. We call this the method of parallel replications. This paper is concerned with using the method of parallel replications for estimating steady-state performance measures. We report on the results of queueing network simulation experiments that compare the statistical properties of several possible estimators that can be formed using this method. The theoretical asymptotic properties of these estimators were determined in Glynn and Heidelberger (1989a, b). Both the theory and the experimental results reported here strongly indicate that a nonstandard (in the context of steady-state simulation), yet easy to apply, estimation procedure is required on highly parallel machines. This nonstandard estimator is a ratio estimator. The experiments also show that use of the ratio estimator is advantageous even on machines with only a moderate degree of parallelism. [ABSTRACT FROM AUTHOR]

The transactional data of a queueing system are the recorded times of service commencement and service completion for each customer served. With increasing use of computers to aid or even perform service one often has machine readable transactional data, but virtually no information about the queue itself. In this paper we propose a way to deduce the queueing behavior of Poisson arrival queueing systems from only the transactional data and the Poisson assumption. For each congestion period in which queues may form (in front of a single or multiple servers), the key quantities obtained are mean wait in queue, time-dependent mean number in queue, and probability distribution of the number in queue observed by a randomly arriving customer. The methodology builds on arguments of order statistics and usually requires a computer to evaluate a recursive function. The results are exact for a homogeneous Poisson arrival process (with unknown parameter) and approximately correct for a slowly time varying Poisson process. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the Partial Conditional Expectation (PCE) variance reduction technique, derived by modifying the well-known Conditional Expectation (CE) technique to make it more widely applicable. We apply this PCE technique to obtain a consistent estimator for the expected waiting time in queue in a single-server queueing system. We then derive an improved version of this estimator. taking into consideration further properties of the system. Empirical results show that these two estimators always perform better than the classical estimator. When the traffic intensity is low, the variance reductions obtained by these two estimators become very significant. [ABSTRACT FROM AUTHOR]

This paper presents an alternative procedure for computing the steady state probability vector of an M/M/1 queue with randomly varying arrival and service rates. By exploiting the structure of the infinitesimal generator of the underlying continuous-time Markov chain, the approach represents an efficient adaptation of the state reduction method introduced by Grassmann for solving problems involving M/M/1 queues under a random environment. We compare computational requirements of the proposed approach with the method of Neuts and block elimination under different rush-hour congestion patterns while keeping the overall traffic intensity constant as well as under different traffic intensities. We demonstrate that the proposed method requires minimal computing time to reach convergence and moreover the time requirement does not change much when traffic intensity increases. [ABSTRACT FROM AUTHOR]

Queueing networks have been used to model the performance or a variety of complex systems. Since exact results exist for only a limited class of networks, the decomposition methodology has been used extensively to obtain approximate results. In this paper, we consider open queueing networks with multiple product classes, deterministic routings and general arrival and service distributions. We examine the decomposition method for such systems and show that it provides estimates of key parameters with an accuracy that is not acceptable in many practical settings, Recognizing this weakness, we enrich the approach by modeling a phenomenon previously ignored. We consider interference among products and describe its effect on the variance of the departure streams. The recognition of this effect significantly improves the performance of this methodology. We provide extensive experimental results based on the data of a manufacturer of semiconductor devices. [ABSTRACT FROM AUTHOR]