Design patterns 设计模式

1. Design patterns introduction
1.设计模式介绍

Timefold Solver design patterns are generic reusable solutions to common challenges in the model or architecture of projects that perform constraint solving. The design patterns in this section list and solve common design challenges.
时间折叠求解器设计模式是针对执行约束求解的项目模型或架构中常见难题的通用可重用解决方案。本节中的设计模式列出并解决了常见的设计难题。

2. Domain modeling guidelines
2.领域建模指南

Follow the guidelines listed in this section to create a well thought-out model that can contribute significantly to the success of your planning.
请遵循本节列出的指导原则，创建一个经过深思熟虑的模型，这将大大有助于您的规划取得成功。

Draw a class diagram of your domain model.
绘制领域模型的类图。
1. Make sure there are no duplications in your data model and that relationships between objects are clearly defined.
  确保数据模型没有重复，对象之间的关系定义明确。
2. Create sample instances for each class. For example, in the employee rostering Employee class, create Ann, Bert, and Carl.
  为每个类创建示例实例。例如，在雇员名册 Employee 类中，创建 Ann 、 Bert 和 Carl 。
Determine which relationships (or fields) change during planning and color them orange. One side of these relationships will become a planning variable later on. For example, in employee rostering, the Shift to Employee relationship changes during planning, so it is orange. However, other relationships, such as from Employee to Skill, are immutable during planning because Timefold Solver cannot assign an extra skill to an employee.
确定哪些关系（或字段）在规划过程中会发生变化，并将其涂成橙色。这些关系的一边稍后将成为计划变量。例如，在员工花名册中， Shift 到 Employee 的关系在计划期间会发生变化，所以用橙色表示。但是，其他关系，如 Employee 到 Skill 的关系，在规划过程中是不变的，因为 Timefold Solver 无法为员工分配额外的技能。

If there are multiple relationships (or fields), check for shadow variables. A shadow variable changes during planning, but its value can be calculated based on one or more genuine planning variables, without dispute. Color shadow relationships (or fields) purple.
如果存在多个关系（或字段），请检查影子变量。影子变量在规划过程中会发生变化，但其值可以根据一个或多个真正的规划变量计算出来，不存在争议。将阴影关系（或字段）涂成紫色。

Only one side of a bi-directional relationship can be a genuine planning variable. The other side will become an inverse relation shadow variable later on. Keep bi-directional relationships orange.
双向关系中只有一边是真正的规划变量。另一侧稍后将成为反向关系的影子变量。保持双向关系为橙色。

If the goal is to find an optimal order of elements, use the Chained Through Time pattern.
如果目标是找到元素的最佳顺序，则可使用 "时间连锁 "模式。

If there is an orange many-to-many relationship, replace it with a one-to-many and a many-to-one relationship to a new intermediate class.
如果存在橙色的多对多关系，则将其替换为新的中间类的一对多和多对一关系。

The following figure illustrates introducing a ShiftAssignment class to represent the many-to-many relationship between Shift and Employee. Shift contains every shift time that needs to be filled with an employee.
下图说明了引入 ShiftAssignment 类来表示 Shift 和 Employee 之间的多对多关系。 Shift 包含了每个需要被员工填补的轮班时间。

Timefold Solver does not currently support a @PlanningVariable annotation on a collection. Planning list variable is not a means of achieving a many-to-one relationship; it serves to indicate that these values happen in a sequence one after another.
Timefold Solver 目前不支持集合上的 @PlanningVariable 注释。规划列表变量并不是实现多对一关系的一种手段；它的作用是表明这些值是一个接一个地按顺序出现的。

Annotate a many-to-one relationship with a @PlanningEntity annotation. Usually the many side of the relationship is the planning entity class that contains the planning variable. If the relationship is bi-directional, both sides are a planning entity class but usually the many side has the planning variable and the one side has the shadow variable. For example, in employee rostering, the ShiftAssignment class has an @PlanningEntity annotation.
用 @PlanningEntity 注释多对一关系。通常，关系的多方是包含规划变量的规划实体类。如果是双向关系，则双方都是规划实体类，但通常多方拥有规划变量，单方拥有影子变量。例如，在雇员名册中， ShiftAssignment 类有一个 @PlanningEntity 注解。
Make sure that the planning entity class has at least one problem property. A planning entity class cannot consist of only planning variables or an ID and only planning variables.
确保规划实体类至少有一个问题属性。规划实体类不能只包含规划变量或 ID 和规划变量。
1. Remove any surplus @PlanningVariable annotations so that they become problem properties. Doing this significantly decreases the search space size and significantly increases solving efficiency. For example, in employee rostering, the ShiftAssignment class should not annotate both the Shift and Employee relationship with @PlanningVariable.
  删除多余的 @PlanningVariable 注释，使其成为问题属性。这样做可以大大减少搜索空间的大小，显著提高解题效率。例如，在员工轮岗中， ShiftAssignment 类不应该用 @PlanningVariable 同时注解 Shift 和 Employee 的关系。
