Constraint Satisfaction Problem (CSP)

The set of decision points that must be assigned a value. In manufacturing, these represent the entities to be scheduled or configured.

• Production Orders: A specific job that needs a time slot.
• Machine Assignments: The allocation of a specific tool to an operation.
• Start Times: The temporal slot for a batch process.

Each variable has a defined role, such as Job_01, Machine_A, or Shift_3. The agent's goal is to find a consistent assignment for every variable in the set.

The finite set of possible values that each variable can legally take. Domains define the search space for the autonomous agent.

• Discrete Domains: A specific list of machines capable of performing a task (e.g., {CNC_1, CNC_2, CNC_4}).
• Continuous Domains: A time interval for a start time (e.g., [08:00, 12:00]).
• State Domains: Binary states like {Idle, Busy, Maintenance}.

Domain reduction is a primary strategy for pruning the search space before deep computation begins.

The logical relations that restrict the combinations of values variables can simultaneously take. Constraints encode the physics, logic, and business rules of the factory floor.

• Unary Constraints: Restrict a single variable (e.g., Machine_A ≠ Maintenance).
• Binary Constraints: Relate two variables (e.g., Job_01.EndTime < Job_02.StartTime).
• Global Constraints: Involve multiple variables (e.g., AllDifferent for resource allocation).

Constraints are the hard rules; violating them produces an infeasible schedule.

While a pure CSP seeks any valid assignment, industrial problems usually require finding the best one. This transforms the problem into a Constraint Optimization Problem (COP).

• Makespan Minimization: Completing all jobs as early as possible.
• Cost Minimization: Reducing changeover times or energy consumption.
• Priority Maximization: Ensuring high-value orders are scheduled first.

The objective function guides the search algorithm toward the optimal solution within the feasible region defined by the constraints.

A mapping from variables to values from their respective domains. An assignment can be partial (some variables unassigned) or complete (all variables assigned).

• Consistent Assignment: Does not violate any constraints.
• Inconsistent Assignment: Violates at least one constraint.
• Solution: A complete and consistent assignment.

The search algorithm iteratively extends a partial assignment by selecting an unassigned variable and assigning a value that maintains consistency.

A visual and structural representation of the CSP where nodes represent variables and edges represent binary constraints between them.

• Structure Analysis: The graph's topology determines the complexity of the problem.
• Tree-Structured CSPs: Can be solved in polynomial time.
• Cycle Cutset: Identifying variables whose removal makes the graph a tree.

Analyzing the constraint graph allows the agent to decompose a complex global schedule into loosely coupled subproblems.