More Automaton Fun

2026-05-30 · Source: Blog on Activimetrics LLC · Field: Technology & Digital — Software Development & Engineering, Artificial Intelligence & Machine Learning · Depth: Intermediate, long

Summary

This article details the implementation of a "two days off in a row every seven days" constraint using a Deterministic Finite Automaton (DFA) within a scheduling system. The author initially attempted to modify an existing DFA for "one off shift after at most three days of work," but faced issues with conflicting transitions. The successful approach involved designing a new DFA with a dedicated "Two Day Off" node, allowing the solver to determine placement. This DFA was translated into Python code for OR-Tools. Initial tests combining this new constraint with other existing rules resulted in "No solution!" (0 solutions, 31276 conflicts, 4.73s WallTime). By isolating the new constraint, solutions were found (2 solutions, 0.109s WallTime). The conflict was resolved by increasing nurses to 8 and relaxing "exactly" off-duty shift constraints, yielding 2 solutions in 0.274s. This demonstrates the ability of OR-Tools to combine independent DFA constraints.

Key takeaway

Operations researchers or software engineers designing complex scheduling systems should note that Deterministic Finite Automata (DFAs) are robust for encoding intricate temporal constraints, like ensuring consecutive days off. You should consider implementing individual scheduling rules as separate DFAs and integrating them with constraint solvers like OR-Tools. Be prepared to diagnose and resolve conflicts by adjusting resource availability or relaxing other "exactly" constraints to achieve feasible solutions.

Key insights

Deterministic Finite Automata effectively model complex temporal constraints for scheduling problems.

Principles

• DFAs can track state for complex scheduling rules.
• Constraint conflicts require resource or rule adjustments.
• Independent DFAs combine well in constraint solvers.

Method

Design a DFA with specific nodes for consecutive off-days, then translate states and transitions into a Python dictionary for integration with a constraint solver like OR-Tools.

In practice

• Model "two days off in a row" with a DFA.
• Use OR-Tools for combining DFA-based constraints.
• Adjust resource counts to resolve constraint conflicts.

Topics

• Deterministic Finite Automata
• Constraint Programming
• Shift Scheduling
• OR-Tools
• Constraint Satisfaction
• Scheduling Algorithms

Best for: AI Engineer, Software Engineer, Research Scientist

Related on AIssential

• Automatons in CP-SAT for Rostering — DFAs can model complex scheduling rules for CP-SAT solvers, enabling robust constraint enforcement.
• Clock problem — A clock puzzle can be precisely solved using mathematical programming, addressing modular arithmetic and variable assignment.
• SDOF: Taming the Alignment Tax in Multi-Agent Orchestration with State-Constrained Dispatch — SDOF enforces business process constraints in multi-agent LLM workflows using a state machine and two defensive layers.
• LLM-Evolved Pattern Generators for Optimal Classical Planning — LLM-driven program synthesis generates admissible, domain-dependent heuristics for optimal classical planning, preserving A* search optimality.
• Hacking with the Automaton Constraint — Decomposing complex DFA constraints into layered, simpler automata simplifies implementation and debugging.
• Petri Net Induced Heuristic Search for Resource Constrained Scheduling — RCPSP can be optimally solved via A* search on a TTPNR reachability graph using consistent combined heuristics.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Blog on Activimetrics LLC.