2. Make sure that when all planning variables have a value of null, the planning entity instance is describable to the business people. Planning variables have a value of null when the planning solution is uninitialized.
  确保当所有规划变量的值为 null 时，规划实体实例可以向业务人员描述。当规划解决方案未初始化时，规划变量的值为 null 。
  - A surrogate ID does not suffice as the required minimum of one problem property.
    代用 ID 不足以满足最少一个问题属性的要求。
  - There is no need to add a hard constraint to assure that two planning entities are different. They are already different due to their problem properties.
    无需添加硬约束来确保两个规划实体是不同的。由于它们的问题属性，它们本来就是不同的。
  - In some cases, multiple planning entity instances have the same set of problem properties. In such cases, it can be useful to create an extra problem property to distinguish them. For example, in employee rostering, the ShiftAssignment class has the problem property Shift as well as the problem property indexInShift which is an int class.
    在某些情况下，多个规划实体实例具有相同的问题属性集。在这种情况下，创建一个额外的问题属性来区分它们可能是有用的。例如，在员工轮岗中， ShiftAssignment 类具有 Shift 问题属性，而 indexInShift 是 int 类的问题属性。
Choose the model in which the number of planning entities is fixed during planning. For example, in the employee rostering, it is impossible to know in advance how many shifts each employee will have before Timefold Solver solves the model and the results can differ for each solution found. On the other hand, the number of employees per shift is known in advance, so it is better to make the Shift relationship a problem property and the Employee relationship a planning variable as shown in the following examples.
选择规划期间规划实体数量固定的模型。例如，在员工轮岗中，在 Timefold Solver 求解模型之前，不可能事先知道每个员工将有多少个班次，因此找到的每个解决方案的结果都可能不同。另一方面，每个班次的员工人数是事先已知的，因此最好将 Shift 关系作为问题属性，而 Employee 关系作为规划变量，如以下示例所示。

3. Assigning time to planning entities
3.为规划实体分配时间

Dealing with time and dates in planning problems may be problematic because it is dependent on the needs of your use case.
在规划问题中处理时间和日期可能会有问题，因为这取决于用例的需求。

There are several representations of timestamps, dates, durations and periods in Java, Kotlin and Python. Choose the right representation type for your use case:
在 Java、Kotlin 和 Python 中，时间戳、日期、持续时间和周期有多种表示方法。请根据您的用例选择正确的表示类型：

DayOfWeek with or without LocalTime if no date is involved.
DayOfWeek 如果不涉及日期，则带或不带 LocalTime 。
LocalDate if no time is involved.
LocalDate 如果不涉及时间。
LocalDateTime if your model only works in a single timezone without DST (Daylight Saving Time).
LocalDateTime 如果您的模型只在没有 DST（夏令时）的单一时区工作。
OffsetDateTime if your model supports timezones or DST (Daylight Saving Time).
OffsetDateTime 如果您的机型支持时区或 DST（夏令时）。
- Avoid ZonedDateTime, it is error-prone.
  避免使用 ZonedDateTime ，它容易出错。
Never use java.util.Date: it is a slow, error-prone way to represent timestamps.
切勿使用 java.util.Date ：这种表示时间戳的方法既慢又容易出错。

There are also several designs for assigning a planning entity to a starting time (or date):
还有几种将规划实体分配到起始时间（或日期）的设计：

If the starting time is fixed beforehand, it is not a planning variable (in that solver).
如果起始时间是事先确定的，那么它就不是一个规划变量（在该求解器中）。
- For example: in Bed Allocation Scheduling, the arrival day of each patient is fixed beforehand.
  例如：在病床分配调度中，每个病人的到达日期是事先确定的。
- This is common in multi-stage planning, when the starting time has been decided already in an earlier planning stage.
  这在多阶段规划中很常见，因为在早期规划阶段已经决定了起始时间。
If the starting time is not fixed, it is a planning variable (genuine or shadow).
如果起始时间不固定，那么它就是一个规划变量（真实变量或影子变量）。
- If all planning entities have the same duration, use the Timeslot pattern.
  如果所有规划实体的持续时间相同，则使用时隙模式。
  - For example, in school timetabling, all lectures take one hour. Therefore, each timeslot is one hour.
    例如，在学校课程表中，所有讲座的时间都是一小时。因此，每个时段为一小时。
  - Even if the planning entities have different durations, but the same duration per type, it’s often appropriate.
    即使规划实体的持续时间不同，但每种类型的持续时间相同，通常也是合适的。
    
    For example, in conference scheduling, breakout talks take one hour and lab talks take 2 hours. But there’s an enumeration of the timeslots and each timeslot only accepts one talk type.
    例如，在会议日程安排中，分组讨论需要一小时，实验室讨论需要两小时。但有一个时间段枚举，每个时间段只接受一种会谈类型。
