Spring Boot + Timefold Solver: Solving Complex Scheduling & Routing with Constraint Optimization

How Timefold Solves Combinatorial Optimization Problems

Timefold Solver (the Apache 2.0 successor to OptaPlanner, package renamed from org.optaplanner to ai.timefold.solver) addresses problems with solution spaces of O(m^n) where brute force is impossible. It sits between rule engines (which only do if-else without global optimization) and MIP/CP-SAT (which lack modeling flexibility and incremental re-solving). Key concepts:

Planning entity : object with undecided fields (e.g., ShiftAssignment)

Planning variable : field the solver assigns (e.g., ShiftAssignment.employee)

Problem fact : immutable input (e.g., Employee, Shift)

Planning solution : the complete solution; its quality measured by a score

Constraint : a scoring function

The solver picks a value for each planning variable from its value range to maximize the total score.

Two-Phase Solving Process

Construction Heuristic (Phase 1)

Quickly builds a feasible initial solution in seconds. Common types: FIRST_FIT_DECREASING: assign most-constrained entities first WEAKEST_FIT / WEAKEST_FIT_DECREASING: balance load when resources are abundant CHEAPEST_INSERTION: typical for routing problems ALLOCATE_ENTITY_FROM_QUEUE: for explicit task-queue semantics

Local Search (Phase 2)

Iteratively tries moves (change one assignment, swap two assignments) and accepts based on strategy: HILL_CLIMBING: reject worsening moves SIMULATED_ANNEALING: accept worsening moves with probability TABU_SEARCH (default, stable): tabu recent moves LATE_ACCEPTANCE (fast convergence): tolerate deterioration within a threshold

Performance hinges on incremental scoring : each move affects only a few constraints; Timefold's constraint-stream nodes propagate changes incrementally, enabling millions of move evaluations in seconds.

Score Types

SimpleScore

HardSoftScore

(most common) HardMediumSoftScore: three-tier priority (e.g., compliance > coverage > preference) BendableScore.of(2,1,3): 2 hard levels, 1 medium, 3 soft HardSoftBigDecimalScore: for monetary/precision-sensitive scores (or scale integers)

Lexicographic comparison: -1hard is always worse than 0hard regardless of soft score.

Domain Modeling

Problem Facts

@Getter @Setter
public class Employee {
    @PlanningId
    private Long id;
    private String name;
    private Set<String> skills = new HashSet<>();
    private String location;
    private int weeklyMaxMinutes;
    private int targetShiftCount;
    private Set<Long> preferredShiftIds = new HashSet<>();
    private Set<String> forbiddenDates = new HashSet<>();
}

@Getter @Setter
public class Shift {
    @PlanningId
    private Long id;
    private LocalDateTime start;
    private LocalDateTime end;
    private Set<String> requiredSkills = new HashSet<>();
    private String location;
    private boolean nightShift;
    public long durationMinutes() { return Duration.between(start, end).toMinutes(); }
    public boolean overlaps(Shift other) { return start.isBefore(other.end) && other.start.isBefore(end); }
    public long gapMinutesTo(Shift other) { ... }
}

Planning Entity

@PlanningEntity
@Getter @Setter
public class ShiftAssignment {
    @PlanningId
    private Long id;
    private Shift shift;
    @PlanningVariable(allowsUnassigned = true)
    private Employee employee;
    @PlanningPin
    private boolean pinned;
}

Key points: allowsUnassigned = true prevents solver crash when no feasible assignment exists (penalize via constraint); @PlanningPin enables incremental re-solving and manual locking; value range provided on employee list; skill matching expressed as constraint (not value-range filter) for explainability; @PlanningId on Employee improves multi-threaded consistency.

Planning Solution

@PlanningSolution
@Getter @Setter
public class EmployeeSchedule {
    @PlanningId
    private Long id;
    @ProblemFactCollectionProperty @ValueRangeProvider
    private List<Employee> employees;
    @ProblemFactCollectionProperty
    private List<Shift> shifts;
    @PlanningEntityCollectionProperty
    private List<ShiftAssignment> assignments;
    @PlanningScore
    private HardSoftScore score;
    @ConstraintWeightOverrides
    private ConstraintWeightOverrides<HardSoftScore> weightOverrides = ConstraintWeightOverrides.none();
}

Constraints: Translating Business Rules into Scores

Implemented via ConstraintProvider using Constraint Streams API. Each constraint has a name that appears in score explanations.

