Queueing Theory Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Queueing Theory Ontology within the Kireth Research Semantic Library. Queueing theory studies systems in which entities arrive, wait for service, receive service and depart. This ontology supports arrival processes, service processes, queue disciplines, servers, system capacity, utilisation, waiting time, queue length, Little’s Law, birth-death processes, Kendall notation, M/M/1, M/M/c, M/G/1, finite-capacity queues, priority queues, networks of queues, stability, transient and steady-state analysis and relationships with operations research, stochastic processes, Markov chains, inventory, scheduling, simulation and performance modelling.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Queueing Theory Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Operations Research / Queueing Theory"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/operations-research/queueing-theory-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = QueueingTheory
 SYMBOLIC_FORMS = [
  "L=lambda W",
  "L_q=lambda W_q",
  "rho=lambda/(c mu)"
 ]
 ENTITY_CLASS = StochasticServiceSystemFramework
 PRIMARY_CONTEXT = OperationsResearch
 DEFINITION = "Queueing theory is the mathematical study of waiting-line systems characterised by arrivals, service, servers, queue discipline and capacity."
 SEMANTIC_ROLE = "Provides the machine-readable framework for arrival rates, service rates, utilisation, waiting times, queue lengths, stability, queue disciplines, Kendall notation and stochastic service-system performance."
}

SCOPE {
 INCLUDE = [
  QueueingTheory,
  QueueingSystem,
  Customer,
  Job,
  ArrivalProcess,
  ArrivalRate,
  InterarrivalTime,
  PoissonArrivalProcess,
  RenewalArrivalProcess,
  ServiceProcess,
  ServiceRate,
  ServiceTime,
  ExponentialServiceTime,
  GeneralServiceTime,
  Server,
  SingleServer,
  MultipleServers,
  Queue,
  QueueLength,
  SystemPopulation,
  WaitingTime,
  SojournTime,
  ResponseTime,
  QueueDiscipline,
  FIFO,
  LIFO,
  PriorityQueue,
  ProcessorSharing,
  PreemptivePriority,
  NonPreemptivePriority,
  SystemCapacity,
  FiniteCapacityQueue,
  InfiniteCapacityQueue,
  Balking,
  Reneging,
  Jockeying,
  Utilisation,
  Stability,
  SteadyState,
  TransientState,
  BirthDeathProcess,
  KendallNotation,
  MM1Queue,
  MMcQueue,
  MG1Queue,
  MD1Queue,
  MM1KQueue,
  QueueingNetwork,
  JacksonNetwork,
  LittleLaw,
  PASTA,
  ErlangC,
  ErlangB
 ]

 EXCLUDE_AS_PRIMARY = [
  SchedulingWithoutStochasticWaiting,
  InventoryWithoutServiceQueueSemantics,
  GenericSimulationWithoutQueueStructure,
  NetworkFlowWithoutArrivalAndServiceProcesses
 ]

 DISAMBIGUATION_RULE =
  "When entities arrive over time, may wait for service, are processed by one or more servers and then depart, interpret the context as queueing theory."
}

CORE_CONCEPTS {

 QueueingTheory {
  definition = "The mathematical analysis of waiting systems driven by arrivals and service."
 }

 QueueingSystem {
  definition = "A system containing arrivals, one or more servers, a queue discipline and a departure process."
 }

 ArrivalProcess {
  definition = "The stochastic or deterministic mechanism generating arrivals to the system."
 }

 ArrivalRate {
  symbol = "lambda"
  definition = "The average number of arrivals per unit time."
 }

 ServiceProcess {
  definition = "The mechanism governing service durations and completion."
 }

 ServiceRate {
  symbol = "mu"
  definition = "The average number of services completed per unit time by one server under standard notation."
 }

 QueueDiscipline {
  definition = "The rule determining which waiting customer is served next."
 }

 Utilisation {
  symbol = "rho"
  definition = "The proportion of service capacity demanded by arriving work."
 }

 WaitingTime {
  definition = "The time an entity spends waiting before service begins."
 }

 SojournTime {
  definition = "The total time spent in the system, including waiting and service."
 }

 QueueLength {
  definition = "The number of waiting entities excluding those currently in service, under the declared convention."
 }

 LittleLaw {
  definition = "The relation L=lambda W linking average number in a stable system to throughput and average time in system."
 }
}