- If the duration differs and time is rounded to a specific time granularity (for example 5 minutes) use the TimeGrain pattern.
  如果持续时间不同，且时间四舍五入到特定的时间粒度（例如 5 分钟），则使用 TimeGrain 模式。
- If the duration differs and one task starts immediately after the previous task (assigned to the same executor) finishes, use the Chained Through Time pattern.
  如果持续时间不同，且一项任务在前一项任务（分配给同一执行器）完成后立即开始，则使用 "时间链 "模式。
  - For example, in time windowed vehicle routing, each vehicle departs immediately to the next customer when the delivery for the previous customer finishes.
    例如，在时间窗口车辆路由选择中，每辆车在为前一位客户送货结束后，立即出发前往下一位客户。
  - Even if the next task does not always start immediately, but the gap is deterministic, it applies.
    即使下一项任务并不总是立即开始，但间隙是确定的，它也适用。
    
    For example, in vehicle routing, each driver departs immediately to the next customer, unless it’s the first departure after noon, in which case there’s first a 1 hour lunch.
    例如，在车辆路线安排中，每位司机都会立即出发前往下一位客户，除非是中午过后的第一次出发，在这种情况下，首先要有 1 小时的午餐时间。
- If the employees need to decide the order of theirs tasks per day, week or SCRUM sprint themselves, use the Time Bucket pattern.
  如果员工需要自己决定每天、每周或 SCRUM 冲刺阶段的任务顺序，可使用时间桶模式。
  - For example, in elevator maintenance scheduling, a mechanic gets up to 40 hours worth of tasks per week, but there’s no point in ordering them within 1 week because there’s likely to be disruption from entrapments or other elevator outages.
    例如，在电梯维护调度中，技工每周最多能完成 40 小时的任务，但在 1 周内下达任务是没有意义的，因为很可能会出现夹人或其他电梯故障。

Choose the right pattern depending on the use case:
根据使用情况选择正确的模式：

3.1. Timeslot pattern: assign to a fixed-length timeslot

If all planning entities have the same duration (or can be inflated to the same duration), the Timeslot pattern is useful. The planning entities are assigned to a timeslot rather than time. For example, in school timetabling, all lectures take one hour.

The timeslots can start at any time. For example, the timeslots start at 8:00, 9:00, 10:15 (after a 15-minute break), 11:15, … They can even overlap, but that is unusual.

It is also usable if all planning entities can be inflated to the same duration. For example, in Examination Timetabling, some exams take 90 minutes and others 120 minutes, but all timeslots are 120 minutes. When an exam of 90 minutes is assigned to a timeslot, for the remaining 30 minutes, its seats are occupied too and cannot be used by another exam.

Usually there is a second planning variable, for example the room. In course timetabling, two lectures are in conflict if they share the same room at the same timeslot. However, in exam timetabling, that is allowed, if there is enough seating capacity in the room (although mixed exam durations in the same room do inflict a soft score penalty).

3.2. TimeGrain pattern: assign to a starting TimeGrain

Assigning humans to start a meeting at four seconds after 9 o’clock is pointless because most human activities have a time granularity of five minutes or 15 minutes. Therefore it is not necessary to allow a planning entity to be assigned subsecond, second or even one minute accuracy. A granularity of 15 minutes, 1 hour or 1 day accuracy suffices for most use cases. The TimeGrain pattern models such time accuracy by partitioning time as time grains. For example, in Meeting Scheduling, all meetings start/end in hour, half hour, or 15-minute intervals before or after each hour, therefore the optimal settings for time grains is 15 minutes.

Each planning entity is assigned to a start time grain. The end time grain is calculated by adding the duration in grains to the starting time grain. Overlap of two entities is determined by comparing their start and end time grains.

The TimeGrain pattern doesn’t scale well. Especially with a finer time granularity (such as 1 minute) and a long planning window, the value range (and therefore the search space) is too big to scale well. It’s recommended to use a coarse time granularity (such as 1 week, 1 day, 1 half day, …) or shorten the planning window size to scale. To resolve scaling issues, the Time Bucket pattern is often a good alternative.

3.3. Chained through time pattern: assign in a chain that determines starting time

