Queueing Theory and Scheduling

Queueing theory and scheduling is the mathematical study of waiting lines and the strategic allocation of resources to service them. As a core component of systems science, it provides analytical models to understand and predict the behavior of systems where demand for a service contends for limited capacity, focusing on metrics like wait times, queue lengths, and resource utilization. Scheduling, in turn, applies these insights to develop and implement policies and algorithms that determine the order in which tasks or customers are processed, aiming to optimize system performance by minimizing delays, maximizing throughput, or ensuring fairness across diverse applications such as computer networks, manufacturing, and service operations.

1. Introduction to Queueing Systems
   1. Definition and Purpose of Queueing Systems
   2. Real-World Examples of Queueing Systems
      1. Telecommunication Networks
      2. Computer Systems
      3. Manufacturing Systems
      4. Service Centers
      5. Transportation Systems
      6. Healthcare Facilities
   3. Core Components of a Queueing System
      1. Arrival Process
         1. Arrival Rate
         2. Inter-arrival Time Distribution
         3. Batch Arrivals
         4. Time-Dependent Arrivals
         5. Balking and Reneging
      2. Service Mechanism
         1. Service Rate
         2. Service Time Distribution
         3. Service Channels
         4. Service Policies
         5. Service Interruptions
      3. Queue Discipline
         1. First-Come First-Served (FCFS)
         2. Last-Come First-Served (LCFS)
         3. Priority-Based Disciplines
         4. Random Selection
         5. Processor Sharing
         6. Service in Random Order (SIRO)
      4. System Capacity
         1. Infinite Capacity
         2. Finite Capacity
         3. Blocking and Loss
         4. Buffer Management
      5. Number of Servers
         1. Single-Server Systems
         2. Multi-Server Systems
         3. Infinite-Server Systems
   4. Kendall's Notation
      1. Structure and Interpretation
      2. Arrival Distribution (A)
         1. Markovian (M)
         2. Deterministic (D)
         3. General (G)
         4. Erlang (Ek)
         5. Hyperexponential (H2)
      3. Service Time Distribution (B)
         1. Markovian (M)
         2. Deterministic (D)
         3. General (G)
         4. Erlang (Ek)
         5. Hyperexponential (H2)
      4. Number of Servers (c)
      5. System Capacity (K)
      6. Calling Population Size (N)
      7. Queue Discipline (D)
   5. Key Performance Metrics
      1. Queue Length Measures
         1. Average Queue Length
         2. Distribution of Queue Length
         3. Variance of Queue Length
      2. Waiting Time Measures
         1. Average Waiting Time
         2. Waiting Time Distribution
         3. Percentiles of Waiting Time
      3. System Time Measures
         1. Average System Time
         2. System Time Distribution
         3. Response Time Analysis
      4. Server Utilization
         1. Definition and Calculation
         2. Individual Server Utilization
         3. System Utilization
         4. Impact on Performance
      5. Throughput Measures
         1. Effective Arrival Rate
         2. Service Rate
         3. System Throughput
      6. Probability Measures
         1. Probability of Delay
         2. Probability of Blocking
         3. Probability of Loss
         4. Probability of Empty System
   6. Little's Law
      1. Statement and Mathematical Formulation
      2. Proof and Derivation
      3. Conditions for Applicability
      4. Applications and Implications
      5. Extensions and Variations