Two Scheduling Examples

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

Summary

An analysis of two OR-Tools Python examples for bus driver scheduling, "bus_driver_scheduling_flow_sat.py" and "bus_driver_scheduling_sat.py", reveals significant performance differences and implementation details. The "flow_sat" example proved infeasible for a 50-shift instance and became stuck on 200 and 1356-shift problems. In contrast, "bus_driver_scheduling_sat.py" completed "tiny" instances in 1.8s and "small" instances in 28s, though it failed on "medium" and "large" problems. This "sat" approach employs a two-pass optimization, initially minimizing the number of drivers, then optimizing total working time. It constructs a detailed network for each driver, tracking "total_driving" and "no_break_driving" variables to enforce constraints like "max_driving_time" (540 minutes) and "min_pause_after_4h" (30 minutes), crucial for managing mandatory breaks. The author suggests the examples might be outdated given recent OR-Tools improvements.

Key takeaway

For software engineers or ML engineers designing complex scheduling solutions, recognize that simple interval-based constraints are insufficient for problems requiring cumulative state tracking, such as mandatory breaks after specific driving durations. You should prioritize explicit network modeling within your solver, using variables like "total_driving" and "no_break_driving" to maintain state across sequential tasks. Be aware that OR-Tools examples, while illustrative, may contain older code that doesn't fully leverage recent solver improvements, potentially impacting performance on larger instances.

Key insights

Explicitly modeling shift order and cumulative state within a solver's network is crucial for complex temporal scheduling constraints like mandatory breaks.

Principles

• Complex temporal constraints necessitate network-based state tracking within the solver.
• Symmetry breaking and redundant constraints can significantly enhance solver performance.
• Two-pass optimization can first determine minimum resources, then optimize their usage.

Method

A two-pass optimization approach first minimizes the number of required drivers, then, with that fixed number, minimizes total delay between tasks or working times.

In practice

• Use "IntVar" to track cumulative state like "total_driving" and "no_break_driving".
• Employ "only_enforce_if" for conditional constraint enforcement based on literal truth.
• Introduce "~working" literals to represent unused resources and simplify driver minimization.

Topics

• OR-Tools
• CP-SAT Solver
• Constraint Programming
• Bus Driver Scheduling
• Scheduling Optimization
• Symmetry Breaking

Code references

• google/or-tools

Best for: Machine Learning Engineer, Software Engineer, AI Student

Related on AIssential

• More Automaton Fun — Deterministic Finite Automata effectively model complex temporal constraints for scheduling problems.
• Towards Efficient Constraint Handling in Neural Solvers for Routing Problems — CaR efficiently handles complex VRP constraints by jointly training construction and lightweight refinement modules with shared representations.
• 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.
• Clock problem — A clock puzzle can be precisely solved using mathematical programming, addressing modular arithmetic and variable assignment.
• GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization — GOAL is a graph-based diffusion solver for dynamic multi-objective optimization, achieving high feasibility and speed.
• Optimizing Earth Observation Satellite Schedules under Unknown Operational Constraints: An Active Constraint Acquisition Approach — Optimizing satellite schedules with unknown constraints requires interactive learning from a binary oracle.

Open in AIssential →

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