public class ScheduleConstraintProvider implements ConstraintProvider {
    @Override
    public Constraint[] defineConstraints(ConstraintFactory cf) {
        return new Constraint[] {
            // Hard constraints
            unassignedShift(cf),
            requiredSkill(cf),
            overlappingShift(cf),
            minimumRest(cf),
            maxDailyMinutes(cf),
            maxWeeklyMinutes(cf),
            unavailableDate(cf),
            // Soft constraints
            preferredShift(cf),
            balanceShiftCount(cf),
            avoidIsolatedShift(cf),
            consecutiveNightShift(cf)
        };
    }
}

Example Constraints

Unassigned shift (hard):

Constraint unassignedShift(ConstraintFactory cf) {
    return cf.forEach(ShiftAssignment.class)
        .filter(a -> a.getEmployee() == null)
        .penalize(HardSoftScore.ONE_HARD)
        .asConstraint("班次未分配");
}

Skill match (hard):

Constraint requiredSkill(ConstraintFactory cf) {
    return cf.forEach(ShiftAssignment.class)
        .filter(a -> a.getEmployee() != null)
        .filter(a -> !a.getEmployee().getSkills().containsAll(a.getShift().getRequiredSkills()))
        .penalize(HardSoftScore.ONE_HARD)
        .asConstraint("员工技能不满足班次要求");
}

Overlap & rest (hard) using forEachUniquePair with Joiners.equal to avoid Cartesian product:

Constraint overlappingShift(ConstraintFactory cf) {
    return cf.forEachUniquePair(ShiftAssignment.class,
            Joiners.equal(ShiftAssignment::getEmployee))
        .filter((a,b) -> a.getEmployee() != null)
        .filter((a,b) -> a.getShift().overlaps(b.getShift()))
        .penalize(HardSoftScore.ONE_HARD)
        .asConstraint("同一员工班次时间重叠");
}

Constraint minimumRest(ConstraintFactory cf) {
    return cf.forEachUniquePair(ShiftAssignment.class,
            Joiners.equal(ShiftAssignment::getEmployee))
        .filter((a,b) -> a.getEmployee() != null)
        .filter((a,b) -> {
            long gap = a.getShift().gapMinutesTo(b.getShift());
            return gap >= 0 && gap < 11 * 60;
        })
        .penalize(HardSoftScore.ONE_HARD)
        .asConstraint("班次间休息不足 11 小时");
}

Daily hours limit (hard) with groupBy and ConstraintCollectors.sumLong :

Constraint maxDailyMinutes(ConstraintFactory cf) {
    return cf.forEach(ShiftAssignment.class)
        .filter(a -> a.getEmployee() != null)
        .groupBy(ShiftAssignment::getEmployee,
                a -> a.getShift().getStart().toLocalDate(),
                ConstraintCollectors.sumLong(a -> a.getShift().durationMinutes()))
        .filter((emp, date, minutes) -> minutes > 480)
        .penalize(HardSoftScore.ONE_HARD,
                (emp, date, minutes) -> (int)(minutes - 480))
        .asConstraint("单日工时超限");
}

Second penalize argument is a weight function: penalty grows with excess minutes.

Soft constraints (preference & fairness):

Constraint preferredShift(ConstraintFactory cf) {
    return cf.forEach(ShiftAssignment.class)
        .filter(a -> a.getEmployee() != null)
        .filter(a -> a.getEmployee().getPreferredShiftIds().contains(a.getShift().getId()))
        .reward(HardSoftScore.ONE_SOFT)
        .asConstraint("满足员工偏好");
}

Constraint balanceShiftCount(ConstraintFactory cf) {
    return cf.forEach(ShiftAssignment.class)
        .filter(a -> a.getEmployee() != null)
        .groupBy(ShiftAssignment::getEmployee, ConstraintCollectors.count())
        .penalize(HardSoftScore.ONE_SOFT,
                (emp, count) -> Math.max(0, count.intValue() - emp.getTargetShiftCount()) * 2)
        .asConstraint("工作量超出目标");
}

Fairness pitfall: avoid Math.abs(count - target) — its diminishing marginal penalty pushes disparity onto few employees. Penalize only excess (or separately penalize shortfall).

Runtime Weight Overrides

Map<String, HardSoftScore> weights = Map.of(
    "满足员工偏好", HardSoftScore.ofSoft(5),
    "工作量超出目标", HardSoftScore.ofSoft(20)
);
schedule.setWeightOverrides(ConstraintWeightOverrides.of(weights));

Spring Boot Integration

Dependency

