mathematical optimization - Timefold scheduling: am I running into limitations of the solver or am I doing something wrong? - St

admin管理员组

文章数量:1122832

I am trying to use Timefold (in Python) to solve a certain scheduling problem. The solutions I get violate a bunch of hard constraints, and I am wondering if I am running into the limitations of Timefold or if I am doing something wrong.

To explain my situation, I came up with a toy problem which is representative of my actual problem. Suppose we have 10 stores, 10 employees and we want to plan the shifts for 10 days. At each store, at most one employee can work on a given day. Moreover, we require each employee to work all 10 days and we don't want an employee to work in the same store more than once.

For completeness I give some code, but feel free to skip to the end, it may not be necessary to read this. Firstly in my domains.py file, I have a @planning_solution which looks as follows:

@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)

Then I have the following @planning_entity class:

@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}'

the @dataclass Shift

@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}'

and dataclasses Store and Employee, which are straightforward.

Then I have the following three constraints:

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!"))

When I create the above mentioned example in my main.py and run it for 500 seconds, this is some of the relevant output I get:

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)

So I end up with 20 violated hard constraints. So my question is, could I change something to get better results? Or is the problem simply too difficult for the solver to find a solution with no hard constraint violations? (Of course to this particular problem it is easy to write down a solution by hand - I'm not looking for that kind of answer.)

I am trying to use Timefold (in Python) to solve a certain scheduling problem. The solutions I get violate a bunch of hard constraints, and I am wondering if I am running into the limitations of Timefold or if I am doing something wrong.

To explain my situation, I came up with a toy problem which is representative of my actual problem. Suppose we have 10 stores, 10 employees and we want to plan the shifts for 10 days. At each store, at most one employee can work on a given day. Moreover, we require each employee to work all 10 days and we don't want an employee to work in the same store more than once.

For completeness I give some code, but feel free to skip to the end, it may not be necessary to read this. Firstly in my domains.py file, I have a @planning_solution which looks as follows:

@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)

Then I have the following @planning_entity class:

@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}'

the @dataclass Shift

@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}'

and dataclasses Store and Employee, which are straightforward.

Then I have the following three constraints:

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!"))

When I create the above mentioned example in my main.py and run it for 500 seconds, this is some of the relevant output I get:

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)

So I end up with 20 violated hard constraints. So my question is, could I change something to get better results? Or is the problem simply too difficult for the solver to find a solution with no hard constraint violations? (Of course to this particular problem it is easy to write down a solution by hand - I'm not looking for that kind of answer.)

• mathematical-optimization
• timefold

Share Improve this question Follow edited Nov 23, 2024 at 13:54 Reinderien 14.5k88 gold badges5454 silver badges8282 bronze badges asked Nov 22, 2024 at 0:26 StevenSteven 1111 silver badge22 bronze badges 2

• Hi @Steven. I don't immediately see anything wrong in your constraints, besides the fact the 2nd one probably isn't needed. The solver will not just duplicate any ProblemFacts (in your case Shifts), so no need to check for that. Could you check and share your data setup? My assumption would be that in the inputs you accidently added the same Employee or Store to more objects than you should have. – Tom Cools Commented Nov 22, 2024 at 8:24
• @TomCools Thank you for your response, two things: firstly, I made a typo, I intended that only one employee can work on a given day - changed that. Secondly, if I do remove the second constraint, I just get the solution where each employee works in store n on day n, so given the typo I just fixed, that would not be a valid solution. – Steven Commented Nov 22, 2024 at 8:49

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 1

It's not the ideal model: Instead of assigning an employee to a shift, assign a shift to an employee. Read this chapter.

Basically, you're doing row 2 of this, but should be doing row 3.

For your input with your constaints no feasible solution exist.

Potential causes:

• Your input. For example: do 100 hours of work with 2 people that can't work more than 40 hours each.
• Your constraints. For example: the "max 40 hours per week" is incorrectly implemented as "max 30 hours per week"

To prove that theory:

• Run a score analysis (see docs) on your output solution. Look at which shifts are still breaking which constraints.
• If you are convinced there is a feasible solution, build one by hand.
• Or make a change to the output solution so it becomes a better solution.
• Run that new solution through score analysis: does it agree it has a better score?

本文标签：