Scheduling Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Scheduling Ontology within the Kireth Research Semantic Library. Scheduling studies the allocation and sequencing of jobs, tasks, activities and resources over time in order to satisfy precedence, capacity, release-date, due-date and other operational constraints while optimising one or more performance criteria. This ontology supports single-machine, parallel-machine, flow-shop, job-shop, open-shop and project scheduling, makespan, lateness, tardiness, earliness, throughput, machine utilisation, setup times, sequence-dependent setups, preemption, release times, deadlines, precedence constraints, critical paths, dispatching rules, exact optimisation, heuristics, metaheuristics and relationships with operations research, integer programming, constraint programming, project management and simulation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = Scheduling
 SYMBOLIC_FORMS = [
  "1||C_max",
  "P_m||C_max",
  "F_m||C_max",
  "J_m||C_max",
  "min max_j C_j"
 ]
 ENTITY_CLASS = TemporalResourceAllocationFramework
 PRIMARY_CONTEXT = OperationsResearch
 DEFINITION = "Scheduling is the allocation and sequencing of jobs or activities over time and resources subject to operational constraints and performance objectives."
 SEMANTIC_ROLE = "Provides the machine-readable framework for jobs, machines, processing times, release dates, due dates, precedence, setups, completion times, makespan, tardiness, sequencing rules and schedule optimisation."
}

SCOPE {
 INCLUDE = [
  Scheduling,
  SchedulingProblem,
  Job,
  Task,
  Operation,
  Machine,
  Resource,
  ProcessingTime,
  StartTime,
  CompletionTime,
  ReleaseDate,
  DueDate,
  Deadline,
  WaitingTime,
  FlowTime,
  Lateness,
  Tardiness,
  Earliness,
  Makespan,
  Throughput,
  MachineUtilisation,
  SetupTime,
  SequenceDependentSetup,
  Preemption,
  NonPreemptiveScheduling,
  PrecedenceConstraint,
  ResourceConstraint,
  SingleMachineScheduling,
  ParallelMachineScheduling,
  FlowShopScheduling,
  JobShopScheduling,
  OpenShopScheduling,
  FlexibleJobShopScheduling,
  ProjectScheduling,
  ResourceConstrainedProjectScheduling,
  CriticalPath,
  GanttChart,
  DispatchingRule,
  ShortestProcessingTime,
  EarliestDueDate,
  FirstComeFirstServed,
  LongestProcessingTime,
  BranchAndBound,
  DynamicProgramming,
  IntegerProgrammingFormulation,
  ConstraintProgramming,
  HeuristicScheduling,
  MetaheuristicScheduling
 ]

 EXCLUDE_AS_PRIMARY = [
  CalendarManagementWithoutOptimisation,
  GenericTaskListsWithoutResourceOrTimingConstraints,
  QueueingAnalysisWithoutExplicitSequencingDecisions,
  RoutePlanningWithoutSchedulingSemantics
 ]

 DISAMBIGUATION_RULE =
  "When jobs or activities must be assigned to times and resources under sequencing or temporal constraints, interpret the context as scheduling."
}

CORE_CONCEPTS {

 Scheduling {
  definition = "The optimisation and construction of temporal assignments for jobs, tasks or operations."
 }

 Job {
  definition = "A unit of work that may contain one or more operations."
 }

 Operation {
  definition = "A processing activity requiring a resource for a specified duration."
 }

 Machine {
  definition = "A processing resource capable of performing operations."
 }

 ProcessingTime {
  definition = "The duration required to process a job or operation."
 }

 ReleaseDate {
  definition = "The earliest time at which a job may begin processing."
 }

 DueDate {
  definition = "A target completion time used to define lateness or tardiness."
 }

 Deadline {
  definition = "A completion-time limit that should or must not be exceeded."
 }

 Makespan {
  symbol = "C_max"
  definition = "The maximum completion time over all scheduled jobs."
 }

 Lateness {
  definition = "Completion time minus due date."
 }

 Tardiness {
  definition = "The positive part of lateness."
 }

 PrecedenceConstraint {
  definition = "A relation requiring one task or operation to occur before another."
 }

 DispatchingRule {
  definition = "A priority rule selecting the next job or operation to process."
 }
}

