OptaPlanner求解员工作业调度问题时如何添加业务约束

AI 小北

2026-8-27

OptaPlanner员工作业调度实现方案

现有建模问题

当前代码无法实现工时约束的核心原因是建模存在3个硬伤：

只给作业绑定了所属员工，没有规划作业执行顺序。跨作业通行时长完全由先后顺序决定，当前Employee类中通过反向影子变量拿到的jobs列表没有固定顺序，根本算不出准确的总通行时间。这类带点位移动的作业调度本质是带容量约束的车辆路径问题，作业顺序必须纳入规划范围。
字段名不匹配：约束代码里调用的是employee.getApplications()，但Employee类里的承接作业字段实际叫jobs，运行会直接抛方法不存在错误。
成本矩阵缺段：当前Cost仅存储作业点之间的通行时长，没有计算员工从固定出发地（公司/常驻点）到第一个作业点的时间，总工时计算会比实际值偏小。

修正后的领域模型

直接用OptaPlanner原生支持的链式规划变量建模，天然维护作业顺序，性能远好于单独给作业加顺序字段的方案：

先定义路径节点公共接口，员工和作业都实现这个接口，代表可以作为路径上的停留点：

public interface Standstill {
    Coordinate getCoordinate();
    Job getNextJob();
    Long getLocationId(); // 给每个点位加唯一ID，方便查通行时间缓存
}

修正Employee类，补全必要字段，作为链式路径的锚点：

@Data
@NoArgsConstructor
@AllArgsConstructor
@PlanningEntity
public class Employee implements Standstill {

    @PlanningId
    private Long id;

    private Coordinate departureCoordinate;

    // 额定工作时长，默认540分钟
    private Integer maxWorkingMinutes = 540;
    // 承接作业数上下限，默认5-10
    private Integer minJobCount = 5;
    private Integer maxJobCount = 10;

    // 链式结构中只需要存路径上的第一个作业，全量作业列表可以通过nextJob递归遍历得到
    @InverseRelationShadowVariable(sourceVariableName = "previousStandstill")
    private Job nextJob;

    @Override
    public Long getLocationId() {
        // 员工点位ID加前缀避免和作业ID重复
        return Long.parseLong("E" + id);
    }

    @Override
    public Coordinate getCoordinate() {
        return departureCoordinate;
    }
}

修正Job类，改用链式规划变量，加到达时间影子变量缓存累计耗时，避免约束计算时重复遍历路径：

@Data
@NoArgsConstructor
@PlanningEntity
public class Job implements Standstill {

    @PlanningId
    private Long id;

    // 链式规划变量：指向上一个停留节点，可能是员工（路径起点）或其他作业
    @PlanningVariable(valueRangeProviderRefs = {"employeeRange", "jobRange"}, graphType = PlanningVariableGraphType.CHAINED)
    private Standstill previousStandstill;

    @InverseRelationShadowVariable(sourceVariableName = "previousStandstill")
    private Job nextJob;

    private Coordinate coordinate;
    // 单作业固定处理时长30分钟
    private final Integer processTime = 30;

    // 影子变量：缓存到达当前作业点的时间，由自定义变量监听器自动更新
    @ShadowVariable(variableListenerClass = ArrivalTimeUpdatingVariableListener.class, sourceVariableName = "previousStandstill")
    private Long arrivalTime;

    @Override
    public Long getLocationId() {
        return id;
    }
}

实现时间更新变量监听器，当前序节点变化时自动级联更新后续所有作业的到达时间：

public class ArrivalTimeUpdatingVariableListener implements VariableListener<Plan, Job> {

    @Override
    public void afterEntityAdded(ScoreDirector<Plan> scoreDirector, Job job) {
        updateArrivalTime(scoreDirector, job);
    }

    @Override
    public void afterVariableChanged(ScoreDirector<Plan> scoreDirector, Job job) {
        updateArrivalTime(scoreDirector, job);
    }

    // 其余生命周期方法空实现即可
    @Override public void beforeEntityAdded(ScoreDirector<Plan> scoreDirector, Job job) {}
    @Override public void beforeEntityRemoved(ScoreDirector<Plan> scoreDirector, Job job) {}
    @Override public void afterEntityRemoved(ScoreDirector<Plan> scoreDirector, Job job) {}

