Queueing Theory Ontology

flow "QueueingTheoryOntology2" v4.0

# QUEUEING THEORY ONTOLOGY 2
# Kireth Semantic Research Archive
# Authors: Mark Anthony Higgins — Sky (Recursive AI)

PAGE:
  url: "https://kirethresearch.org/booksai-core/ontologies/probability-statistics-ontologies/stochastic-mathematics/queueing-theory-ontology-2.html"
  title: "Queueing Theory Ontology 2"
  domain: "Probability and Statistics"
  category: "Stochastic Mathematics"
  entity: QUEUEING_THEORY
  entity_type: STOCHASTIC_SYSTEMS_FRAMEWORK

DEFINE:
  QUEUEING_THEORY :=
    MATHEMATICAL_FRAMEWORK(
      ARRIVAL_PROCESS,
      SERVICE_PROCESS,
      WAITING_LINE,
      SERVERS,
      QUEUE_DISCIPLINE,
      SYSTEM_CAPACITY,
      PERFORMANCE_MEASURES
    )

PURPOSE:
  MODEL_RANDOM_SERVICE_SYSTEMS
  TO:
    ESTIMATE_WAITING
    ESTIMATE_CONGESTION
    ESTIMATE_UTILISATION
    PLAN_CAPACITY

ENTITIES:
  CUSTOMER: ARRIVING_ENTITY
  ARRIVAL_PROCESS: STOCHASTIC_PROCESS
  SERVICE_TIME: NONNEGATIVE_RANDOM_VARIABLE
  SERVER: SERVICE_RESOURCE
  QUEUE: WAITING_POPULATION
  QUEUE_DISCIPLINE: SERVICE_ORDER_RULE
  SYSTEM_CAPACITY: MAXIMUM_SYSTEM_POPULATION
  UTILISATION: RESOURCE_LOAD_MEASURE
  WAITING_TIME: RANDOM_DURATION
  SOJOURN_TIME: TOTAL_TIME_IN_SYSTEM
  QUEUE_LENGTH: NUMBER_WAITING
  SYSTEM_SIZE: NUMBER_WAITING_PLUS_IN_SERVICE

RELATIONSHIPS:
  CUSTOMER -> ARRIVES_VIA -> ARRIVAL_PROCESS
  CUSTOMER -> JOINS -> QUEUE
  QUEUE -> FEEDS -> SERVER
  SERVER -> PROVIDES -> SERVICE
  SERVICE_COMPLETION -> CAUSES -> DEPARTURE
  QUEUE_DISCIPLINE -> DETERMINES -> SERVICE_ORDER
  ARRIVAL_RATE -> CONTRIBUTES_TO -> SYSTEM_LOAD
  SERVICE_RATE -> DETERMINES -> SERVICE_CAPACITY

KENDALL_NOTATION:
  form: A/S/c/K/N/D
  A: INTERARRIVAL_DISTRIBUTION
  S: SERVICE_TIME_DISTRIBUTION
  c: NUMBER_OF_SERVERS
  K: SYSTEM_CAPACITY
  N: CALLING_POPULATION
  D: QUEUE_DISCIPLINE

QUEUE_DISCIPLINES:
  - FCFS
  - LCFS
  - RANDOM_ORDER
  - PRIORITY
  - PROCESSOR_SHARING

ARRIVAL_PROCESS:
  models:
    - POISSON_PROCESS
    - RENEWAL_PROCESS
    - BATCH_ARRIVAL_PROCESS
    - MARKOV_MODULATED_PROCESS

SERVICE_PROCESS:
  service_rate:
    mu := 1/E[S]
    WHEN_MEAN_FINITE

  models:
    - EXPONENTIAL
    - DETERMINISTIC
    - GENERAL
    - PHASE_TYPE

TRAFFIC_INTENSITY:
  single_server:
    rho := lambda/mu

  c_servers:
    rho := lambda/(c*mu)

STABILITY:
  M_M_1:
    rho < 1

  M_M_C:
    lambda < c*mu

  general:
    LONG_RUN_SERVICE_CAPACITY_MUST_EXCEED_EFFECTIVE_LOAD
    UNDER_MODEL_SPECIFIC_CONDITIONS