If a person or a machine continuously works on one task at a time in sequence, which means starting a task when the previous is finished (or with a deterministic delay), the Chained Through Time pattern is useful. For example, in Vehicle routing with time windows, a vehicle drives from customer to customer (thus it handles one customer at a time).

The focus in this pattern is on deciding the order of a set of elements instead of assigning them to a specific date and time. However, the time coordinate of each element can be deduced from its position in the sequence. If the elements’ position on time axis affects the score, use a shadow variable to calculate the time.

This pattern is implemented using either the chained planning variable or the planning list variable. The two modeling approaches are equivalent because they both allow Timefold Solver to order elements in sequences of variable lengths. The planning list variable is easier to use than the chained planning variable, but it does not yet support all the advanced planning techniques.

3.3.1. Chained through time pattern using chained planning variable

Using the chained planning variable, planning entities are arranged in a recursive data structure, forming a chain, that ends with an anchor.

The anchor determines the starting time of its first planning entity. The second entity’s starting time is calculated based on the starting time and duration of the first entity. For example, in task assignment, Beth (the anchor) starts working at 8:00, thus her first task starts at 8:00. It lasts 52 minutes, therefore her second task starts at 8:52. The starting time of an entity is usually a shadow variable.

An anchor has only one chain. Although it is possible to split up the anchor into two separate anchors, for example split up Beth into Beth’s left hand and Beth’s right hand (because she can do two tasks at the same time), this model makes pooling resources difficult. Consequently, using this model in the exam scheduling example to allow two or more exams to use the same room at the same time is problematic.

3.3.2. Chained through time pattern using planning list variable

Timefold Solver distributes planning values into planning entities’ planning list variable.

The planning entity determines the starting time of the first element in its planning list variable. The second element’s starting time is calculated based on the starting time and duration of the first element. For example, in task assignment, Beth (the entity) starts working at 8:00, thus her first task starts at 8:00. It lasts 52 minutes, therefore her second task starts at 8:52. The starting time of an element is usually a shadow variable.

3.3.3. Chained through time pattern: creating gaps

Between planning entities, there are three ways to create gaps:

No gaps: This is common when the anchor is a machine. For example, a build server always starts the next job when the previous finishes, without a break.
Only deterministic gaps: This is common for humans. For example, any task that crosses the 10:00 barrier gets an extra 15 minutes duration so the human can take a break.
- A deterministic gap can be subjected to complex business logic. For example, a cross-continent truck driver needs to rest 15 minutes after two hours of driving (which may also occur during loading or unloading time at a customer location) and also needs to rest 10 hours after 14 hours of work.
Planning variable gaps: This is uncommon, because that extra planning variable reduces efficiency and scalability, (besides impacting the search space too).

3.3.4. Chained through time: automatic collapse

In some use case there is an overhead time for certain tasks, which can be shared by multiple tasks, if those are consecutively scheduled. Basically, the solver receives a discount if it combines those tasks.

For example when delivering pizza to two different customers, a food delivery service combines both deliveries into a single trip, if those two customers ordered from the same restaurant around the same time and live in the same part of the city.

Implement the automatic collapse in the custom variable listener that calculates the start and end times of each task.

3.3.5. Chained through time: automatic delay until last

Some tasks require more than one person to execute. In such cases, both employees need to be there at the same time, before the work can start.

For example when assembling furniture, assembling a bed is a two-person job.

chainedThroughTimeAutomaticDelayUntilLast

Implement the automatic delay in the custom variable listener that calculates the arrival, start and end times of each task. Separate the arrival time from the start time. Additionally, add loop detection to avoid an infinite loop:

chainedThroughTimeAutomaticDelayUntilLastLoop

3.4. Time bucket pattern: assign to a capacitated bucket per time period

In this pattern, the time of each employee is divided into buckets. For example 1 bucket per week. Each bucket has a capacity, depending on the FTE (Full Time Equivalent), holidays and the approved vacation of the employee. For example, a bucket usually has 40 hours for a full time employee and 20 hours for a half time employee but only 8 hours on a specific week if the employee takes vacation the rest of that week.

Each task is assigned to a bucket, which determines the employee and the coarse-grained time period for working on it. The tasks within one bucket are not ordered: it’s up to the employee to decide the order. This gives the employee more autonomy, but makes it harder to do certain optimization, such as minimize travel time between task locations.

4. Cloud architecture patterns

There are two common usage patterns of Timefold Solver in the cloud:

Batch planning: Typically runs at night for hours to solve each tenant’s dataset and deliver each schedule for the upcoming day(s) or week(s). Only the final best solution is sent back to the client. This is a good fit for a serverless cloud architecture.
Real-time planning: Typically runs during the day, to handle unexpected problem changes as they occur in real-time and sends each best solution as they are discovered to the client.