时间折叠调度：我是否遇到了求解器的限制或者我做错了什么？

Question

我正在尝试使用Timefold（在Python中）来解决某个调度问题。我得到的解决方案违反了一系列硬性约束，我想知道我是否遇到了 Timefold 的限制或者我是否做错了什么。

为了解释我的情况，我想出了一个代表我实际问题的玩具问题。假设我们有 10 家商店、10 名员工，我们想要计划 10 天的轮班。每家商店每天最多可以工作一名员工。而且，我们要求每个员工工作满10天，并且我们不希望员工在同一家商店工作超过一次。

为了完整起见，我给出了一些代码，但请随意跳到最后，可能没有必要阅读此内容。首先在我的domains.py 文件中，我有一个@planning_solution，如下所示：

@planning_solution
@dataclass
class Schedule:
    id: str
    shifts: Annotated[list[Shift],
                     ProblemFactCollectionProperty,
                     ValueRangeProvider]
    shift_assignments: Annotated[list[ShiftAssignment], PlanningEntityCollectionProperty]

    score: Annotated[HardSoftScore, PlanningScore] = field(default=None)

然后我有以下@planning_entity类：

@planning_entity
@dataclass
class ShiftAssignment:
    id: Annotated[str, PlanningId]
    period: int
    employee: Employee
    shift: Annotated['Shift', PlanningVariable] = field(default=None)

    def __str__(self):
        return f'{self.name}'

@dataclass 转变

@dataclass
class Shift:
    id: Annotated[str, PlanningId]
    store: Store
    period: int
    #shift_assignment_list: Annotated[list[ShiftAssignment],
    #                                    InverseRelationShadowVariable(source_variable_name ="shift")]

    def __str__(self):
        return f'{self.name}'

还有数据类 Store 和 Employee，它们很简单。

那么我有以下三个限制：

def shift_period_constraint(constraint_factory: ConstraintFactory) -> Constraint:
    return (constraint_factory
            .for_each(ShiftAssignment)
            .filter(lambda shift_assignment: shift_assignment.period != shift_assignment.shift.period)
            .penalize(HardSoftScore.ONE_HARD)
            .as_constraint("Assigned shift in wrong period!"))


def doubly_assigned_shift_conflict(constraint_factory: ConstraintFactory) -> Constraint:
    return (constraint_factory
            .for_each_unique_pair(ShiftAssignment,
                                Joiners.equal(lambda shift_assignment: shift_assignment.shift))
            .penalize(HardSoftScore.ONE_HARD)
            .as_constraint("Shift assigned more than once!"))



def employee_works_store_at_most_once(constraint_factory: ConstraintFactory) -> Constraint:
    return (constraint_factory
            .for_each_unique_pair(ShiftAssignment,
                                  Joiners.equal(lambda shift_assignment: shift_assignment.employee),
                                  Joiners.equal(lambda shift_assignment: shift_assignment.shift.store))
            .penalize(HardSoftScore.ONE_HARD)
            .as_constraint("Employee works at same store more than once conflict!"))

当我在 main.py 中创建上述示例并运行 500 秒时，这是我得到的一些相关输出：

approximate problem scale (1 × 10^200)
Heuristic phase (0) ended: time spent (322), best score (-24hard/0soft), score calculation speed (41322/sec), step total (100)
INFO:timefold.solver:Solving ended: time spent (500001), best score (-20hard/0soft), score calculation speed (59304/sec)

所以我最终遇到了 20 个违反的硬约束。所以我的问题是，我可以改变一些东西以获得更好的结果吗？或者问题对于求解者来说太难找到不违反硬约束的解决方案？ （当然，对于这个特定问题，很容易手工写下解决方案 - 我不是在寻找那种答案。）

Answer 1

这不是理想的模型：不要将员工分配到轮班，而是将轮班分配给员工。 阅读本章。

基本上，您正在执行第 2 行，但应该执行第 3 行。