LITTLE_LAW:
  system:
    L := lambda_eff * W

  queue:
    L_q := lambda_eff * W_q

  requirements:
    - STABLE_LONG_RUN_SYSTEM
    - CONSISTENT_CUSTOMER_POPULATION
    - FINITE_RELEVANT_AVERAGES

M_M_1:
  assumptions:
    ARRIVALS: POISSON_RATE_lambda
    SERVICE: EXPONENTIAL_RATE_mu
    SERVERS: 1
    CAPACITY: INFINITE_STANDARD_MODEL

  stability:
    rho := lambda/mu < 1

  stationary_probability:
    pi_n := (1-rho)*rho^n

  expected_system_size:
    L := rho/(1-rho)

  expected_queue_length:
    L_q := rho^2/(1-rho)

  expected_system_time:
    W := 1/(mu-lambda)

  expected_waiting_time:
    W_q := lambda/[mu*(mu-lambda)]

  relation:
    W := W_q + 1/mu

M_M_C:
  assumptions:
    POISSON_ARRIVALS
    EXPONENTIAL_SERVICE
    c_IDENTICAL_SERVERS

  utilisation:
    rho := lambda/(c*mu)

  stability:
    rho < 1

  probability_wait:
    ERLANG_C

M_M_C_C:
  type:
    LOSS_SYSTEM

  property:
    NO_WAITING_ROOM

  blocking_probability:
    ERLANG_B

ERLANG_B:
  offered_load:
    a := lambda/mu

  B(c,a) :=
    [a^c/c!]
    /
    SUM[k=0..c] a^k/k!

M_M_1_K:
  capacity:
    K

  when_full:
    ARRIVAL_BLOCKED_OR_LOST

  effective_arrival_rate:
    lambda_eff := lambda*(1-pi_K)

M_G_1:
  arrivals:
    POISSON

  service:
    GENERAL_IID

  utilisation:
    rho := lambda*E[S]

  stability:
    rho < 1

POLLACZEK_KHINCHINE:
  W_q :=
    lambda*E[S^2]
    /
    (2*(1-rho))

  W :=
    W_q + E[S]

M_D_1:
  service:
    DETERMINISTIC

  relation:
    SPECIAL_CASE_OF_M_G_1

G_G_1:
  arrivals:
    GENERAL

  service:
    GENERAL

KINGMAN_APPROXIMATION:
  W_q approximately:
    [rho/(1-rho)]
    * [(c_a^2+c_s^2)/2]
    * E[S]

  role:
    APPROXIMATE_MEAN_WAITING_TIME

QUEUE_LENGTH:
  Q(t):
    NUMBER_WAITING

SYSTEM_SIZE:
  N(t):
    NUMBER_WAITING_PLUS_IN_SERVICE

WAITING_TIME:
  W_q:
    TIME_FROM_ARRIVAL_TO_SERVICE_START

SOJOURN_TIME:
  W:
    TIME_FROM_ARRIVAL_TO_DEPARTURE

  relation:
    W := W_q + SERVICE_TIME

UTILISATION:
  standard_single_server:
    FRACTION_OF_TIME_SERVER_BUSY

  caution:
    WAITING_TIME_CAN_GROW_RAPIDLY
    AS:
      rho APPROACHES 1

PASTA:
  full_name:
    POISSON_ARRIVALS_SEE_TIME_AVERAGES

  property:
    POISSON_ARRIVALS_OBSERVE_TIME_AVERAGE_STATE_DISTRIBUTION
    UNDER_STANDARD_CONDITIONS

BURKE_THEOREM:
  standard_stationary_M_M_1:
    DEPARTURE_PROCESS_IS_POISSON_RATE_lambda

BUSY_PERIOD:
  definition:
    INTERVAL_SERVER_REMAINS_CONTINUOUSLY_BUSY

  M_M_1_mean:
    E[B] := 1/(mu-lambda)

STEADY_STATE:
  requires:
    STABILITY
    AND:
      MODEL_SPECIFIC_ERGODIC_CONDITIONS

