基于Timefold处理模板班次重复调度的约束优化问题

我现有MasterSchedule、LiveSchedule、TemplateShift、Shift和Employee这几个领域模型，但当前Timefold代码仅用到Shift和Employee，规划变量为员工与班次的分配。MasterSchedule与TemplateShift支持用户修改未来规划班次并设置生效日期，最终会将MasterSchedule同步至LiveSchedule。

TemplateShift无具体日期，仅存储周期周数、周期内的星期几、起止时间，生成Shift时会基于当前周转换为具体日期（比如第1周第2天对应当前周周二），班次也支持跨天（例如周一20:00至周二6:00）。

我需要同时优化TemplateSchedule与LiveSchedule，希望通过模板生成Shift传入Timefold简化处理，但遇到模板班次的跨周期冲突问题：比如1周周期的MasterSchedule中，第1天1:00-5:00的模板班次与第7天22:00-3:00的班次可能冲突（后者跨到第8天，即下一周的第1天），需要将第8天视为第1天来校验约束并惩罚冲突，求最优解决方案。

现有领域模型代码 #

@PlanningEntity
public class Shift {
  @PlanningId
  Long id;

  Location location;
  LocalDateTime start;
  LocalDateTime end;
  boolean locked;

  @PlanningVariable(nullable = true)
  Employee employee;

  @PlanningPin
  public boolean isLocked() {
    return locked;
  }
}


public class Employee {
  @PlanningId
  Long id;
  String name;
  double rate;
}

核心思路 #

将TemplateShift的周期特性转化为Timefold可处理的循环时间窗口，通过计算班次在周期内的相对时间区间，在约束规则中处理跨周期的冲突逻辑；同时保留模板转实体的生成逻辑，兼顾TemplateSchedule和LiveSchedule的优化需求。

步骤1：扩展TemplateShift模型，增加周期与相对时间计算 #

给TemplateShift补充周期属性，并实现相对时间、实际时间的转换方法，方便后续约束校验与Shift生成：

public class TemplateShift {
    @PlanningId
    Long id;
    Integer cycleWeeks; // 周期周数，默认1表示每周重复
    Integer dayOfCycle; // 周期内的第几天（1=周一，7=周日）
    LocalTime startTime;
    LocalTime endTime;
    boolean locked;
    Location location;

    // 计算模板班次在指定周期偏移下的实际开始时间
    public LocalDateTime getStartDateTime(LocalDate baseDate, int cycleOffset) {
        // 以周一为周期起始基准
        LocalDate cycleBase = baseDate.with(TemporalAdjusters.previousOrSame(DayOfWeek.MONDAY));
        LocalDate shiftDate = cycleBase.plusDays(dayOfCycle - 1).plusWeeks(cycleOffset);
        return LocalDateTime.of(shiftDate, startTime);
    }

    // 计算模板班次在指定周期偏移下的实际结束时间，自动处理跨天
    public LocalDateTime getEndDateTime(LocalDate baseDate, int cycleOffset) {
        LocalDate cycleBase = baseDate.with(TemporalAdjusters.previousOrSame(DayOfWeek.MONDAY));
        LocalDate shiftDate = cycleBase.plusDays(dayOfCycle - 1).plusWeeks(cycleOffset);
        LocalDateTime end = LocalDateTime.of(shiftDate, endTime);
        // 若结束时间早于开始时间，说明跨天，自动加1天
        if (end.isBefore(getStartDateTime(baseDate, cycleOffset))) {
            end = end.plusDays(1);
        }
        return end;
    }

    // 获取班次在周期内的相对起始分钟数（从周期第一天0点开始计算）
    public int getRelativeStartMinutes() {
        return (dayOfCycle - 1) * 24 * 60 + startTime.getHour() * 60 + startTime.getMinute();
    }

    // 获取班次在周期内的相对结束分钟数，跨天则追加一天的分钟数
    public int getRelativeEndMinutes() {
        int baseMinutes = (dayOfCycle - 1) * 24 * 60 + endTime.getHour() * 60 + endTime.getMinute();
        if (endTime.isBefore(startTime)) {
            baseMinutes += 24 * 60;
        }
        return baseMinutes;
    }
}

