Queuing Theory PDF

# Introduction to Queuing Theory ## Queueing Systems - A queueing system consists of customers arriving for some type of service, waiting in line if necessary, and eventually receiving service from one or more service providers. - Customers leave the system after receiving their service. - A **q...

# Introduction to Queuing Theory ## Queueing Systems - A queueing system consists of customers arriving for some type of service, waiting in line if necessary, and eventually receiving service from one or more service providers. - Customers leave the system after receiving their service. - A **queue** is a line of waiting customers who require service from one or more service providers. - A **queueing system** is composed of three components: a waiting room, customers and service providers. ## Queueing Models - Queueing models are mathematical models that are used to analyze and design queueing systems. - These models help to estimate desired performance measures of the system. - **Types of measures**: - server utilization - length of waiting lines - delays of customers - **Applications of queueing models** - Determine the minimum number of servers needed at a service center. - Detection of performance bottleneck or congestion. - Evaluate alternative system designs. - Determine the average waiting time, how many customers are waiting on average, how long the average service time is, and the chance that one of the services has nothing to do. ## Queueing Notation - **Arrival process**: Customer arrival patterns, how many customers arrive and when. - **Service Time distribution**: The time to service one customer. - **Number of servers**: The number of resources available to serve customers. - **Server Capacity**: The maximum number of customers that can be in the queue at any one time. - **Customer Population**: The number of customers that could potentially need service. - **Service Discipline**: The order in which customers are served (e.g., first-come, first-served). ## Parameters of a Queueing System - The behavior of a queueing system is dependent on the following parameters: - **Arrival process**: The distribution of interarrival times. - **Service process**: The distribution of service times (and number of servers). - **Number of Servers**: How many servers are available. - **Capacity of the System**: The number of customers who can wait in line. - **Size of the population**: The number of customers that can potentially need service. ## Kendall Notation - Kendall notation represents the different aspects of a queuing system. It is a standard shorthand notation: - A/S/m/B/K/SD. - **A**: arrival process. - **S**: service time distribution. - **m**: number of servers. - **B**: number of buffers (system capacity). - **K**: population size. - **SD**: service discipline. ## Number of Servers - The number of servers available in a queueing system significantly impacts the performance and waiting times. - **Single Server Queue**: One server is available to serve customers. - **Multiple Server Queue**: More than one server is available to serve customers simultaneously. ## Service Disciplines - **Service discipline** defines how the customers are chosen to be served. Some of the common service disciplines are: - **First-come-first-served (FCFS)**: Customers are served in the order they arrive. - **Last-come-first-served (LCFS)**: Customers are served in the reverse order of their arrival. - **Shortest processing time first (SPT)**: Customers with the shortest service time are served first. - **Shortest remaining processing time first (SRPT)**: Customers with the shortest remaining service time are served first. - **Shortest expected processing time first (SEPT)**: Customers with the shortest expected service time are served first. - **Shortest expected remaining processing time first (SERPT)**: Customers with the shortest expected remaining service time are served first. - **Biggest-in-first-served (BIFS)**: Customers with the largest size are served first. - **Loudest-voice-first-served (LVFS)**: Customers with the loudest voice are served first. ## Common Distributions - Several probability distributions commonly used in queuing models to model arrival and service processes: - **Exponential distribution (M)**: Arrivals are random and unpredictable times. - **Erlang distribution (Ek)**: Delays and arrival times are predictable. - **Hyperexponential distribution (Hk)**: A mixture of k exponential distributions. This captures more variability than a single exponential than the single exponential distribution. - **Deterministic distribution (D)**: Events occur at predictable and fixed time intervals. - **General distribution (G)**: Represents very general, and could be any arrival or service time distribution. ## Example - **M/M/3/20/1500/FCFS:** - **M**: Exponential distribution. - **M**: Exponential distribution. - **3**: Three servers. - **20**: 20 buffers - the system capacity (3 service + 17 waiting). - **1500**: 1500 jobs that can be serviced. - **FCFS**: First-come, first-served. - **Time between successive arrival**: Exponentially distributed. - **Service times**: Exponentially distributed. - **After 20 jobs**: any arriving jobs are lost. - **Service discipline**: First-come, first-served. ## Defaults - In queuing models, there are some defaults that are used when not explicitly specified. These defaults make the models simpler and easier to work with: - **Infinite buffer capacity**: The system never becomes full. - **Infinite population size**: The number of customers is limitless. - **FCFS service discipline**. Customers are served in the order they arrive. - These defaults are sufficient for many queueing problems. - **G/G/1=G/G/1/∞/∞/FCFS**: This notation represents a queueing system with a general arrival process, a general service time distribution, one server, unlimited buffer capacity, an infinite population size, and the first-come, first-served discipline. - **Assume only individual arrivals (no bulk arrivals)**: Customers arrive one at a time (no bundles of customers). ## Arrival Process - **Arrival times**: the times at which customers arrive. - **Interarrival times**: the times between successive customer arrivals. - **Interarrival times**: are independent and identically distributed (IID) random variables. It means each customer arrives independently of the others. - **The most common arrival process: Poisson arrivals**: - Inter-arrival times are exponentially distributed, and they are independent and identically distributed (IID): Poisson arrivals. ## Service Time Distribution - **Service time**: The amount of time each customer spends at the server. - **Service time**: usually assume IID. - **The most commonly used distribution**: Exponential distribution. - **Distribution**: M, E, H, or G. ## Key Variables - The following are some key variables used in queuing models: - **τ = Inter-arrival time**: The time between two successive arrivals. - **λ = Mean arrival rate**: The average number of customers arriving per unit of time. - **s = Service time per job**: The time it takes to serve a single customer. - **μ = Mean service rate per server**: The average number of customers served per unit of time. - **mμ = Total Service rate**: The total number of customers served per unit of time by the server. - **n₁ = Number of jobs waiting**: The number of customers waiting in queue. - **n₁ = Number of jobs receiving service**: The number of customers being served. - **n = Number of jobs in the system**: The total number of customers in the queueing system (in queue and being served). - **Queue Length**: The total number of customers in the queueing system. - **r= Response time**: Total time spent in the system. - **w = Waiting time**: The time spent waiting in queue. ## Rules for All Queues - **The Stability condition**: - **λ < mμ**: The mean arrival rate (λ) must be less than the mean service rate (mμ). - If the mean arrival rate exceeds the mean service rate, the system may become unstable, and the queue will grow infinitely long. - **Finite buffer systems and finite population systems**: Are always stable. - **Finite buffer system**: Arrivals are lost when the number of jobs in the system exceeds the system capacity. - **Finite population systems**: The queue length is always finite, and the average number of jobs in the queue remains limited. ## Little's Law - Little's Law relates the mean number of jobs in the queuing system, the average arrival rate, and the average response time. - **Mean number in the system**: The average number of customers in the queueing system at any time. - **Mean number in the system**: Arrival rate × Mean response time. - **Applies to:** All systems or parts of systems where the number of jobs entering the system equals the number completing the service process. - **Black-box view**: Little's Law applies to a black-box view of the system. ## Application of Little's Law - Applies to just the waiting facility (only customers waiting in queue): - Mean number in the queue = Arrival rate X Mean waiting time. - Applies to those currently receiving the service: - Mean number in service = Arrival rate X Mean service time. ## Example - A monitor on a disk server shows that the average time to satisfy an I/O request is 100 milliseconds (0.1 seconds). The I/O rate is 100 requests per second. - We want to determine the mean number of requests at the disk server. - Applying Little's law: - Mean number in the disk server = Arrival rate × Response time. - Mean number in the disk server = 100 (requests/second) × (0.1 seconds). - Mean number in the disk server = 10 requests.