TRANSIENT_ANALYSIS:
  use_when:
    - SHORT_HORIZON
    - INITIAL_STATE_MATTERS
    - TIME_VARYING_DEMAND

TIME_VARYING_QUEUE:
  parameters:
    lambda(t)
    mu(t)

  caution:
    CONSTANT_RATE_STEADY_STATE_FORMULAS_MAY_BE_INVALID

ABANDONMENT:
  customer:
    MAY_LEAVE_BEFORE_SERVICE

BALKING:
  customer:
    MAY_DECIDE_NOT_TO_JOIN

RETRIAL:
  blocked_customer:
    MAY_RETRY_LATER

PRIORITY_QUEUE:
  types:
    - PREEMPTIVE
    - NONPREEMPTIVE

NETWORK_OF_QUEUES:
  structure:
    MULTIPLE_SERVICE_NODES

  routing:
    CUSTOMERS_MOVE_BETWEEN_NODES

JACKSON_NETWORK:
  assumptions:
    EXTERNAL_POISSON_ARRIVALS
    EXPONENTIAL_SERVICE
    MARKOVIAN_ROUTING

  result:
    PRODUCT_FORM_STATIONARY_DISTRIBUTION
    UNDER_STANDARD_STABILITY_CONDITIONS

SIMULATION:
  events:
    - ARRIVAL
    - SERVICE_COMPLETION
    - ABANDONMENT

  flow:
    INITIALISE_SYSTEM
      -> SCHEDULE_EVENTS
      -> ADVANCE_TO_NEXT_EVENT
      -> UPDATE_STATE
      -> COLLECT_STATISTICS
      -> REPEAT

PERFORMANCE_MEASURES:
  - L
  - L_q
  - W
  - W_q
  - UTILISATION
  - THROUGHPUT
  - BLOCKING_PROBABILITY
  - SERVICE_LEVEL
  - ABANDONMENT_PROBABILITY

CAPACITY_PLANNING:
  choose:
    - NUMBER_OF_SERVERS
    - SERVICE_RATE
    - BUFFER_CAPACITY

  subject_to:
    - WAITING_TARGET
    - SERVICE_LEVEL
    - COST_CONSTRAINT

MODEL_CONNECTIONS:
  QUEUEING_THEORY -> CONNECTS_TO -> STOCHASTIC_PROCESS
  QUEUEING_THEORY -> CONNECTS_TO -> MARKOV_PROCESS
  QUEUEING_THEORY -> CONNECTS_TO -> POISSON_PROCESS
  QUEUEING_THEORY -> CONNECTS_TO -> RENEWAL_PROCESS
  QUEUEING_THEORY -> CONNECTS_TO -> BIRTH_DEATH_PROCESS
  QUEUEING_THEORY -> CONNECTS_TO -> LITTLE_LAW

APPLICATIONS:
  QUEUEING_THEORY -> SUPPORTS -> TELECOMMUNICATIONS
  QUEUEING_THEORY -> SUPPORTS -> CALL_CENTRES
  QUEUEING_THEORY -> SUPPORTS -> COMPUTER_NETWORKS
  QUEUEING_THEORY -> SUPPORTS -> HEALTHCARE_OPERATIONS
  QUEUEING_THEORY -> SUPPORTS -> MANUFACTURING
  QUEUEING_THEORY -> SUPPORTS -> TRANSPORTATION
  QUEUEING_THEORY -> SUPPORTS -> CLOUD_COMPUTING

SEMANTIC_EQUIVALENCE:
  "queueing theory" ~= "waiting-line theory"
  "sojourn time" ~= "total time in system"
  "M/M/1" ~= "single-server queue with Poisson arrivals and exponential service"

  EXCLUDE_EQUIVALENCE:
    QUEUE_LENGTH != SYSTEM_SIZE
    WAITING_TIME != SOJOURN_TIME
    ARRIVAL_RATE != THROUGHPUT_BY_DEFAULT
    UTILISATION != PROBABILITY_OF_WAIT_BY_DEFAULT
    POISSON_ARRIVAL != GENERAL_RENEWAL_ARRIVAL
    STABILITY != ZERO_WAITING