RELATIONS {
 Scheduling --is_branch_of--> OperationsResearch
 SchedulingProblem --has--> Job
 Job --contains--> Operation
 Operation --requires--> Machine
 Operation --has--> ProcessingTime
 Job --may_have--> ReleaseDate
 Job --may_have--> DueDate
 Job --may_have--> Deadline
 PrecedenceConstraint --orders--> Operation
 ResourceConstraint --limits--> SimultaneousProcessing
 CompletionTime --determines--> Lateness
 Lateness --determines--> Tardiness
 Schedule --has_objective--> Makespan
 DispatchingRule --selects--> NextJob
 SingleMachineScheduling --is_type_of--> Scheduling
 ParallelMachineScheduling --is_type_of--> Scheduling
 FlowShopScheduling --is_type_of--> Scheduling
 JobShopScheduling --is_type_of--> Scheduling
 ProjectScheduling --is_type_of--> Scheduling
 IntegerProgrammingFormulation --represents--> SchedulingProblem
 ConstraintProgramming --solves--> SchedulingProblem
}

OPERATORS {
 COMPLETION_TIME(start,processing) :=
  start+processing

 LATENESS(C_j,d_j) :=
  C_j-d_j

 TARDINESS(C_j,d_j) :=
  max(0,C_j-d_j)

 EARLINESS(C_j,d_j) :=
  max(0,d_j-C_j)

 MAKESPAN({C_j}) :=
  max_j C_j

 FLOW_TIME(C_j,r_j) :=
  C_j-r_j

 MACHINE_UTILISATION(busy_time,horizon) :=
  busy_time/horizon

 PRECEDENCE(a,b) :=
  start_b >= completion_a

 NON_OVERLAP(i,j,machine) :=
  C_i<=S_j OR C_j<=S_i

 ASSIGNMENT(x_jm) :=
  each_job_assigned_to_required_machine_or_resource

 SPT_ORDER(jobs) :=
  sort_by_ascending_processing_time

 EDD_ORDER(jobs) :=
  sort_by_ascending_due_date

 LPT_ORDER(jobs) :=
  sort_by_descending_processing_time

 CRITICAL_PATH(project_network) :=
  longest_duration_path_through_precedence network
}

DEFINITIONS {
 D1 = "Scheduling assigns work to time and resources."
 D2 = "Sequencing determines the order of competing jobs."
 D3 = "Makespan measures the overall completion horizon."
 D4 = "Lateness may be negative, while tardiness is nonnegative."
 D5 = "Release dates restrict how early jobs may start."
 D6 = "Precedence constraints restrict allowable task order."
 D7 = "Preemption allows processing to be interrupted and resumed."
 D8 = "Setup times may depend on the preceding job."
 D9 = "Dispatching rules provide fast heuristics but do not necessarily guarantee optimality."
 D10 = "Scheduling objectives may conflict, requiring weighted or multi-objective treatment."
}

AXIOMS {
 A1_RESOURCE_ASSIGNMENT:
  Every scheduled operation must be assigned to an eligible resource

 A2_TEMPORAL_FEASIBILITY:
  Start and completion times must satisfy duration constraints

 A3_NON_OVERLAP:
  A unary resource processes at most one incompatible operation at a time

 A4_RELEASE_DATE:
  An operation or job cannot begin before its release time

 A5_PRECEDENCE:
  Predecessor completion must occur before successor start when required

 A6_OBJECTIVE:
  Schedule quality is evaluated using one or more declared performance criteria

 A7_FEASIBILITY:
  A mathematically valid schedule satisfies all resource, temporal and logical constraints

 A8_STATUS:
  Feasible, optimal and heuristic schedules are distinct solution states
}