步骤2：实现跨周期冲突的约束规则 #

在Timefold约束流中，基于TemplateShift的相对时间区间，校验同周期内的班次冲突（包括跨周期的重叠情况）：

public class TemplateShiftConstraints {
    private static final int MINUTES_PER_WEEK = 7 * 24 * 60;

    public Constraint overlappingTemplateShifts(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(TemplateShift.class)
                .join(TemplateShift.class,
                        Joiners.equal(TemplateShift::getCycleWeeks), // 仅校验同周期的班次
                        Joiners.lessThan(TemplateShift::getPlanningId), // 避免重复校验同一对班次
                        Joiners.filtering(this::isOverlappingInCycle))
                .penalize("跨周期重叠模板班次", HardSoftScore.ONE_HARD)
                .asConstraint();
    }

    // 判断两个模板班次在周期内是否重叠（含跨周期情况）
    private boolean isOverlappingInCycle(TemplateShift s1, TemplateShift s2) {
        int cycleTotalMinutes = s1.getCycleWeeks() * MINUTES_PER_WEEK;
        int s1Start = s1.getRelativeStartMinutes();
        int s1End = s1.getRelativeEndMinutes();
        int s2Start = s2.getRelativeStartMinutes();
        int s2End = s2.getRelativeEndMinutes();

        boolean s1Wraps = s1End > cycleTotalMinutes;
        boolean s2Wraps = s2End > cycleTotalMinutes;

        if (s1Wraps || s2Wraps) {
            // 跨周期班次拆分为两个区间：[start, 周期结束] 和 [0, 溢出部分]，分别校验重叠
            return (isIntervalOverlap(s1Start, cycleTotalMinutes, s2Start, s2End) ||
                    isIntervalOverlap(0, s1End - cycleTotalMinutes, s2Start, s2End)) ||
                    (isIntervalOverlap(s2Start, cycleTotalMinutes, s1Start, s1End) ||
                    isIntervalOverlap(0, s2End - cycleTotalMinutes, s1Start, s1End));
        } else {
            // 普通区间重叠校验
            return isIntervalOverlap(s1Start, s1End, s2Start, s2End);
        }
    }

    // 基础区间重叠判断逻辑
    private boolean isIntervalOverlap(int aStart, int aEnd, int bStart, int bEnd) {
        return aStart < bEnd && bStart < aEnd;
    }
}

步骤3：TemplateShift到Shift的生成逻辑 #

当优化LiveSchedule时，根据模板生成指定时间范围内的Shift实例，传入Timefold进行员工分配：

public class ShiftGenerator {
    public List<Shift> generateShiftsFromTemplate(List<TemplateShift> templateShifts, LocalDate startDate, int weeksToGenerate) {
        List<Shift> shifts = new ArrayList<>();
        for (TemplateShift template : templateShifts) {
            for (int offset = 0; offset < weeksToGenerate; offset++) {
                LocalDateTime shiftStart = template.getStartDateTime(startDate, offset);
                LocalDateTime shiftEnd = template.getEndDateTime(startDate, offset);
                Shift shift = new Shift();
                shift.setId(template.getId() * 1000 + offset); // 生成唯一Shift ID
                shift.setLocation(template.getLocation());
                shift.setStart(shiftStart);
                shift.setEnd(shiftEnd);
                shift.setLocked(template.isLocked());
                shifts.add(shift);
            }
        }
        return shifts;
    }
}

步骤4：双Schedule优化策略 #

• TemplateSchedule优化：直接将TemplateShift作为规划实体，规划变量可设为Employee（提前绑定固定员工到模板）或调整班次的相对时间（允许修改模板时间），用上述跨周期约束处理冲突。
• LiveSchedule优化：用ShiftGenerator生成未来N周的Shift实例，结合原有员工分配逻辑，通过@PlanningPin注解保留Locked班次的固定分配。

内容的提问来源于stack exchange，提问作者kurupt_89