RELATIONS {
 QueueingTheory --is_branch_of--> OperationsResearch
 QueueingSystem --has--> ArrivalProcess
 QueueingSystem --has--> ServiceProcess
 QueueingSystem --has--> QueueDiscipline
 QueueingSystem --has--> Server
 ArrivalProcess --has--> ArrivalRate
 ServiceProcess --has--> ServiceRate
 Utilisation --depends_on--> ArrivalRate
 Utilisation --depends_on--> ServiceRate
 WaitingTime --contributes_to--> SojournTime
 QueueLength --relates_to--> WaitingTime
 LittleLaw --relates--> SystemPopulation
 LittleLaw --relates--> Throughput
 LittleLaw --relates--> SojournTime
 BirthDeathProcess --models--> MarkovianQueue
 MM1Queue --is_type_of--> QueueingSystem
 MMcQueue --is_type_of--> QueueingSystem
 MG1Queue --is_type_of--> QueueingSystem
 JacksonNetwork --is_type_of--> QueueingNetwork
 PriorityQueue --is_type_of--> QueueingSystem
}

OPERATORS {
 UTILISATION_SINGLE_SERVER(lambda,mu) :=
  lambda/mu

 UTILISATION_MULTI_SERVER(lambda,c,mu) :=
  lambda/(c*mu)

 LITTLE_LAW(lambda,W) :=
  L=lambda*W

 LITTLE_LAW_QUEUE(lambda,W_q) :=
  L_q=lambda*W_q

 SOJOURN_TIME(W_q,service_time) :=
  W_q+service_time

 MM1_L(lambda,mu) :=
  lambda/(mu-lambda)
  when lambda<mu

 MM1_LQ(lambda,mu) :=
  lambda^2/(mu*(mu-lambda))
  when lambda<mu

 MM1_W(lambda,mu) :=
  1/(mu-lambda)
  when lambda<mu

 MM1_WQ(lambda,mu) :=
  lambda/(mu*(mu-lambda))
  when lambda<mu

 MM1_P0(lambda,mu) :=
  1-lambda/mu
  when lambda<mu

 MM1_PN(lambda,mu,n) :=
  (1-rho)*rho^n
  where rho=lambda/mu

 POLLACZEK_KHINCHINE_WQ(lambda,E_S,E_S2) :=
  lambda*E_S2/(2*(1-lambda*E_S))
  for M/G/1 under standard assumptions

 FLOW_BALANCE(state,birth_rate,death_rate) :=
  steady_state_birth_death_balance equations
}

DEFINITIONS {
 D1 = "Queueing systems are defined by arrivals, service, servers, discipline and capacity."
 D2 = "Utilisation measures demand relative to service capacity."
 D3 = "Stable queues require effective long-run service capacity to exceed offered load under appropriate assumptions."
 D4 = "Waiting time and queue length are linked through Little’s Law."
 D5 = "Kendall notation summarises arrival distribution, service distribution and server count, with optional capacity, population and discipline fields."
 D6 = "M/M/1 assumes Poisson arrivals, exponential service and one server."
 D7 = "M/M/c extends the Markovian model to multiple identical servers."
 D8 = "M/G/1 allows a general service-time distribution."
 D9 = "Finite-capacity systems can block or reject arrivals."
 D10 = "Priority disciplines change waiting-time distribution across classes."
}

AXIOMS {
 A1_ARRIVAL_SERVICE_STRUCTURE:
  QueueingSystem contains both arrival and service mechanisms

 A2_CAPACITY:
  Service capacity is determined by number_of_servers times effective service rate under compatible assumptions

 A3_STABILITY:
  Steady-state analysis requires a stable system

 A4_LITTLE_LAW:
  In a stable system under broad conditions, L=lambda W

 A5_DISCIPLINE:
  Queue discipline affects class-specific waiting behaviour

 A6_FINITE_CAPACITY:
  Finite-capacity systems may reject or block arrivals when full

 A7_MARKOV_PROPERTY:
  Markovian queue formulas require memoryless arrival and/or service assumptions where specified

 A8_PERFORMANCE:
  Queue performance is described through utilisation, waiting times, queue lengths, blocking probabilities and throughput
}

