Queueing Theory Fundamentals and Cost Analysis

Fundamentals of Operations Research

Goal Programming Basics

Goal Programming aims to Minimize W, the weighted sum of deviations from the goals. The fundamental relationship is:

Level Achieved – Amount Over + Amount Under = Goal

Introduction to Queueing Theory

The basis of Queueing Theory is the trade-off between the cost of improving service and the costs associated with making customers wait. Queues arise when the short-term demand for service exceeds the capacity (i.e., arrival rates exceed the service rates).

Key Components of a Queueing System

• Calling Population: Refers to the pool of potential customers.
• Customer Behavior: Customers can be patient or impatient (those who leave the line before receiving service).
• Queue Capacity: Can be finite or infinite.
• Queue Discipline: The rule governing the order of service. Common disciplines include First-Come-First-Serve (FCFS), Last-Come-First-Serve (LCFS), Random, or priority-based systems.

The Queueing System Flow

Arrival Process → Waiting Line / Queue → Service Process

The Poisson Process and Interarrival Times

A Poisson process describes arrivals where interarrival times are completely unpredictable. The chance of an arrival in the next minute is always the same. This is known as the lack-of-memory property: the probability of an arrival in the next minute is completely uninfluenced by when the last arrival occurred.

If arrivals occur according to a Poisson process, then the time between two arrivals has an exponential distribution.

Equivalency of Poisson and Exponential Distributions

1. Arrivals occur according to a Poisson process with rate .
2. The number of arrivals follows a Poisson distribution, and the expected number of arrivals per unit time is .
3. The interarrival time follows an exponential distribution with rate .
4. The time between two arrivals is exponentially distributed, and the expected time between two arrivals is 1/ .

Service Rates and Cost Trade-offs

For a stable system, the total service rate must be greater than the total arrival rate.

Utilization Factor (U)

The Utilization Factor, U, is the average fraction of time that a server is busy serving customers.

Typical Cost Trade-offs for Service

1. Service Cost (SC):
   • Depends on the number of servers (S).
   • Standard assumption: constant server cost ($C_s$ per server per unit time).
   • Formula: $SC = C_s \times S$
2. Waiting Cost (WC):
   • $C_w$: waiting cost per unit of time per customer.
   • Waiting cost is proportional to the number of customers waiting in line ($L_q$). Formula: $WC = C_w \times L_q$.
   • Alternatively, waiting cost may be proportional to the total amount of time a customer waits in the system ($L$). Formula: $WC = C_w \times L$.