OPTIMAL RENEGING DECISIONS IN A G/M/1 QUEUE

This paper is an analysis of the optimal reneging decision of a customer who joins a G/M/1 queue, having imperfect information about the queue. It is assumed that a customer receives a constant, known reward upon completion of service and incurs a cost proportional to the time spent in the queueing system. It is also assumed that a customer revises his estimated remaining waiting time in the system based on his initial estimate and observations of service time. Thus, a customer will renege when his estimated cost of remaining in the system exceeds his reward. The probability of a customer reneging during any given service is determined. Finally, it is shown how this probability varies with the parameters of the customer.     

APPROXIMATE QUEUEING NETWORK MODELS FOR CLOSED FABRICATION/ASSEMBLY SYSTEMS. PART I: SINGLE LEVEL SYSTEMS

We address the issue of performance analysis of fabrication/assembly (F/A) systems, which are systems that first fabricate components and then join the components and subassemblies into a product. Here we consider an F/A system consisting of a single assembly station with input from K fabrication stations. We assume that the system uses a Kanban control mechanism with a fixed number of kanbans circulating between each input station and the assembly station. Even with Markovian assumptions, computing an exact solution for the performance evaluation of such systems becomes intractable due to an explosion in the state-space. We develop computationally efficient algorithms to approximate the throughput and mean queue lengths. The accuracy of the approximations is studied by comparison to exact results (K = 2) and to simulations (K > 2). Part II of this paper demonstrates how these models can be used as building blocks to evaluate more complex F/A systems with multiple levels of assembly stations.     

基于顾客公平偏好的服务机制与定价研究

由于顾客异质性（单位时间等待成本不同），服务提供商通常对顾客采取分类服务策略，然而分类服务会引起服务系统中不同类型顾客之间等待时间和服务价值的差异性，从而给顾客带来心理上的不公平感，进而引起顾客在服务系统中的流动和转移，进一步影响企业收益和社会福利。本文针对非抢占M/M/1服务系统顾客分类情形为背景，由两种顾客之间期望等待时间的不同和公平偏好参数相结合构建普通顾客的公平心理效用模型，以垄断型服务系统为背景，分别从企业收益、社会福利与顾客效用三个视角进行分析。研究表明，服务提供商应对顾客采取可观测型的分类服务机制来获得最大收益；从社会福利视角，服务提供商应对顾客采取不可观测型的分类服务机制；从顾客效用视角，服务提供商应取消顾客分类服务，仅保留普通顾客。最后同现有结论进行比较分析，并进行拓展研究。本文研究对服务提供商采取合理的服务机制及相应的服务定价具有重要参考价值和指导意义。     

SHIFTING PRODUCTION BOTTLENECKS: CAUSES,CURES, AND CONUNDRUMS

We examine the phenomenon of shifting production bottlenecks from an analytic perspective. We quantify the propensity of a work center to be a bottleneck, defined as maximal queue length, using a simple Jackson production network model. Comparison of the analytic model against an empirical simulation-based model shows that the two are in good agreement. A scalar measure of bottleneck shiftiness is proposed and used to investigate several policies for mitigating shiftiness. Simulation experiments show that several commonly observed managerial policies for coping with shifting bottlenecks actually increase shiftiness, but that shiftiness declines when the capacity of nonbottleneck resources is increased.     

STATE-OF-THE-ART SURVEY: OPEN QUEUEING NETWORKS: OPTIMIZATION AND PERFORMANCE EVALUATION MODELS FOR DISCRETE MANUFACTURING SYSTEMS

In this survey we review methods to analyze open queueing network models for discrete manufacturing systems. We focus on design and planning models for job shops. The survey is divided in two parts: in the first we review exact and approximate decomposition methods for performance evaluation models for single and multiple product class networks. The second part reviews optimization models of three categories of problems: the first minimizes capital investment subject to attaining a performance measure (WIP or lead time), the second seeks to optimize the performance measure subject to resource constraints, and the third explores recent research developments in complexity reduction through shop redesign and products partitioning.     

Coping with Time‐Varying Demand When Setting Staffing Requirements for a Service System

We review queueing‐theory methods for setting staffing requirements in service systems where customer demand varies in a predictable pattern over the day. Analyzing these systems is not straightforward, because standard queueing theory focuses on the long‐run steady‐state behavior of stationary models. We show how to adapt stationary queueing models for use in nonstationary environments so that time‐dependent performance is captured and staffing requirements can be set. Relatively little modification of straightforward stationary analysis applies in systems where service times are short and the targeted quality of service is high. When service times are moderate and the targeted quality of service is still high, time‐lag refinements can improve traditional stationary independent period‐by‐period and peak‐hour approximations. Time‐varying infinite‐server models help develop refinements, because closed‐form expressions exist for their time‐dependent behavior. More difficult cases with very long service times and other complicated features, such as end‐of‐day effects, can often be treated by a modified‐offered‐load approximation, which is based on an associated infinite‐server model. Numerical algorithms and deterministic fluid models are useful when the system is overloaded for an extensive period of time. Our discussion focuses on telephone call centers, but applications to police patrol, banking, and hospital emergency rooms are also mentioned.     