<dependency>
    <groupId>ai.timefold.solver</groupId>
    <artifactId>timefold-solver-spring-boot-starter</artifactId>
    <version>${timefold.version}</version>
</dependency>

Configuration ( application.yaml )

timefold:
  solver:
    termination:
      spent-limit: 30s
      unimproved-spent-limit: 10s
    move-thread-count: 4
    environment-mode: REPRODUCIBLE

Service Layer

@Service @RequiredArgsConstructor @Slf4j
public class SchedulingService {
    private final SolverManager<EmployeeSchedule, Long> solverManager;
    private final SolutionManager<EmployeeSchedule, HardSoftScore> solutionManager;
    private final ScheduleRepository scheduleRepository;
    private final AtomicLong jobIdSeq = new AtomicLong();

    public Long submit(EmployeeSchedule problem) {
        Long jobId = jobIdSeq.incrementAndGet();
        solverManager.solveBuilder()
            .withProblemId(jobId)
            .withProblem(problem)
            .withFinalBestSolutionConsumer(solution -> persist(jobId, solution))
            .withExceptionHandler((id, ex) -> log.error("求解任务 {} 异常", id, ex))
            .run();
        return jobId;
    }

    public void terminate(Long jobId) {
        solverManager.terminateEarly(jobId);
    }

    public Optional<EmployeeSchedule> bestSolution(Long jobId) {
        return solverManager.getSolverStatus(jobId) == SolverStatus.NOT_SOLVING
            ? scheduleRepository.findByJobId(jobId)
            : Optional.empty();
    }

    private void persist(Long jobId, EmployeeSchedule solution) {
        HardSoftScore recomputed = solutionManager.update(solution);
        log.info("任务 {} 求解完成，最终评分 {}（复算 {}")", jobId, solution.getScore(), recomputed);
        scheduleRepository.saveSnapshot(jobId, solution, recomputed);
    }
}

solutionManager.update(solution)

recomputes score in non-incremental mode — a critical verification guard; mismatch indicates constraint implementation bugs.

REST Endpoints

@RestController @RequestMapping("/api/scheduling") @RequiredArgsConstructor
public class SchedulingController {
    private final SchedulingService schedulingService;

    @PostMapping("/{planId}/solve")
    public ResponseEntity<Long> solve(@PathVariable Long planId) {
        EmployeeSchedule problem = schedulingService.buildProblem(planId);
        return ResponseEntity.accepted().body(schedulingService.submit(problem));
    }

    @DeleteMapping("/jobs/{jobId}")
    public void cancel(@PathVariable Long jobId) {
        schedulingService.terminate(jobId);
    }

    @GetMapping("/jobs/{jobId}")
    public ResponseEntity<EmployeeSchedule> result(@PathVariable Long jobId) {
        return schedulingService.bestSolution(jobId)
            .map(ResponseEntity::ok)
            .orElse(ResponseEntity.accepted().build());
    }
}

SolverManager

maintains a task queue; parallel-solver-count (default = CPU cores) limits concurrent solves. Same problemId re-submission waits for prior run. Production advice: add tenant-level rate limiting, combine spent-limit (hard timeout) with unimproved-spent-limit (early exit).

Tuning

Construction Heuristic Selection

Same guidelines as earlier: FIRST_FIT_DECREASING general-purpose; WEAKEST_FIT(_DECREASING) for load balancing; CHEAPEST_INSERTION for chained routing; ALLOCATE_ENTITY_FROM_QUEUE for queue semantics.

Local Search & Move Selectors

SolverConfig config = new SolverConfig()
    .withSolutionClass(EmployeeSchedule.class)
    .withEntityClasses(ShiftAssignment.class)
    .withConstraintProviderClass(ScheduleConstraintProvider.class)
    .withPhases(
        new ConstructionHeuristicPhaseConfig()
            .withConstructionHeuristicType(ConstructionHeuristicType.WEAKEST_FIT_DECREASING),
        new LocalSearchPhaseConfig()
            .withLocalSearchType(LocalSearchType.LATE_ACCEPTANCE)
            .withTerminationConfig(
                new TerminationConfig()
                    .withUnimprovedSpentLimit(Duration.ofSeconds(15))));

Move selectors define neighborhood: changeMoveSelector (reassign one), swapMoveSelector (swap two — highest payoff for scheduling). For weekly re-shifts, consider pillar moves (group assignments per employee). Filter pinned = true entities in entitySelector for incremental re-solving.

Concurrency & Reproducibility

move-thread-count: 4

enables parallel local search but breaks reproducibility. For regression tests, set to 1 with environment-mode: REPRODUCIBLE.