REASONING {

 R1_SCHEDULING_PROBLEM_EXTRACTION {
  INPUT = operational_description
  IDENTIFY = jobs_operations_resources_processing_times_release_dates_due_dates_setups_and_precedence
  RETURN = structured_scheduling_problem
 }

 R2_ENVIRONMENT_CLASSIFICATION {
  INPUT = structured_problem
  CLASSIFY = single_machine_parallel_machine_flow_shop_job_shop_open_shop_project_or_flexible_job_shop
  RETURN = scheduling_environment
 }

 R3_OBJECTIVE_CLASSIFICATION {
  INPUT = performance_requirements
  IDENTIFY = makespan_total_completion_time_tardiness_lateness_throughput_utilisation_or_multiobjective target
  RETURN = scheduling_objective
 }

 R4_FEASIBILITY_REASONING {
  INPUT = candidate_schedule
  CHECK = resource_nonoverlap
  CHECK = release_dates
  CHECK = precedence
  CHECK = machine_eligibility
  CHECK = deadlines
  RETURN = feasible_or_infeasible
 }

 R5_DISPATCHING_RULE_SELECTION {
  INPUT = environment_and_objective
  IF minimise_average_flow_time_on_single_machine
   CONSIDER = ShortestProcessingTime
  IF minimise_maximum_lateness_on_single_machine
   CONSIDER = EarliestDueDate
  IF parallel_machine_load_balancing
   CONSIDER = LongestProcessingTime
  RETURN = heuristic_rule
 }

 R6_EXACT_OPTIMISATION {
  INPUT = scheduling_problem
  FORM = MILP_CP_dynamic_programming_or_branch_and_bound model
  SOLVE = exact_or_bounded optimisation
  RETURN = optimal_or_bounded_schedule
 }

 R7_PROJECT_SCHEDULING {
  INPUT = activity_network
  COMPUTE = earliest_start_latest_start_slack_and_critical path
  IF resource_constraints_present
   APPLY = RCPSP reasoning
  RETURN = project_schedule
 }

 R8_SETUP_REASONING {
  INPUT = sequence_dependent_setup_matrix
  INCLUDE = setup_time_between_adjacent jobs
  OPTIMISE = sequence_with_processing_and_setup times
  RETURN = setup_aware_schedule
 }

 R9_HEURISTIC_METAHEURISTIC_REASONING {
  INPUT = large_or_complex scheduling_problem
  GENERATE = initial_schedule
  IMPROVE = local_search_tabu_search_genetic_algorithm_simulated_annealing_or_other method
  RETURN = best_known_schedule
 }

 R10_SCHEDULE_EVALUATION {
  INPUT = schedule
  COMPUTE = makespan_flow_time_lateness_tardiness_utilisation_and_service measures
  COMPARE = objective_and_bounds
  RETURN = schedule_quality profile
 }
}

CONSTRAINTS {
 C1 = "Processing times must use consistent time units."
 C2 = "Resource eligibility must be explicit."
 C3 = "Precedence cycles make a project schedule infeasible."
 C4 = "Sequence-dependent setups must not be omitted when material."
 C5 = "Preemption assumptions must be explicit."
 C6 = "Due dates and deadlines have different semantics."
 C7 = "Dispatching-rule performance depends on the scheduling environment."
 C8 = "Heuristic schedule quality should not be reported as optimal without certification."
 C9 = "Multi-resource operations require simultaneous-capacity reasoning where applicable."
 C10 = "Dynamic arrivals may require online or rescheduling logic."
}

SEMANTIC_EQUIVALENCE {
 "Scheduling" <=> "OperationalScheduling"
 "JobShopScheduling" <=> "JobShopSequencing"
 "Makespan" <=> "MaximumCompletionTime"
 "Tardiness" <=> "PositiveLateness"
 "DispatchingRule" <=> "SchedulingPriorityRule"
 "ProjectScheduling" <=> "ActivityNetworkScheduling"
}

