Queues with stochastic service rates

The purpose of this paper is to explore an extension of the output discipline for the Poisson input, general output, single channel, first-come, first-served queueing system. The service time parameter, μ, is instead considered a random variable, M. In other words, the service time random variable, T, is to be conditioned by a parameter random variable, M. Therefore, if the distribution function of M is denoted by F_M(μ) and the known conditional service time distribution as B(t |_μ), then the unconditional service distribution is given by B(t) = Pr {T ≤ t}. = ∫_-∞^∞ B(t |_μ) dF_M(μ). Results are obtained that characterize queue size and waiting time using the imbedded Markov chain approach. Expressions are derived for the expected queue length and Laplace-Stieltjes transforms of the steady-state waiting time when conditional service times are exponential. More specific results are found for three special distributions of M: (1) uniform on [1.2]; (2) two-point; and (3) gamma.     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

Scheduling customer arrivals to a stochastic service system

An efficient algorithm for determining the optimal arrival schedule for customers in a stochastic service system is developed. All customers arrive exactly when scheduled, and service times are modeled as iid Erlang random variables. Costs are incurred at a fixed rate per unit of time each customer waits for service, and an additional cost is incurred for every unit of time the server operates beyond a scheduled closing time. The objective is to minimize total operating cost. This type of problem arises in many operational contexts including transportation, manufacturing, and appointment‐based services. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 549–559, 1999     

Performance of N machine centers of K-out-of-M: G type maintained by a single repairman

We consider a system of N (nonsymmetric) machine centers of the K-out-of-M : G type that are maintained by a single repairman. [A machine center functions if and only if at least K of the M machines belonging to the center are good (G).] Such systems are commonly found in various manufacturing and service industries. A stochastic model is developed that accommodates generally distributed repair times and repairman walk times, and most repair scheduling disciplines. K-out-of-M : G type systems also appear as a modeling paradigm in reliability analysis and polling systems performance analysis. Several performance measures are derived for machine-repair systems having K-out-of-M-type centers. A simple example system is developed in detail that exposes the computations involved in modeling applications. © 1992 John Wiley & Sons, Inc.     

A queueing system with multiple service time distributions

This paper explores a modification of the output discipline for the Poisson input, exponential output, single channel, first-come, first-served queueing system. Instead, the service time distribution of customers beginning service when alone in the system is considered different from that governing service times of all other customers. More specifically, the service times of lone customers are governed by a one parameter gamma distribution, while the service times of all other customers are exponentially ajstributed. The generating function for the steady-state probsbilities, n_j = Pr { j customers in system at an arbitrary point of departure}, of the imbedded chain, {X_n/X_n = number in system after nth customer is serviced}, is obtained, and the steady-state probabilities, themselves, are found in closed form.     

A model for use in the rationing of inventory during lead time

While the traditional solution to the problem of meeting stochastically variable demands for inventory during procurement lead time is through the use of some level of safety stock, several authors have suggested that a decision be made to employ some form of rationing so as to protect certain classes of demands against stockout by restricting issues to other classes. Nahmias and Demmy [10] derived an approximate continuous review model of systems with two demand classes which would permit an inventory manager to calculate the expected fill rates per order cycle for high-priority, low-priority, and total system demands for a variety of parameters. The manager would then choose the rationing policy that most closely approximated his fill-rate objectives. This article describes a periodic review model that permits the manager to establish a discrete time rationing policy during lead time by prescribing a desired service level for high-priority demands. The reserve levels necessary to meet this level of service can then be calculated based upon the assumed probability distributions of high- and low-priority demands over lead time. The derived reserve levels vary with the amount of lead time remaining. Simulation tests of the model indicate they are more effective than the single reserve level policy studied by Nahmias and Demmy.     

Optimal investment,pricing and replacement of computer resources

The problem of multiple-resource capacity planning under an infinite time horizon is analyzed using a nonlinear programming model. The analysis generalizes to the long term the short-run pricing model for computer networks developed in Kriebel and Mikhail [5]. The environment assumes heterogeneous resource capacities by age (vingate), which service a heterogeneous and relatively captive market of users with known demand functions in each time period. Total variable operating costs are given by a continuous psuedoconcave function of system load, capacity, and resource age. Optimal investment, pricing, and replacement decision rules are derived in the presence of economies of scale and exogenous technological progress. Myopic properties of the decision rules which define natural (finite) planning subhorizons are discussed.     