Score Type Selection

Pure coverage: HardSoftScore Priority layers (compliance > coverage > preference): HardMediumSoftScore Multiple soft tiers: BendableScore Monetary/precision: HardSoftBigDecimalScore or integer scaling (cents)

Production Engineering Essentials

Three-Layer Validation

SolutionManager.update()

recomputes score independently; compare with solver score.

Independent validator (pure Java, no constraint streams) cross-checks hard constraints.

Business assertions: e.g., "every shift ≥1 person", "no one works >6 consecutive days".

@Component
public class ScheduleValidator {
    public List<String> validate(EmployeeSchedule s) {
        List<String> errors = new ArrayList<>();
        for (ShiftAssignment a : s.getAssignments()) {
            if (a.getEmployee() == null) {
                errors.add("班次未分配: " + a.getShift().getId());
            }
        }
        // other hard constraint checks
        return errors;
    }
}

Manual Adjustments & Incremental Re-solving

Pin manually locked assignments:

assignment.setEmployee(zhangsan);
assignment.setPinned(true);
schedulingService.submit(schedule);

Solver only adjusts unpinned entities.

Incremental re-solving reuses previous solution as starting point:

public EmployeeSchedule buildIncrementalProblem(Long planId, List<Long> changedShiftIds) {
    EmployeeSchedule base = scheduleRepository.loadLatest(planId);
    base.getAssignments().forEach(a -> {
        boolean affected = changedShiftIds.contains(a.getShift().getId());
        a.setPinned(!affected);
    });
    return base;
}

Combine with ConstructionHeuristicType.NO_CONSTRUCTION_HEURISTIC to skip initial construction; local search starts from existing solution, yielding adjusted plan in seconds.

Version Snapshots

Store at least: plan_id, version, score (solver), recomputed_score (independent), solver_config_snapshot, status (DRAFT, PENDING_APPROVAL, APPROVED, PUBLISHED), created_by. New version per solve; approve then publish; rollback/compare anytime.

Case Study: 230-Employee Multi-Store Scheduling

230 employees, 45 stores, 1 month, ~6,900 ShiftAssignment s. Manual scheduling: 8 person-days, 12 hard violations. Timefold 30s: 0 hard violations, preference satisfaction 61% → 84%, workload std dev 3.8 → 1.9. At 120s: preference 89%, std dev 1.5. Business adopted despite modest gains because process became quantifiable, reproducible, auditable.

Six Common Pitfalls

O(n²) Cartesian product : missing Joiners.equal in forEachUniquePair causes 50M pairs for 10k entities. Always join first, then filter.

Too many constraints : each adds a stream node with incremental overhead. Keep ≤20-30; merge similar rules (e.g., multiple hour-limit constraints into one with weight function).

Unsatisfiable hard constraints : solver stalls at -N hard. Use ScoreAnalysis to see per-constraint match counts and scores:

ScoreAnalysis<HardSoftScore> analysis = solutionManager.analyze(solution);
analysis.getConstraintMatchTotalMap().forEach((ref, total) ->
    log.info("约束 {} 命中 {} 次，扣分 {}", ref.constraintName(), total.getConstraintMatchCount(), total.getScore()));

Pre-validate data (e.g., required skill exists) before solving.

Memory pressure : undo logs for each move. Start with -Xmx4g, tune move-thread-count, avoid large objects in planning entities (no whole Schedule references), use NON_REPRODUCIBLE to reduce debug overhead.

Conflicting soft constraints (e.g., preference vs. isolated-shift avoidance) cause oscillation. Widen weight gap (5:1) or demote one to a lower tier in HardMediumSoftScore.

Timezone/DST bugs : store instants in UTC ( Instant or ZonedDateTime), never LocalDateTime for actual time points; convert at presentation layer.

Launch Checklist

Shadow run: algorithm runs in parallel, results shown side-by-side with manual schedules for two weeks.

Keep manual override entry — algorithm is co-pilot, not autopilot.

Pilot one store/team, then expand.

Dashboard: solve time, initial/final score, hard-match counts; sudden score drop signals upstream data issue.

Fallback: on timeout/failure, return last approved version, not error.

Conclusion

Timefold in Spring Boot boils down to modeling, constraints, integration, tuning. But what determines production success is not the solver itself — it's accurate constraint modeling and complete engineering pipelines. Getting 0hard/-137soft is easy; making the business trust, adopt, and stably reproduce the solution is where the value lies. Turning scheduling from guesswork into a quantifiable, reproducible, auditable process is the real payoff.