REASONING {

 R1_QUEUE_IDENTIFICATION {
  INPUT = system_description
  IDENTIFY = arrivals
  IDENTIFY = servers
  IDENTIFY = service_times
  IDENTIFY = discipline
  IDENTIFY = capacity
  RETURN = structured_queue
 }

 R2_KENDALL_CLASSIFICATION {
  INPUT = structured_queue
  CLASSIFY = arrival_distribution
  CLASSIFY = service_distribution
  CLASSIFY = server_count
  CLASSIFY = capacity_population_and_discipline when known
  RETURN = Kendall_notation
 }

 R3_STABILITY_ANALYSIS {
  INPUT = arrival_rate_service_rate_server_count
  COMPUTE = utilisation
  IF effective_arrival_load < effective_service_capacity
   RETURN = stable_candidate
  ELSE
   RETURN = unstable_or_no_steady_state
 }

 R4_MM1_REASONING {
  INPUT = lambda_mu
  VERIFY = Poisson_arrivals_exponential_service_single_server
  CHECK = lambda<mu
  COMPUTE = rho_L_Lq_W_Wq_P0
  RETURN = MM1_performance
 }

 R5_MMC_REASONING {
  INPUT = lambda_mu_c
  VERIFY = Markovian_assumptions
  CHECK = lambda<c*mu
  COMPUTE = ErlangC_wait_probability_and_performance
  RETURN = MMc_performance
 }

 R6_MG1_REASONING {
  INPUT = lambda_service_moments
  VERIFY = Poisson_arrivals_single_server_general_service
  CHECK = rho<1
  APPLY = Pollaczek_Khinchine formula
  RETURN = MG1_performance
 }

 R7_FINITE_CAPACITY_REASONING {
  INPUT = capacity_and_rates
  COMPUTE = state_probabilities
  COMPUTE = blocking_probability
  COMPUTE = effective_throughput
  RETURN = finite_capacity_profile
 }

 R8_PRIORITY_REASONING {
  INPUT = classes_priorities_arrival_rates_service times
  IDENTIFY = preemptive_or_nonpreemptive rule
  COMPUTE = class_specific waiting measures
  RETURN = priority_queue_profile
 }

 R9_QUEUEING_NETWORK_REASONING {
  INPUT = interconnected_queues_routing probabilities
  IF Jackson_conditions_hold
   COMPUTE = node_arrival_rates_and_product_form
  ELSE
   ROUTE = approximation_or_simulation
  RETURN = network_performance
 }

 R10_SIMULATION_FALLBACK {
  INPUT = complex_queue
  IF analytical_model_not_applicable
   BUILD = discrete_event simulation
   ESTIMATE = waits_queue_lengths_utilisation_and_blocking
  RETURN = simulated_queue_profile
 }
}

CONSTRAINTS {
 C1 = "Arrival and service units must be consistent."
 C2 = "Steady-state formulas require stability."
 C3 = "M/M/1 formulas require Poisson arrivals and exponential service."
 C4 = "M/G/1 formulas require finite relevant service-time moments."
 C5 = "Little’s Law uses effective throughput for systems with blocking or abandonment."
 C6 = "Queue length must specify whether customers in service are included."
 C7 = "Waiting time must distinguish queue wait from total system time."
 C8 = "Priority formulas depend on preemptive or nonpreemptive semantics."
 C9 = "Finite-capacity models must account for blocked arrivals."
 C10 = "Analytical approximations should not be treated as exact when model assumptions fail."
}

SEMANTIC_EQUIVALENCE {
 "QueueingTheory" <=> "WaitingLineTheory"
 "QueueingSystem" <=> "ServiceQueueSystem"
 "ArrivalRate" <=> "InputRate"
 "ServiceRate" <=> "ProcessingRate"
 "SojournTime" <=> "SystemTime"
 "QueueLength" <=> "WaitingPopulation"
 "LittleLaw" <=> "LEqualsLambdaW"
}