Estimation of a hidden service distribution of an M/G/∞ system

The maximum likelihood estimator of the service distribution function of an M/G/∞ service system is obtained based on output time observations. This estimator is useful when observation of the service time of each customer could introduce bias or may be impossible. The maximum likelihood estimator is compared to the estimator proposed by Mark Brown, [2]. Relative to each other, Brown's estimator is useful in light traffic while the maximum likelihood estimator is applicble in heavy trafic. Both estimators are compared to the empirical distribution function based on a sample of service times and are found to have drawbacks although each estimator may have applications in special circumstances.     

Appointment scheduling at a multidisciplinary outpatient clinic using stochastic programming

The purpose of this paper is to investigate the problem of constructing an appointment template for scheduling patients at a specific type of multidisciplinary outpatient clinic called an integrated practice unit (IPU). The focus is on developing and solving a stochastic optimization model for a back pain IPU in the face of random arrivals, an uncertain patient mix, and variable service times. The deterministic version of the problem is modeled as a mixed integer program with the objective of minimizing a weighted combination of clinic closing time (duration) and total patient waiting time (length of stay). A two‐stage stochastic program is then derived to account for the randomness and the sequential nature of the decisions. Although it was not possible to solve the two‐stage problem for even a limited number of scenarios, the wait‐and‐see (WS) problem was sufficiently tractable to provide a lower bound on the stochastic solution. The introduction of valid inequalities, limiting indices, and the use of special ordered sets helped to speed up the computations. A greedy heuristic was also developed to obtain solutions much more quickly. Out of practical considerations, it was necessary to develop appointment templates with time slots at fixed intervals, which are not available from the WS solution. The first to be derived was the expected value (EV) template that is used to find the expected value of the EV solution (EEV). This solution provides an upper bound on the objective function value of the two‐stage stochastic program. The average gap between the EEV and WS solutions was 18%. Results from extensive computational testing are presented for the EV template and for our adaptation of three other templates found in the literature. Depending on the relative importance of the two objective function metrics, the results demonstrate the trade‐off that exists between them. For the templates investigated, the “closing time” ranged from an average of 235 to 275 minutes for a 300‐minute session, while the corresponding “total patient time in clinic” ranged from 80 to 71 minutes.     

A note on a computational model for a data/voice communication queueing system

Certain types of communication nodes can be viewed as multichannel queueing systems with two types of arrival streams. Data arrivals are characterized by high arrival and service rates and have the ability to queue if all service channels are busy. Voice arrivals have small arrival and service rates and do not have the ability to wait when the channels are full. Computational procedures are presented for obtaining the invariant probabilities associated with the queueing model.     

光互连网络中资源预留的多级光互连仲裁机制

基于资源预留策略提出一种多级光互连仲裁机制,通过将网络分级实现快速、高效的仲裁。多优先级数据缓存队列的传输节点设计,提供了不同类型流量的差异化传输;通过预约式两级仲裁机制,实现网络的完全公平与100%的高吞吐率。设计并对快速仲裁通道进行了合理布局,极大地缩短了仲裁延迟。仿真结果表明:采用基于资源预留的分级仲裁策略,在多种流量模式下所有节点均获得公平的服务。与Feather Weight相比,分级仲裁策略吞吐率提高17%;与2-pass相比,仲裁延迟减少15%,同时,功耗减少5%。     

Stochastic call center staffing with uncertain arrival,service and abandonment rates: A Bayesian perspective

In this article, we introduce staffing strategies for the Erlang‐A queuing system in call center operations with uncertain arrival, service, and abandonment rates. In doing so, we model the system rates using gamma distributions that create randomness in operating characteristics used in the optimization formulation. We divide the day into discrete time intervals where a simulation based stochastic programming method is used to determine staffing levels. More specifically, we develop a model to select the optimal number of agents required for a given time interval by minimizing an expected cost function, which consists of agent and abandonment (opportunity) costs, while considering the service quality requirements such as the delay probability. The objective function as well as the constraints in our formulation are random variables. The novelty of our approach is to introduce a solution method for the staffing of an operation where all three system rates (arrival, service, and abandonment) are random variables. We illustrate the use of the proposed model using both real and simulated call center data. In addition, we provide solution comparisons across different formulations, consider a dynamic extension, and discuss sensitivity implications of changing constraint upper bounds as well as prior hyper‐parameters. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 460–478, 2016     