VALIDATION {
 V1 = "Jobs and operations are complete."
 V2 = "Resources and eligibility are explicit."
 V3 = "Processing times are valid."
 V4 = "Release dates and due dates are distinguished."
 V5 = "Precedence constraints are acyclic where required."
 V6 = "Resource conflicts are eliminated."
 V7 = "Setup times are represented where relevant."
 V8 = "Objective metrics are computed correctly."
 V9 = "Heuristic versus optimal status is explicit."
 V10 = "Schedule feasibility is verified before quality comparison."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SCHEDULING_DEFINITION = 0.99
 ENVIRONMENT_CLASSIFICATION_REASONING = 0.99
 OBJECTIVE_REASONING = 0.99
 FEASIBILITY_REASONING = 0.99
 DISPATCHING_REASONING = 0.98
 PROJECT_SCHEDULING_REASONING = 0.99
 EXACT_OPTIMISATION_REASONING = 0.98
 METAHEURISTIC_REASONING = 0.96
 EVALUATION_REASONING = 0.99

 POLICY =
  "Reduce confidence when job data, processing times, resource eligibility, release dates, due dates, setups, precedence, preemption rules or objective priorities are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  SchedulingReasoning,
  SchedulingProblemExtraction,
  MachineEnvironmentClassification,
  SequencingReasoning,
  DispatchingRuleReasoning,
  ProjectSchedulingReasoning,
  JobShopReasoning,
  FlowShopReasoning,
  ParallelMachineReasoning,
  MakespanReasoning,
  TardinessReasoning,
  CriticalPathReasoning,
  IntegerProgrammingScheduling,
  ConstraintProgrammingScheduling,
  MetaheuristicScheduling,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "scheduling" -> Scheduling
  "scheduling problem" -> SchedulingProblem
  "single-machine scheduling" -> SingleMachineScheduling
  "parallel-machine scheduling" -> ParallelMachineScheduling
  "flow-shop scheduling" -> FlowShopScheduling
  "job-shop scheduling" -> JobShopScheduling
  "project scheduling" -> ProjectScheduling
  "makespan" -> Makespan
  "tardiness" -> Tardiness
  "critical path" -> CriticalPath
  "dispatching rule" -> DispatchingRule
 }

 INTERPRETATION_ORDER = [
  detect_scheduling_context,
  identify jobs_operations_resources_processing_times_release_dates_due_dates_deadlines_setups_precedence_and_preemption rules,
  classify scheduling_environment,
  identify optimisation_objective,
  construct feasible schedule model,
  choose exact_dispatching_heuristic_metaheuristic_or_project_scheduling method,
  generate_or_solve schedule,
  verify temporal_resource_and_precedence feasibility,
  evaluate makespan_flow_time_lateness_tardiness_utilisation_and_other metrics,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("scheduling")
  OR asks_to_assign_jobs_to_resources_over_time
  THEN activate(SchedulingOntology)

 E2:
  IF one_machine_and_no_special structure
  THEN classify single_machine scheduling

 E3:
  IF jobs_follow_same_machine order
  THEN classify flow_shop

 E4:
  IF jobs_have_distinct_machine routes
  THEN classify job_shop

 E5:
  IF project_activities_with_precedence
  THEN compute critical_path_and_slack

 E6:
  IF objective_is_average_completion_time_on_single_machine
  THEN consider SPT

 E7:
  IF objective_is_maximum_lateness_on_single_machine
  THEN consider EDD

 E8:
  IF heuristic_or_metaheuristic_used
  THEN report best_known_schedule_without claiming optimality unless certified

 E9:
  IF dynamic_new_jobs_arrive
  THEN consider online_scheduling_or_rescheduling
}