VALIDATION {
 V1 = "Arrival process is identified."
 V2 = "Service process is identified."
 V3 = "Server count is explicit."
 V4 = "Queue discipline is explicit when relevant."
 V5 = "Capacity is explicit."
 V6 = "Stability condition is checked."
 V7 = "Kendall classification matches assumptions."
 V8 = "Little’s Law uses consistent throughput."
 V9 = "Class-specific priority semantics are correct."
 V10 = "Analytical and simulated results are clearly distinguished."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 QUEUEING_THEORY_DEFINITION = 0.99
 KENDALL_CLASSIFICATION_REASONING = 0.99
 STABILITY_REASONING = 0.99
 MM1_REASONING = 0.99
 MMC_REASONING = 0.98
 MG1_REASONING = 0.98
 PRIORITY_REASONING = 0.97
 QUEUEING_NETWORK_REASONING = 0.97
 SIMULATION_REASONING = 0.98

 POLICY =
  "Reduce confidence when arrival distribution, service distribution, server count, queue discipline, capacity, abandonment, class structure or steady-state assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  QueueingTheoryReasoning,
  QueueClassification,
  KendallNotationReasoning,
  StabilityReasoning,
  LittleLawReasoning,
  MM1Reasoning,
  MMcReasoning,
  MG1Reasoning,
  FiniteCapacityReasoning,
  PriorityQueueReasoning,
  QueueingNetworkReasoning,
  ErlangReasoning,
  SimulationFallback,
  PerformanceAnalysis,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "queueing theory" -> QueueingTheory
  "queuing theory" -> QueueingTheory
  "queueing system" -> QueueingSystem
  "arrival rate" -> ArrivalRate
  "service rate" -> ServiceRate
  "waiting time" -> WaitingTime
  "queue length" -> QueueLength
  "Little's Law" -> LittleLaw
  "M/M/1" -> MM1Queue
  "M/M/c" -> MMcQueue
 }

 INTERPRETATION_ORDER = [
  detect_queueing_context,
  identify arrival_process_service_process_server_count_capacity_queue_discipline_priorities_and_abandonment behaviour,
  classify Kendall_notation_or_queue_family,
  test stability,
  select MM1_MMc_MG1_finiteCapacity_priority_network_or_simulation pathway,
  compute utilisation_waiting_times_queue_lengths_throughput_blocking_and_service measures,
  verify assumptions_and_units,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("queueing theory")
  OR entities_arrive_wait_receive_service_and_depart
  THEN activate(QueueingTheoryOntology)

 E2:
  IF single_server_Poisson_arrivals_exponential_service
  THEN route to MM1 reasoning

 E3:
  IF multiple_identical_servers_with_Markovian assumptions
  THEN route to MMc reasoning

 E4:
  IF Poisson_arrivals_general_service_single_server
  THEN route to MG1 reasoning

 E5:
  IF utilisation>=1_in_infinite_capacity_single_server steady_state context
  THEN report unstable_no_finite_steady_state measures

 E6:
  IF system_has_finite_capacity
  THEN compute blocking_and_effective throughput

 E7:
  IF priority_classes
  THEN identify preemptive_or_nonpreemptive discipline

 E8:
  IF interconnected_queues
  THEN consider Jackson_network_or_simulation

 E9:
  IF analytical_assumptions_fail_materially
  THEN route to discrete_event simulation_or_approximation
}