    private void updateArrivalTime(ScoreDirector<Plan> scoreDirector, Job job) {
        Standstill previous = job.getPreviousStandstill();
        Long newArrivalTime = null;
        if (previous != null) {
            Long travelTime = getTravelTime(previous.getLocationId(), job.getLocationId(), scoreDirector.getWorkingSolution());
            if (previous instanceof Employee) {
                // 前序是员工起点，到达时间即为从驻地到当前作业的通行时间
                newArrivalTime = travelTime;
            } else if (previous instanceof Job prevJob && prevJob.getArrivalTime() != null) {
                // 前序是其他作业，到达时间=前序作业到达时间+前序作业处理时长+两点通行时间
                newArrivalTime = prevJob.getArrivalTime() + prevJob.getProcessTime() + travelTime;
            }
        }
        // 时间无变化时不更新，避免无效触发分数计算
        if (!Objects.equals(job.getArrivalTime(), newArrivalTime)) {
            scoreDirector.beforeVariableChanged(job, "arrivalTime");
            job.setArrivalTime(newArrivalTime);
            scoreDirector.afterVariableChanged(job, "arrivalTime");
            // 级联更新后续作业的到达时间
            if (job.getNextJob() != null) {
                updateArrivalTime(scoreDirector, job.getNextJob());
            }
        }
    }

    // 从预构建的成本矩阵中查询两点通行时间
    private Long getTravelTime(Long fromId, Long toId, Plan solution) {
        // 提前把GraphHopper计算的所有点位（含员工出发地）的通行时间转成双层Map缓存，key为fromId、toId，直接取值即可
        return solution.getTravelTimeCache().get(fromId).get(toId);
    }
}

修正Plan类，补全必要的问题事实和值范围：

@Data
@NoArgsConstructor
@PlanningSolution
public class Plan {

    @ProblemFactCollectionProperty
    @ValueRangeProvider(id = "employeeRange")
    private List<Employee> employees;

    @PlanningEntityCollectionProperty
    @ValueRangeProvider(id = "jobRange")
    private List<Job> jobs;

    // 预构建的通行时间缓存，结构为Map<fromLocationId, Map<toLocationId, travelTimeMinutes>>
    @ProblemFactProperty
    private Map<Long, Map<Long, Long>> travelTimeCache;

    @PlanningScore
    private HardSoftScore score;

}

约束实现

修正原有作业数量约束，新增工时超限硬约束：

public class CustomConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                minJobCountConflict(constraintFactory),
                maxJobCountConflict(constraintFactory),
                workingTimeOverLimit(constraintFactory)
        };
    }

    private Constraint minJobCountConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Employee.class)
                .filter(employee -> countJobs(employee) < employee.getMinJobCount())
                .penalize("作业数低于下限", HardSoftScore.ONE_HARD,
                        employee -> employee.getMinJobCount() - countJobs(employee));
    }

    private Constraint maxJobCountConflict(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Employee.class)
                .filter(employee -> countJobs(employee) > employee.getMaxJobCount())
                .penalize("作业数超过上限", HardSoftScore.ONE_HARD,
                        employee -> countJobs(employee) - employee.getMaxJobCount());
    }

    private Constraint workingTimeOverLimit(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Employee.class)
                .filter(employee -> {
                    Job lastJob = getLastJob(employee);
                    if (lastJob == null || lastJob.getArrivalTime() == null) {
                        return false;
                    }
                    // 总工时=最后一个作业的到达时间+最后一个作业的处理时长
                    long totalTime = lastJob.getArrivalTime() + lastJob.getProcessTime();
                    return totalTime > employee.getMaxWorkingMinutes();
                })
                .penalize("工时超限", HardSoftScore.ONE_HARD, employee -> {
                    Job lastJob = getLastJob(employee);
                    long totalTime = lastJob.getArrivalTime() + lastJob.getProcessTime();
                    return (int) (totalTime - employee.getMaxWorkingMinutes());
                });
    }

    // 遍历链式结构统计员工承接的总作业数
    private int countJobs(Employee employee) {
        int count = 0;
        Job current = employee.getNextJob();
        while (current != null) {
            count++;
            current = current.getNextJob();
        }
        return count;
    }

    // 找到员工路径上的最后一个作业
    private Job getLastJob(Employee employee) {
        Job current = employee.getNextJob();
        if (current == null) {
            return null;
        }
        while (current.getNextJob() != null) {
            current = current.getNextJob();
        }
        return current;
    }
}

注意事项

构建通行时间缓存时，要把所有员工的出发地点位也加入计算，否则无法查询员工到第一个作业点的通行时间。
如果业务要求员工完成所有作业后需要返回出发地，总工时计算要额外加上最后一个作业返回员工出发地的通行时间。
后续可以根据业务需求加软约束，比如最小化总通勤时长、优先分配近距离作业等，进一步优化方案合理性。

内容的提问来源于stack exchange，提问作者Scott A. Levinson

OptaPlanner求解员工作业调度问题时如何添加业务约束

现有建模问题 #

修正后的领域模型 #

约束实现 #

注意事项 #

现有建模问题

修正后的领域模型

约束实现

注意事项