Introduction to Queueing Systems

INTRODUCTION TO QUEUEING SYSTEMS BASIC STRUCTURE OF QUEUEING MODELS Input Service Customers Queue Mechanis Served Customers Source m...

INTRODUCTION TO QUEUEING SYSTEMS BASIC STRUCTURE OF QUEUEING MODELS Input Service Customers Queue Mechanis Served Customers Source m Queueing System  Input source: the calling population. May be infinite or finite.  Interarrival time (IAT): time between consecutive arrivals. When arrivals are “random” but with a certain average rate, we assume customers are generated according to a Poisson process with mean λ=  Queue: the maximum permissible number of customers. May be infinite or finite.  Traffic light, bank teller, airport security screening, emergency room, toll booth, parking lot, call center QUEUEING 2 BASIC STRUCTURE OF QUEUEING MODELS Input Service Customers Queue Mechanis Served Customers Source m Queueing System  How does the size of the queue (infinite or finite) affect the performance of the queueing system? balking , reneging  How does the service discipline (FIFO, LIFO, priority, random) affect the performance of the queueing system? QUEUEING 3 BASIC STRUCTURE OF QUEUEING MODELS Service Input Customers Queue Mechanis Served Customers Source m Queueing System  Service Discipline: order in which members of the queue are selected for service. FIFO, LIFO, priority, random.  Service mechanism: one or more service facilities, each with one or more parallel service channels (servers)  Service time: must specify the distribution of service (holding) times and all parameters, eg.., constant, exponential,... QUEUEING 4 BASIC STRUCTURE OF QUEUEING MODELS Service Input Customers Queue Mechanis Served Customers Source m Queueing System  What are the implications of assuming a Poisson arrival process for the input source? The Poisson arrival process assumption implies that the interarrival times between customers are independent and exponentially distributed, which simplifies the analysis of the queueing system.  How does the number of servers in the service mechanism affect the performance of the queueing system? Increasing the number of servers can reduce the waiting time and queue length, but it also comes with additional costs. The optimal number of servers depends on the trade-off between performance and cost. QUEUEING 5   Commercial Service systems – barber SOME shop, bank teller service, checkout at supermarket, gas station  Transportation service systems – toll EXAMPLES booth, traffic light, truck or ship loading / unloading, parking lot (no queue, the spaces are servers), taxis, OF REAL elevators  Business – industrial service systems - maintenance (repair crews) QUEUEING systems, inspection stations, secretarial / clerical pools  Social service systems: judicial SYSTEMS system, legislative systems (bills waiting for processing), health-care systems QUEUEING 6 SOME TERMINOLOGY  State of the System ≡ the number of customers in the queueing system  Queue Length ≡ the number of customers waiting for service = the State of the System minus the number of customers being s ≡ served number of servers  ≡ expected interarrival time  λ ≡ mean arrival rate  ≡ expected service time  µ ≡ mean service rate  ρ = ≡ utilization factor, expected fraction of time the servers are busy QUEUEING 7 SOME EXAMPLES  In a bank teller service, the state of the system would be the number of customers in the bank, including those being served and those waiting in line.  In a parking lot queueing system, the state of the system would be the number of cars in the parking lot, and the queue length would be the number of cars waiting for a parking space to become available. QUEUEING 8 STEADY-STATE CONDITION  After sufficient time has elapsed, state of the system is independent of its initial state and elapsed time.  Usually we say that the system has reached a state of dynamic equilibrium (rate in = rate out).  For this to occur, we require that ρ < 1.  What is the significance of the utilization factor (ρ) in a queueing system, and what are the implications The when utilization ρ≥ factor ρ 1? represents the expected fraction of time the servers are busy. When ρ ≥ 1, it means the arrival rate is greater than or equal to the service rate, which can lead to the system becoming unstable and the queue length growing without bound. QUEUEING 9 STEADY-STATE CONDITION  What are the implications of the steady-state condition not being met in a queueing system? If the steady-state condition is not met, the system may not reach a stable, predictable state, and the performance measures may be heavily influenced by the initial conditions or time-dependent factors.  How might the steady-state condition be affected by changes in the input source or the service mechanism over time? Changes in the arrival rate, service rate, or number of servers can affect the steady-state condition and the overall performance of the queueing system. The system may need to adapt to these changes to maintain a stable, dynamic equilibrium.  A fast-food restaurant may experience significant variations in customer arrivals throughout the day, with peak periods during lunch and dinner hours. Maintaining the steady-state condition in such a system can be challenging.  A hospital emergency room may experience sudden influxes of patients due to unexpected events, disrupting the steady-state condition and requiring the system to adapt quickly to maintain acceptable performance. QUEUEING 10 MEASURES OF PERFORMANCE AT STEADY-STATE  L = expected # customers in the queueing system  Lq = expected # customers in queue  W = expected waiting time in system (including service time)  Wq = expected waiting time in queue  In a bank teller service, the expected waiting time in the queue (Wq) would be an important performance measure to monitor, as it directly affects customer satisfaction.  In a hospital emergency room, the expected number of patients in the queue (Lq) would be a crucial measure, as it indicates the potential for long wait times and the need to adjust staffing or other resources. QUEUEING 11 CLASSIFYING QUEUEING SYSTEMS  # phases: how many work stations might a customer visit? (service facility)  # channels: How many servers at a work station?  Queue discipline: rules which determine which customer in waiting line is next to be served.  FIFO, LIFO, random, priority rule  preemptive priority - can interrupt service of lower priority entity  Other considerations (analytic vs simulation):  balking  reneging  jockeying QUEUEING 12 THE P/M/M/S/Q QUEUE  Queueing models may be denoted by p/M/M/s/q as follows: A bank teller service could be modeled as an M/M/s/q queue, where customers arrive according to a Poisson process, are served with exponential service times, and there is a finite number of tellers and a finite queue capacity. A call center with multiple customer service representatives could be represented as an M/M/s/q queue, where the incoming calls follow a Poisson arrival process, the service times are QUEUEING exponentially distributed, and there is a limited 13 number of representatives and a finite queue capacity. THE BASIC QUEUEING MODEL M/M/1 This is a single-phase, single-server, FIFO queueing system. Servi ce C S Facilit C C C  Infinite source (p = ∞) C y ustome  Poisson arrivals C rs  Exponential service times  One server (s=1) Queueing System  Infinite queue space (q = ∞) (q=∞) Served QUEUEING Customers STEADY-STATE MEASURES OF PERFORMANCE FOR THE M/M/1 QUEUE M/M/1 queueing model, which is a single-phase, single-server, FIFO queueing system with Poisson arrivals, exponential service times, and L = = an infinite queue capacity. Lq = What are the key assumptions and limitations Wq = of the M/M/1 queueing model, and how might W = they affect its applicability to real-world situations? The key assumptions are that the arrivals follow a Poisson process, the service times are exponentially distributed, and there is a single server. These assumptions may not always hold QUEUEING true in real-world systems, which could limit the15 model's accuracy and applicability. THE M/M/S QUEUE This is a single-phase, multiple-server, FIFO queueing system. C S Servi ce C S Facilit C C C C S  Infinite source (p = ∞) C y ustome  Poisson arrivals C rs  Exponential service times  # servers > 1 Queueing System  Infinite queue space (q = ∞) (q=∞) Served QUEUEING Customers STEADY-STATE MEASURES OF PERFORMANCE FOR THE M/M/S QUEUE  Wq =  Pn ≡ probability that there are n customers  L = Lq + ρ in the system  P0 ≡ probability that there are no  W = Wq + customers in the system = To compute Pn: P0 =  if n ≤ s, Pn =  Lq =  if n > s, Pn = QUEUEING 17 RELATIONSHIPS AMONG MEASURES OF PERFORMANCE  L=λW  L q = λ Wq  W = Wq + QUEUEING 18 CONCLUSION  Queueing models are often subjected to simulation for various reasons (discussed in other lectures). We will be using the elements discussed here repeatedly throughout our simulation course. QUEUEING 19