8.2 Little's law

Little's law is a fundamental theorem in queueing theory that connects key system metrics. It states that the average number of customers in a stable system equals the arrival rate multiplied by the average time spent in the system.

This law applies to various systems, from manufacturing to computer networks. It assumes a stable system with deterministic routing and FIFO processing. Little's law helps analyze and optimize system performance by relating arrival rate, number of customers, and average time in the system.

Definition of Little's law

• Fundamental theorem in queueing theory that relates key performance metrics of a stable system
• States the long-term average number of customers (L) in a system is equal to the long-term average effective arrival rate (λ) multiplied by the average time a customer spends in the system (W)
• Applies to a wide range of systems including manufacturing, service, and computer networks

Assumptions of Little's law

Stable system

Top images from around the web for Stable system

• 

  Perfect Competition – Introduction to Microeconomics View original

  Is this image relevant?

• 

  Littles Law Relations | AllAboutLean.com View original

  Is this image relevant?

• 

  The Science of Kanban – Process | AvailAgility View original

  Is this image relevant?

• 

  Perfect Competition – Introduction to Microeconomics View original

  Is this image relevant?

• 

  Littles Law Relations | AllAboutLean.com View original

  Is this image relevant?

1 of 3

Top images from around the web for Stable system

• 

  Perfect Competition – Introduction to Microeconomics View original

  Is this image relevant?

• 

  Littles Law Relations | AllAboutLean.com View original

  Is this image relevant?

• 

  The Science of Kanban – Process | AvailAgility View original

  Is this image relevant?

• 

  Perfect Competition – Introduction to Microeconomics View original

  Is this image relevant?

• 

  Littles Law Relations | AllAboutLean.com View original

  Is this image relevant?

1 of 3

• Requires the system to be in a steady state where the arrival rate and departure rate are equal
• Implies that the system has been operating for a sufficiently long time and has reached equilibrium
• Ensures that the average number of customers in the system remains constant over time

Deterministic routing

• Assumes that customers follow a fixed and predetermined path through the system
• Requires that the routing of customers is not influenced by random factors or decisions
• Simplifies the analysis by eliminating variability in customer flow

FIFO processing

• Assumes that customers are served in the order they arrive (First-In-First-Out)
• Requires that there is no prioritization or reordering of customers based on their attributes
• Ensures that the average waiting time is the same for all customers in the system

Key variables in Little's law

Arrival rate (λ)

• Represents the average number of customers arriving at the system per unit time
• Measured in units such as customers per hour or requests per second
• Determines the load on the system and influences the overall performance

Departure rate

• Represents the average number of customers leaving the system per unit time
• In a stable system, the departure rate is equal to the arrival rate (λ)
• Reflects the system's ability to process and serve customers efficiently

Number of customers in system (L)

• Represents the average number of customers present in the system at any given time
• Includes customers waiting in the queue and those being served
• Directly impacts the system's capacity and resource utilization

Average time in system (W)

• Represents the average duration a customer spends in the system from arrival to departure
• Includes both the waiting time in the queue and the service time
• Reflects the system's responsiveness and the customer's experience

Mathematical formulation of Little's law

L = λW

• Expresses the fundamental relationship between the key variables in Little's law
• States that the average number of customers in the system (L) is equal to the product of the arrival rate (λ) and the average time in the system (W)
• Provides a simple yet powerful equation to analyze and optimize system performance

Intuitive explanation

• Can be understood through a conservation of flow principle
• In a stable system, the rate at which customers enter the system (λ) must equal the rate at which they leave
• The average number of customers in the system (L) is determined by how long each customer stays in the system (W)

Applying Little's law

Calculating average wait times

• Little's law can be rearranged to solve for the average time in the system (W)
• By measuring the arrival rate (λ) and the average number of customers in the system (L), the average wait time can be calculated as W = L / λ
• Helps in assessing the system's performance and identifying bottlenecks

Determining number of customers

• Little's law can be used to estimate the average number of customers in the system (L)
• By knowing the arrival rate (λ) and the average time in the system (W), the number of customers can be calculated as L = λW
• Useful for capacity planning and resource allocation

Estimating throughput

• Little's law can be applied to estimate the throughput or departure rate of a system
• Given the average number of customers in the system (L) and the average time in the system (W), the throughput can be calculated as λ = L / W
• Helps in assessing the system's processing capability and identifying improvement opportunities

Extensions of Little's law

Time varying arrival rates

• Extends Little's law to handle systems with non-stationary arrival processes
• Allows for the analysis of systems where the arrival rate varies over time (e.g., seasonal demand)
• Requires more advanced mathematical techniques to derive performance measures

Non-FIFO systems

• Generalizes Little's law to systems with non-FIFO service disciplines (e.g., priority queues)
• Accounts for the impact of different scheduling policies on the average waiting time
• Enables the analysis of systems with multiple customer classes or service priorities

Multi-class systems

• Extends Little's law to systems with multiple customer classes or service types
• Considers the distinct arrival rates, service times, and routing probabilities for each class
• Allows for the analysis of complex systems with heterogeneous customer populations

Limitations of Little's law

Unstable systems

• Little's law assumes a stable system in steady state, which may not always hold in practice
• In unstable systems where the arrival rate exceeds the service rate, the assumptions of Little's law are violated
• Leads to unbounded growth in the number of customers and waiting times

Correlated arrivals and service

• Little's law assumes that the arrival process and service times are independent
• In systems with correlated arrivals or service times, the assumptions of Little's law may not hold
• Requires more advanced analysis techniques to capture the dependencies and their impact on performance

Infinite populations

• Little's law assumes a finite population of potential customers
• In systems with an infinite population (e.g., open queueing networks), the arrival rate may not be constant
• Requires modified versions of Little's law or alternative analysis approaches

Examples of Little's law applications

Call center queues

• Helps in determining the average waiting time for customers in a call center queue
• Allows for the estimation of the required number of agents to meet service level targets
• Enables the optimization of staffing levels based on call arrival patterns

Manufacturing systems

• Applies to production lines and inventory systems in manufacturing
• Helps in estimating the average work-in-process inventory and production lead times
• Supports the identification of bottlenecks and the balancing of production flows

Computer networks

• Used in the analysis of packet queues in routers and switches
• Helps in estimating the average packet delay and buffer occupancy
• Enables the sizing of buffers and the optimization of network performance

Little's law in queueing theory

Relationship to Kendall's notation

• Little's law is a fundamental result that applies to various queueing systems
• Kendall's notation (A/B/C) is used to describe the characteristics of a queueing system
• Little's law holds for a wide range of queueing systems, regardless of the specific notation

Role in performance analysis

• Little's law provides a simple yet powerful tool for performance analysis of queueing systems
• Enables the derivation of key performance metrics such as average waiting time and system occupancy
• Serves as a foundation for more advanced queueing theory concepts and analysis techniques

Proofs of Little's law

Sample path proof

• Proves Little's law by considering the sample path of customers through the system
• Analyzes the cumulative number of arrivals and departures over time
• Shows that the time-average number of customers in the system converges to L = λW

Algebraic proof

• Proves Little's law using algebraic manipulations and limit theorems
• Defines the key variables as time-averages and establishes their relationships
• Derives the result L = λW by taking the limit as time approaches infinity