如何使用Timefold Solver优化带时间约束的多任务时隙分配

核心建模调整 #

要解决单时隙闲置问题，首先要打破“任务绑定整个可用时隙”的固有逻辑，重新定义实体与变量：

1. 重构实体结构 #

• 保留核心基础实体：Task（包含任务类型、时长、最早开始时间、最晚结束时间）、Worker（包含可执行任务类型集合）
• 新增WorkerAvailability问题事实：记录工人的具体可用时间段（比如2024-05-20 09:00到2024-05-20 12:00），替代原有的“时隙绑定任务”逻辑
• 新增TaskAssignment规划实体：作为任务与工人的关联载体，每个实例代表某任务在某工人的某时间段内执行，不再绑定整个可用时隙

2. 规划变量定义 #

给TaskAssignment设置两个关键规划变量：

• worker：任务分配的目标工人（需满足工人可执行该任务类型的约束）
• startTime：任务的实际开始时间（需落在工人的某个WorkerAvailability区间内，且满足任务自身的时间约束）

关键Solver Pattern选择 #

1. 时间窗调度模式（Time Windowed Scheduling） #

这是适配此类问题的核心模式，需重点实现三类约束：

• 任务时间窗硬约束：任务开始时间≥Task.earliestStart，任务结束时间（startTime+Task.duration）≤Task.latestEnd
• 工人可用时隙硬约束：任务的时间区间必须完全落在某一WorkerAvailability的区间内，且对应工人匹配
• 无重叠硬约束：同一工人的所有TaskAssignment时间区间不能重叠

2. 首次适配递减（First Fit Decreasing）初始解策略 #

在初始解构建阶段，优先安排长任务避免后期资源浪费：

• 先将任务按时长从长到短排序
• 遍历每个任务，为其找到第一个能容纳它的工人可用时隙，将任务插入到时隙的最早可执行位置

3. 局部搜索优化动作 #

初始解完成后，通过以下动作压缩闲置时间：

• 任务移动：将任务从一个工人的时隙移动到另一个工人的空闲时段（满足类型、时间约束）
• 任务交换：交换两个任务的执行时间/工人，填补闲置间隙
• 时间调整：在同一工人的时隙内微调任务开始时间，压缩任务间的空闲间隔

示例约束代码片段 #

硬约束：任务必须落在工人可用时隙内 #

private Constraint taskFitsInWorkerAvailability(ConstraintFactory factory) {
    return factory.forEach(TaskAssignment.class)
            .join(WorkerAvailability.class, 
                Joiners.equal(TaskAssignment::getWorker, WorkerAvailability::getWorker))
            .filter((assignment, availability) -> 
                assignment.getStartTime().isBefore(availability.getStart()) ||
                assignment.getStartTime().plus(assignment.getTask().getDuration()).isAfter(availability.getEnd()))
            .penalize("Task outside worker availability", HardSoftScore.ONE_HARD);
}

硬约束：同一工人任务无时间重叠 #

private Constraint noOverlappingTasksForWorker(ConstraintFactory factory) {
    return factory.forEachUniquePair(TaskAssignment.class, 
            Joiners.equal(TaskAssignment::getWorker),
            Joiners.overlapping(
                TaskAssignment::getStartTime, 
                assignment -> assignment.getStartTime().plus(assignment.getTask().getDuration())
            ))
            .penalize("Overlapping tasks", HardSoftScore.ONE_HARD);
}

软约束：最小化工人工时闲置 #

private Constraint minimizeWorkerIdleTime(ConstraintFactory factory) {
    return factory.forEach(WorkerAvailability.class)
            .join(TaskAssignment.class, 
                Joiners.equal(WorkerAvailability::getWorker, TaskAssignment::getWorker))
            .groupBy(WorkerAvailability::getId, 
                ConstraintCollectors.sumLong((availability, assignment) -> 
                    assignment.getTask().getDuration().toMinutes()))
            .filter((availId, totalTaskDuration) -> {
                WorkerAvailability availability = getAvailabilityById(availId);
                long slotDuration = Duration.between(availability.getStart(), availability.getEnd()).toMinutes();
                return totalTaskDuration < slotDuration;
            })
            .penalize("Idle time in worker slot", HardSoftScore.ONE_SOFT, 
                (availId, totalTaskDuration) -> {
                    WorkerAvailability availability = getAvailabilityById(availId);
                    long slotDuration = Duration.between(availability.getStart(), availability.getEnd()).toMinutes();
                    return slotDuration - totalTaskDuration;
                });
}

额外实用建议 #

• 周期性可用处理：如果工人是周期性可用（比如每周一、三下午），提前将周期规则展开为具体的WorkerAvailability实例（比如未来4周的所有可用时段），简化约束逻辑
• 超长任务拆分：对于单个时隙无法容纳的长任务，可拆分为多个子任务，建模时新增SubTask实体并添加“子任务顺序执行”的硬约束
• 调试辅助：使用Timefold的SolverManager输出调度结果，或结合可视化工具查看时隙填充情况，快速定位闲置间隙的成因

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