Warteschlangen-Modelle in der Produktionsplanung – Möglichkeiten und Grenzen

Production Management often tried to apply queueing models to describe the flow of products and parts. These approaches usually apply very simple queueing models. Due to mathematical problems implied by general waiting line models, an adaptation to real life problems fails often. In this paper, some simple models discussed in production management are presented and it is shown why they failed to be generalized. Afterwards, we try to find a way how to model the simple case of flow shop production using generalized queueing models: First decomposition of serial waiting lines and approximation of the system by a sequence of independent stations. Afterwards the approach of recent literature to consider again the entire system simultaneously is sketched, and it is argued that these approaches are restricted as well to small problems     

Performance models for unreliable flexible manufacturing systems

This paper deals with the analysis and application of queueing models for single and multi stage flexible manufacturing systems that are subject to resource failure. Exact results are derived for the single stage queueing system. Two approximations are presneted for the multi stage queueing system as a closed network. We validate the approximations by comparing their performance estimates against the exact global balance solution.     

AN EFFICIENT METHOD FOR DETERMINING THE WAITING TIME DISTRIBUTION OF QUEUES

This paper presents a practical method for determining the waiting time distribution of a single-stage queueing system for general distribution of inter-arrival/service times. The method requires the matrix solution of Lindley's equation for waiting time distribution by treating time in discrete units. Some important characteristics of the method are: a) it is easily programmable; b) it has high accuracy; c) it has modest CPU time and storage requirements; and, d) it requires no mathematical functional form for inter-arrival/service time distributions.     

Modeling and Managing the Percentage of Satisfied Customers in Hidden and Revealed Waiting Line Systems

We perform an analysis of various queueing systems with an emphasis on estimating a single performance metric. This metric is defined to be the percentage of customers whose actual waiting time was less than their individual waiting time threshold. We label this metric the Percentage of Satisfied Customers (PSC.) This threshold is a reflection of the customers' expectation of a reasonable waiting time in the system given its current state. Cases in which no system state information is available to the customer are referred to as “hidden queues.” For such systems, the waiting time threshold is independent of the length of the waiting line, and it is randomly drawn from a distribution of threshold values for the customer population. The literature generally assumes that such thresholds are exponentially distributed. For these cases, we derive closed form expressions for our performance metric for a variety of possible service time distributions. We also relax this assumption for cases where service times are exponential and derive closed form results for a large class of threshold distributions. We analyze such queues for both single and multi‐server systems. We refer to cases in which customers may observe the length of the line as “revealed” queues.“ We perform a parallel analysis for both single and multi‐server revealed queues. The chief distinction is that for these cases, customers may develop threshold values that are dependent upon the number of customers in the system upon their arrival. The new perspective this paper brings to the modeling of the performance of waiting line systems allows us to rethink and suggest ways to enhance the effectiveness of various managerial options for improving the service quality and customer satisfaction of waiting line systems. We conclude with many useful insights on ways to improve customer satisfaction in waiting line situations that follow directly from our analysis.     

Hierarchical Multi‐skill Resource Assignment in the Telecommunications Industry

We formulate a discrete time Markov decision process for a resource assignment problem for multi‐skilled resources with a hierarchical skill structure to minimize the average penalty and waiting costs for jobs with different waiting costs and uncertain service times. In contrast to most queueing models, our application leads to service times that are known before the job is actually served but only after it is accepted and assigned to a server. We formulate the corresponding Markov decision process, which is intractable for problems of realistic size due to the curse of dimensionality. Using an affine approximation of the bias function, we develop a simple linear program that yields a lower bound for the minimum average costs. We suggest how the solution of the linear program can be used in a simple heuristic and illustrate its performance in numerical examples and a case study.     

Quadratic Assignment Problems and M/G/C/C/ State Dependent Network Flows

One of the most notorious network design problems is the Quadratic Assignment Problem (QAP). We develop an heuristic algorithm for QAPs along with an M/G/C/C state dependent queueing model for capturing congestion in the traffic system interconnecting the nodes in the network. Computational results are also presented.     

基于“云排队”的经济效益分析

随着各种云智能排队预约系统的推出，顾客“排队难”的问题得到了极大的缓解。其简便的操作方式，受到了大量商家与顾客的好评。本文基于当下热门服务行业的运营模式，建立排队博弈模型，从理论上分析了“云排队”平台对顾客以及服务商的影响。本文主要得到了以下几个结果：(1) 给出了两类顾客的纳什均衡策略(包括进队策略与最优到达间隔)；(2) 发现当前的预约机制能够提高“线上”顾客的效用，并刺激更多的线上顾客购买该产品，但同时也降低了“线下”顾客的进队意愿；(3) 发现在云排队机制下服务商的收益将大大提高，同时该机制将刺激服务商收取更高的服务费用。     