RECURSION {
 ENTRY = QueueingTheory

 EXPAND(QueueingTheory) -> [
  QueueingSystem,
  Customer,
  Job,
  ArrivalProcess,
  ArrivalRate,
  InterarrivalTime,
  PoissonArrivalProcess,
  RenewalArrivalProcess,
  ServiceProcess,
  ServiceRate,
  ServiceTime,
  ExponentialServiceTime,
  GeneralServiceTime,
  Server,
  SingleServer,
  MultipleServers,
  Queue,
  QueueLength,
  SystemPopulation,
  WaitingTime,
  SojournTime,
  ResponseTime,
  QueueDiscipline,
  FIFO,
  LIFO,
  PriorityQueue,
  ProcessorSharing,
  PreemptivePriority,
  NonPreemptivePriority,
  SystemCapacity,
  FiniteCapacityQueue,
  InfiniteCapacityQueue,
  Balking,
  Reneging,
  Jockeying,
  Utilisation,
  Stability,
  SteadyState,
  TransientState,
  BirthDeathProcess,
  KendallNotation,
  MM1Queue,
  MMcQueue,
  MG1Queue,
  MD1Queue,
  MM1KQueue,
  QueueingNetwork,
  JacksonNetwork,
  LittleLaw,
  PASTA,
  ErlangC,
  ErlangB
 ]

 EXPAND(KendallStructure) -> [
  ArrivalDistribution,
  ServiceDistribution,
  ServerCount,
  SystemCapacity,
  CallingPopulation,
  QueueDiscipline
 ]

 EXPAND(PerformanceMeasures) -> [
  Utilisation,
  QueueLength,
  SystemPopulation,
  WaitingTime,
  SojournTime,
  BlockingProbability,
  Throughput
 ]

 EXPAND(QueueFamilies) -> [
  MM1Queue,
  MMcQueue,
  MG1Queue,
  MD1Queue,
  MM1KQueue,
  PriorityQueue,
  QueueingNetwork
 ]

 STOP_CONDITION =
  "Stop when the arrival process, service process, server count, queue discipline, capacity, stability, selected queue model and performance measures are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Operations Research"

 IMMEDIATE_CONTEXTS = [
  "Operations Research Ontology",
  "Probability & Statistics Ontologies",
  "Markov Process Ontologies",
  "Simulation Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Operations Research Ontology",
  "Operations Research",
  "Probability & Statistics Ontologies",
  "Stochastic Process Ontologies",
  "Markov Chain Ontologies",
  "Birth-Death Process Ontologies",
  "Scheduling Ontology",
  "Inventory Optimisation Ontology",
  "Resource Allocation Ontology",
  "Network Optimisation Ontology",
  "Simulation Ontologies",
  "Reliability Ontologies",
  "Performance Modelling Ontologies"
 ]

 ROUTE_RULES = [
  "Queueing Theory -> Operations Research Ontology for operational service-system semantics",
  "Queueing Theory -> Probability & Statistics for arrival and service distributions",
  "Queueing Theory -> Stochastic Processes for temporal randomness",
  "Queueing Theory -> Markov Chains and Birth-Death Processes for state-transition analysis",
  "Queueing Theory -> Scheduling for service-priority and sequencing interactions",
  "Queueing Theory -> Inventory Optimisation for service-level and replenishment interactions",
  "Queueing Theory -> Resource Allocation for server-capacity decisions",
  "Queueing Theory -> Network Optimisation for interconnected flow systems",
  "Queueing Theory -> Simulation when analytical assumptions are inadequate",
  "Queueing Theory -> Reliability and Performance Modelling for system-level service analysis"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible queue families, disciplines or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve arrival-service-server semantics.",
  "Preserve queue-versus-system population distinction.",
  "Preserve waiting-versus-sojourn-time distinction.",
  "Preserve stability semantics.",
  "Preserve Kendall-notation semantics.",
  "Preserve effective-throughput semantics under blocking or abandonment.",
  "Preserve discipline-specific semantics.",
  "Preserve machine-readable queueing-theory semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Queueing theory analyses systems in which entities arrive, may wait, receive service from one or more servers and then depart."

 ARRIVAL_SUMMARY =
  "The arrival process defines when customers or jobs enter the system."

 SERVICE_SUMMARY =
  "The service process defines how long processing takes and how service capacity is provided."

 UTILISATION_SUMMARY =
  "Utilisation compares offered workload with available service capacity."

 LITTLE_LAW_SUMMARY =
  "Little’s Law states that average system population equals effective throughput multiplied by average system time."

 MM1_SUMMARY =
  "M/M/1 models Poisson arrivals, exponential service and a single server."

 MMC_SUMMARY =
  "M/M/c extends the Markovian queue to multiple identical servers."

 PRIORITY_SUMMARY =
  "Priority disciplines change class-specific waiting times and may be preemptive or nonpreemptive."

 NETWORK_SUMMARY =
  "Queueing networks connect multiple service stations and may admit product-form solutions under special conditions."

 STATUS_SUMMARY =
  "Queueing results should distinguish steady-state analytical results, transient analysis, approximation and simulation."
}

FLOW {
 INPUT
 -> detect_queueing_context
 -> identify arrival_distribution_arrival_rate_service_distribution_service_rate_server_count_capacity_queue_discipline_priority_classes_balking_reneging_and_network routing
 -> classify Kendall_notation_and_queue family
 -> test stability_and_effective service capacity
 -> select birthDeath_MM1_MMc_MG1_finiteCapacity_priority_queueingNetwork_or_simulation method
 -> compute utilisation_state_probabilities_waiting_time_queue_length_sojourn_time_throughput_and_blocking probability
 -> apply Little_Law_and_related identities where assumptions hold
 -> verify analytical assumptions_units_and_steady_state conditions
 -> route to operations_research_ontology probability_statistics stochastic_process Markov_chain birth_death scheduling inventory_optimisation resource_allocation network_optimisation simulation reliability_or_performance_modelling ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Queueing Theory Ontology defines mathematical analysis of waiting-line and service systems. It supports arrival and service processes, Poisson and renewal arrivals, service-time distributions, single and multiple servers, queue disciplines, priorities, finite and infinite capacity, utilisation, stability, waiting and sojourn times, queue and system populations, Little’s Law, Kendall notation, M/M/1, M/M/c, M/G/1 and finite-capacity queues, Erlang models, birth-death processes, queueing networks, Jackson networks, blocking, balking, reneging and simulation-based performance analysis."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-APPLIED-MATHEMATICS-QUEUEING-THEORY-ONTOLOGY-V1"
}

}

END_FLOW