Probabilistic a priori routing-location problems

In many routing-location models customers located at nodes of a network generate calls for service with known probabilities. The customers that request service in a particular day are served by a single server that performs a service tour visiting these customers. The order of providing service to customers for each potential list of calls is uniquely defined by some a priori fixed basic sequence of all the customers (a priori tour). The problems addressed in this article are to find an optimal home location or an optimal basic sequence for the server so as to minimize the expectation of a criterion. The following criteria are considered: the total waiting time of all the customers, the total length of the tour, the maximal waiting time of a customer, the average traveled length per customer, and the average waiting time per customer. We present polynomial-time algorithms for the location problems. For the routing problems we present lower bounds that can be calculated efficiently (in polynomial time) and used in a branch-and-bound scheme. © 1994 John Wiley & Sons, Inc.     

Single server queues with hyperexponential service times

Single server queues with hyperexponential service times are studied. Explicit expressions are derived for the waiting time and state distributions.     

基于DRFM的匀加速距离门拖引干扰信号的频谱分析

研究了基于DRFM的匀加速距离门拖引干扰信号的频谱。由于DRFM的离散化采样,导致干扰信号频谱有两个明显特征。首先,频谱相对于中心频率会出现微小可测的频移;其次,频谱由菲涅尔谱及其周期性的谐波组成,且在特定情况下会出现频谱的交叠。首先推导了匀加速距离门拖引的时域表达式并分析其频谱,并从理论上得出频移、谐波中心的位置以及频谱交叠的条件。最后通过对时域信号的fft仿真,验证所作理论推导的正确性。     

Probabilistic priorities in the M/G/1 queue

A simple method is presented for deriving the mean and variance of the queueing time distribution in an M/G/1 queue when the priorities assigned to customers have an assignment probability distribution. Several examples illustrate the results. The mean and variance of the queueing time distribution for the longest service time discipline are derived, and its disadvantages are discussed.     

Two novel critical shock models based on Markov renewal processes

In this paper, we investigate systems subject to random shocks that are classified into critical and noncritical categories, and develop two novel critical shock models. Classical extreme shock models and run shock models are special cases of our developed models. The system fails when the total number of critical shocks reaches a predetermined threshold, or when the system stays in an environment that induces critical shocks for a preset threshold time, corresponding to failure mechanisms of the developed two critical shock models respectively. Markov renewal processes are employed to capture the magnitude and interarrival time dependency of environment-induced shocks. Explicit formulas for systems under the two critical shock models are derived, including the reliability function, the mean time to failure and so on. Furthermore, the two critical shock models are extended to the random threshold case and the integrated case where formulas of the reliability indexes of the systems are provided. Finally, a case study of a lithium-ion battery system is conducted to illustrate the proposed models and the obtained results.     

On a single-server queue with state-dependent service

This paper discusses a class of queueing models in which the service time of a customer al a single server facility is dependent on the queue size at the onset of its service. The Laplace transform for the wait in queue distribution is derived and the utilization of the server is given when the arrival is a homogeneous Poisson process.     

Workload distribution of discrete‐time parallel queues with two servers

We study discrete‐time, parallel queues with two identical servers. Customers arrive randomly at the system and join the queue with the shortest workload that is defined as the total service time required for the server to complete all the customers in the queue. The arrivals are assumed to follow a geometric distribution and the service times are assumed to have a general distribution. It is a no‐jockeying queue. The two‐dimensional state space is truncated into a banded array. The resulting modified queue is studied using the method of probability generating function (pgf) The workload distribution in steady state is obtained in form of pgf. A special case where the service time is a deterministic constant is further investigated. Numerical examples are illustrated. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 440–454, 2000     

Production planning for multi-resource network systems

Production planning for large-scale production systems requiring the allocation of numerous resources is considered. It is demonstrated how the dynamic activity analysis developed by Shephard leads to linear programming solutions of production planning problems. Three types of planning problems are formulated: maximization of output levels for a given time horizon; minimization of production duration for given output histories; and minimization of production costs for given output histories.