PERFORMANCE ANALYSIS OF AN ASSEMBLY STATION WITH INPUT FROM MULTIPLE FABRICATION LINES

We develop analytical models for performance evaluation of Fabrication/Assembly (F/A) systems. We consider an F/A system that consists of an assembly station with input from K fabrication lines. Each fabrication line consists of one or more fabrication stations. The system is closed with a fixed number of items circulating between each fabrication line and the assembly station. We present algorithms to estimate the throughput and mean queue lengths of such systems with exponential processing times. We then extend our approach to analyze F/A systems with general processing time distributions. Numerical comparisons with simulations demonstrate the accuracy of our approach.     

DECOMPOSITION ALGORITHM FOR PERFORMANCE EVALUATION OF AGV SYSTEMS

This paper proposes a realistic queueing model of automated guided vehicle (agv) systems in just-in-time production systems. The model takes into consideration return paths, Erlang distributed service times, and pull-type dispatching rule, assuming finite buffer capacities. Since it has no product-form solution and natural decomposability due to complex nontree fork-cum-join architecture and dynamic dispatching rules, we propose a machine-based decomposition algorithm for the performance evaluation of the model. Each decomposed module consists of the processing machine and its dispatching station. Three flow probabilities, derived from flow conservation analysis, relate the modules, which are updated iteratively until the parameters converge. The numerical results from a real-life Agv system application show that the algorithm is reasonably accurate.     

AN OVERVIEW OF TRADEOFF CURVES IN MANUFACTURING SYSTEMS DESIGN

In this paper we review the use of tradeoff curves in the design of manufacturing systems that can be modeled as open queueing networks. We focus particularly on the tradeoff between expected work-in-process (or product leadtime) and capacity investment in job shops. We review the algorithms in the literature to derive tradeoff curves and illustrate their application in evaluating the efficiency of the system, in deciding how much capacity to have, how to allocate resources between the reduction of uncertainty and the introduction of new technologies, and how to assess the impact of changes in products throughput and product mix. The methodology is illustrated with an example derived from an actual application in the semiconductor industry.     

Social Optimal Location of Facilities with Fixed Servers,Stochastic Demand,and Congestion

We consider two capacity choice scenarios for the optimal location of facilities with fixed servers, stochastic demand, and congestion. Motivating applications include virtual call centers, consisting of geographically dispersed centers, walk‐in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems. The choice of locations for such facilities influences both the travel cost and waiting times of users. In contrast to most previous research, we explicitly embed both customer travel/connection and delay costs in the objective function and solve the location–allocation problem and choose facility capacities simultaneously. The choice of capacity for a facility that is viewed as a queueing system with Poisson arrivals and exponential service times could mean choosing a service rate for the servers (Scenario 1) or choosing the number of servers (Scenario 2). We express the optimal service rate in closed form in Scenario 1 and the (asymptotically) optimal number of servers in closed form in Scenario 2. This allows us to eliminate both the number of servers and the service rates from the optimization problems, leading to tractable mixed‐integer nonlinear programs. Our computational results show that both problems can be solved efficiently using a Lagrangian relaxation optimization procedure.     

Modelling the use of the manager's time

This paper starts from two problems: the lack of use of queueing theory (and OR models in general) and the need for greater personal time effectiveness expressed by managers. The application of waiting line theory to the general managerial role is proposed and the most salient assumptions in such an application are explored. A simple example is undertaken which results in tentatively promising evidence. Further questions and possibilities are raised.     

Service Systems with Experience‐Based Anecdotal Reasoning Customers

The existing queueing literature typically assumes that customers either perfectly know the expected waiting time or are able to form rational expectations about it. In contrast, in this article, we study canonical service models where customers do not have such full information or capability. We assume that customers lack full capability or ample opportunities to perfectly infer the service rate or estimate the expected waiting time, and thus can only rely on past experiences and anecdotal reasoning to make their joining decisions. We fully characterize the steady‐state equilibrium in this service system. Compared with the fully rational benchmark, we find that customers with anecdotal reasoning are less price‐sensitive. Consequently, with a higher market potential (higher arrival rate), a revenue‐maximizing firm may increase the price if the service rate is exogenous, and it may decrease the price if the service rate is at the firm's discretion. Both results go against the commonly accepted pricing recommendations in the fully rational benchmark. We also show that revenue maximization and welfare maximization lead to fundamentally different pricing strategies with anecdotal reasoning, whereas they are equivalent in the fully rational benchmark.