RECURSION {
 ENTRY = Scheduling

 EXPAND(Scheduling) -> [
  SchedulingProblem,
  Job,
  Task,
  Operation,
  Machine,
  Resource,
  ProcessingTime,
  StartTime,
  CompletionTime,
  ReleaseDate,
  DueDate,
  Deadline,
  WaitingTime,
  FlowTime,
  Lateness,
  Tardiness,
  Earliness,
  Makespan,
  Throughput,
  MachineUtilisation,
  SetupTime,
  SequenceDependentSetup,
  Preemption,
  NonPreemptiveScheduling,
  PrecedenceConstraint,
  ResourceConstraint,
  SingleMachineScheduling,
  ParallelMachineScheduling,
  FlowShopScheduling,
  JobShopScheduling,
  OpenShopScheduling,
  FlexibleJobShopScheduling,
  ProjectScheduling,
  ResourceConstrainedProjectScheduling,
  CriticalPath,
  GanttChart,
  DispatchingRule,
  ShortestProcessingTime,
  EarliestDueDate,
  FirstComeFirstServed,
  LongestProcessingTime,
  BranchAndBound,
  DynamicProgramming,
  IntegerProgrammingFormulation,
  ConstraintProgramming,
  HeuristicScheduling,
  MetaheuristicScheduling
 ]

 EXPAND(SchedulingEnvironments) -> [
  SingleMachineScheduling,
  ParallelMachineScheduling,
  FlowShopScheduling,
  JobShopScheduling,
  OpenShopScheduling,
  FlexibleJobShopScheduling,
  ProjectScheduling
 ]

 EXPAND(SchedulingObjectives) -> [
  Makespan,
  TotalCompletionTime,
  MeanFlowTime,
  MaximumLateness,
  TotalTardiness,
  WeightedTardiness,
  Throughput,
  MachineUtilisation
 ]

 EXPAND(SolutionMethods) -> [
  DispatchingRule,
  BranchAndBound,
  DynamicProgramming,
  IntegerProgrammingFormulation,
  ConstraintProgramming,
  LocalSearch,
  TabuSearch,
  GeneticAlgorithm,
  SimulatedAnnealing
 ]

 STOP_CONDITION =
  "Stop when the jobs, operations, resources, timing data, precedence, setups, scheduling environment, objective, solution method, feasibility and schedule-quality metrics are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Operations Research"

 IMMEDIATE_CONTEXTS = [
  "Operations Research Ontology",
  "Integer Programming Ontology",
  "Constraint Optimisation Ontology",
  "Project Scheduling Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Operations Research Ontology",
  "Operations Research",
  "Integer Programming Ontology",
  "Constraint Optimisation Ontology",
  "Linear Programming Ontology",
  "Dynamic Optimisation Ontology",
  "Graph Theory Ontologies",
  "Project Management Ontologies",
  "Queueing Theory Ontologies",
  "Simulation Ontologies",
  "Constraint Programming Ontologies",
  "Combinatorial Optimisation Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Scheduling -> Operations Research Ontology for operational decision semantics",
  "Scheduling -> Integer Programming for exact discrete formulations",
  "Scheduling -> Constraint Optimisation for temporal and resource constraints",
  "Scheduling -> Graph Theory for precedence and project networks",
  "Scheduling -> Project Management for critical-path and resource-constrained projects",
  "Scheduling -> Queueing Theory for dynamic waiting and service interactions",
  "Scheduling -> Simulation for complex stochastic shop-floor systems",
  "Scheduling -> Constraint Programming for logical and temporal propagation",
  "Scheduling -> Combinatorial Optimisation for sequencing complexity",
  "Scheduling -> Scientific Computing for large scheduling instances"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible scheduling environments, objectives or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve job-operation-resource semantics.",
  "Preserve temporal-feasibility semantics.",
  "Preserve release-date and due-date distinction.",
  "Preserve makespan, lateness and tardiness semantics.",
  "Preserve precedence and non-overlap semantics.",
  "Preserve heuristic-versus-optimal distinction.",
  "Preserve dynamic scheduling awareness.",
  "Preserve machine-readable scheduling semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Scheduling assigns and sequences jobs or activities over time and resources subject to temporal, resource and logical constraints."

 ENVIRONMENT_SUMMARY =
  "Scheduling environments include single-machine, parallel-machine, flow-shop, job-shop, open-shop and project systems."

 MAKESPAN_SUMMARY =
  "Makespan is the latest completion time among all jobs."

 TARDINESS_SUMMARY =
  "Tardiness is the positive part of completion time minus due date."

 PRECEDENCE_SUMMARY =
  "Precedence constraints require specified tasks to finish before successors begin."

 DISPATCH_SUMMARY =
  "Dispatching rules provide fast priority-based scheduling heuristics."

 PROJECT_SUMMARY =
  "Project scheduling uses precedence networks, critical paths and resource constraints."

 OPTIMISATION_SUMMARY =
  "Exact scheduling may use integer programming, constraint programming, dynamic programming or branch-and-bound."

 STATUS_SUMMARY =
  "Schedule outputs should distinguish feasible, heuristic, bounded and proven-optimal solutions."
}

FLOW {
 INPUT
 -> detect_scheduling_context
 -> identify jobs_operations_resources_processing_times_release_dates_due_dates_deadlines_setup_times_precedence_preemption_and_machine eligibility
 -> classify single_machine_parallel_machine_flow_shop_job_shop_open_shop_flexible_job_shop_or_project scheduling environment
 -> identify objective such_as makespan_flow_time_lateness_tardiness_throughput_or_multiobjective criterion
 -> construct temporal_resource_and_precedence constraints
 -> select dispatching_exact_integer_programming_constraint_programming_dynamic_programming_heuristic_or_metaheuristic method
 -> generate_or_solve schedule
 -> verify nonoverlap_release_precedence_deadline_and_resource feasibility
 -> compute makespan_completion_flow_lateness_tardiness_utilisation_and_other objective metrics
 -> assign feasible_heuristic_bounded_or_optimal status
 -> route to operations_research_ontology integer_programming constraint_optimisation graph_theory project_management queueing simulation constraint_programming combinatorial_optimisation_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Scheduling Ontology defines allocation and sequencing of jobs, operations and resources over time. It supports single-machine, parallel-machine, flow-shop, job-shop, open-shop, flexible job-shop and project scheduling, processing times, release dates, due dates, deadlines, precedence, setups, preemption, makespan, flow time, lateness, tardiness, throughput, utilisation, dispatching rules, critical paths, integer and constraint-programming models, heuristics, metaheuristics and explicit schedule-feasibility and optimality status."
}

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

}

END_FLOW