VALIDATION_RULES:
  RULE_1:
    ARRIVAL_PROCESS_MUST_BE_DEFINED

  RULE_2:
    SERVICE_TIME_DISTRIBUTION_MUST_BE_DEFINED

  RULE_3:
    NUMBER_OF_SERVERS_MUST_BE_POSITIVE_INTEGER

  RULE_4:
    QUEUE_DISCIPLINE_MUST_BE_EXPLICIT_OR_STANDARD_CONTEXT_STATED

  RULE_5:
    SYSTEM_CAPACITY_MUST_BE_DEFINED_OR_DECLARED_INFINITE

  RULE_6:
    STEADY_STATE_FORMULAS_REQUIRE_STABILITY_AND_MODEL_ASSUMPTIONS

  RULE_7:
    LITTLE_LAW_MUST_USE_CONSISTENT_POPULATION_AND_EFFECTIVE_RATE

  RULE_8:
    TIME_VARYING_SYSTEM_MUST_NOT_BLINDLY_USE_CONSTANT_RATE_STEADY_STATE_FORMULAS

CONFIDENCE:
  ontology_identity: 0.99
  queueing_definition: 0.99
  mm1_structure: 0.99
  little_law_structure: 0.99
  multiserver_structure: 0.99
  renewal_relationship: 0.99
  performance_measure_structure: 0.99

UPDATE_MODEL:
  IF:
    NEW_ARRIVAL_OCCURS
  THEN:
    UPDATE:
      SYSTEM_SIZE
      QUEUE_LENGTH
      ARRIVAL_STATISTICS

  IF:
    SERVICE_COMPLETION_OCCURS
  THEN:
    UPDATE:
      SYSTEM_SIZE
      SERVER_STATE
      WAITING_QUEUE
      DEPARTURE_STATISTICS

  IF:
    PARAMETERS_CHANGE
  THEN:
    UPDATE:
      LOAD
      UTILISATION
      PERFORMANCE_ESTIMATES
    REVALIDATE:
      STABILITY

  PRESERVE:
    ARRIVAL_HISTORY
    SERVICE_HISTORY
    QUEUE_DISCIPLINE
    SERVER_COUNT
    CAPACITY
    MODEL_PARAMETERS
    DATA_PROVENANCE

AI_CONSUMPTION:
  parse_as: FORMAL_SEMANTIC_SPECIFICATION
  execution_mode: RECURSIVE_REASONING

  preferred_reasoning_order:
    - IDENTIFY_ARRIVAL_PROCESS
    - IDENTIFY_SERVICE_DISTRIBUTION
    - IDENTIFY_SERVER_COUNT
    - IDENTIFY_CAPACITY
    - IDENTIFY_QUEUE_DISCIPLINE
    - COMPUTE_TRAFFIC_INTENSITY
    - CHECK_STABILITY
    - SELECT_QUEUE_MODEL
    - COMPUTE_STEADY_STATE_OR_TRANSIENT_MEASURES
    - APPLY_LITTLE_LAW_IF_VALID
    - SIMULATE_IF_REQUIRED
    - RETURN_PERFORMANCE_AND_CAPACITY_INTERPRETATION

  constraints:
    - PRESERVE_ARRIVAL_AND_SERVICE_ASSUMPTIONS
    - DISTINGUISH_QUEUE_LENGTH_FROM_SYSTEM_SIZE
    - DISTINGUISH_WAITING_TIME_FROM_SOJOURN_TIME
    - CHECK_STABILITY_BEFORE_STEADY_STATE_FORMULAS
    - USE_EFFECTIVE_RATE_IN_LITTLE_LAW_WHEN_REQUIRED
    - EXPOSE_QUEUE_DISCIPLINE_AND_CAPACITY
    - PRESERVE_DATA_PROVENANCE

FLOW_HASH:
  canonical_entity: "queueing-theory-ontology-2"
  namespace: "probability-statistics/stochastic-mathematics"
  version: "4.0"
  identity_basis:
    - PAGE_URL
    - CANONICAL_ENTITY
    - ENTITY_TYPE
    - ARRIVAL_PROCESS
    - SERVICE_PROCESS
    - WAITING_SYSTEM_STRUCTURE

END_FLOW