使用时间粒度打破分配调度问题

Question

我有以下时间调度优化问题：

有 n 个休息时间要安排。一次休息占用 k 个时间单位，每个时间单位为 15 分钟。我正在查看的总 horizon 是米时间颗粒。每次谷物都有需要优化的中断量。开始休息的范围是每次休息定义的，您不能随意选择范围。

为了使其更通用 - 目标是随着时间的推移分配休息时间。我需要输出一个尽可能符合这个期望分布的结果。我被允许在特定范围内移动每个中断，例如1小时边界。

我查看了 TimeGrain 模式作为起点，在此处进行了描述：https://www.optaplanner.org/blog/2015/12/01/TimeSchedulingDesignPatterns.html and in this video: https://youtu.be/wLK2-4IGtWY。我正在尝试使用约束流进行增量优化。

到目前为止我的方法如下：

Break.scala:

case class Break(vehicleId: String, durationInGrains: Int)

TimeGrain.scala:

@PlanningEntity
case class TimeGrain(desiredBreaks: Int,
                     instant: Instant,
                     @CustomShadowVariable(...), // Dummy annotation, I want to use the entity in constraint stream 
                     var breaks: Set[Break])

中断分配：

@PlanningEntity
case class BreakAssignment(
  break: Break,
  @PlanningVariable(valueRangeProviderRefs = Array("timeGrainRange"))
  var startingTimeGrain: TimeGrain,
  @ValueRangeProvider(id = "timeGrainRange")
  @ProblemFactCollectionProperty @field
  timeGrainRange: java.util.List[TimeGrain],
  @CustomShadowVariable(
    variableListenerClass = classOf[StartingTimeGrainVariableListener],
    sources = Array(new PlanningVariableReference(variableName = "startingTimeGrain"))
  )
  var timeGrains: util.Set[TimeGrain]
)

object BreakAssignment {
  class StartingTimeGrainVariableListener extends VariableListener[Solution, BreakAssignment] {
    override def afterVariableChanged(scoreDirector: ScoreDirector[Solution], entity: BreakAssignment): Unit = {
      val end = entity.startingTimeGrain.instant
        .plusSeconds((entity.break.durationInGrains * TimeGrain.grainLength).toSeconds)
      scoreDirector.getWorkingSolution.timeGrains.asScala
        .filter(
          timeGrain =>
            timeGrain.instant == entity.startingTimeGrain.instant ||
            entity.startingTimeGrain.instant.isBefore(timeGrain.instant) && end
              .isAfter(timeGrain.instant)
        )
        .foreach { timeGrain =>
          scoreDirector.beforeVariableChanged(timeGrain, "breaks")
          timeGrain.breaks = timeGrain.breaks + entity.break
          scoreDirector.afterVariableChanged(timeGrain, "breaks")
        }
    }
  }
}

Constraints.scala:

private def constraint(constraintFactory: ConstraintFactory) =
  constraintFactory
    .from(classOf[TimeGrain])
    .filter(timeGrain => timeGrain.breaks.nonEmpty)
    .penalize(
      "Constraint",
      HardSoftScore.ONE_SOFT,
      (timeGrain: TimeGrain) => {
        math.abs(timeGrain.desiredBreaks - timeGrain.breaks.size)
      }
    )

如您所见，我需要遍历所有谷物，以找出需要更新哪些谷物以保持刚刚及时移动的中断。这在某种程度上否定了约束流的想法。

看待我面临的问题的另一种方式是，我无法通过例如 link 具有相应 TimeGrains 的 BreakAssignment 规划实体的方法。阴影变量。中断分配跨越多个时间粒度。 return 中的时间粒度包含多个中断分配。对于软约束，我需要将所有分配分组在同一个 grain 中，访问一个 grain 的所需目标中断计数，同时对我时间的所有 grains 执行此操作 horizon。因此，我的方法是将每个 grain 作为一个计划实体，这样我就可以在每次更改作业的开始时间 grain 时存储所有中断的信息。我最终得到的基本上是作业和时间粒度之间的 many-to-many 关系。根据我的理解，这不符合影子变量的逆机制，因为它需要 one-to-many 关系。

我在尝试提出正确的模型时是否走错了方向？

Answer 1

如果我正确理解你的意思，那么从概念上讲，在 TimeGrain class 中，我会保留一个（自定义）影子变量来保持（仅）与 TimeGrain 重叠的 Break 实例的计数（实例).为简单起见，我将其称为 breakCount。让我称 x 为 Break 跨度的 TimeGrains 数量。

因此，在求解器将 Break 实例分配给 TimeGrain 实例时，我会增加该 TimeGrain 实例的 breakCount。不仅是那个 TimeGrain 实例的 breakCount，还有接下来几个 (x-1) 个 TimeGrain 实例的 breakCount。请注意将每个增量包装在“scoreDirector.beforeVariableChanged()”-“scoreDirector.afterVariableChanged()”括号中。

分数计算会完成剩下的工作。但请注意，我自己也会 square TimeGrain 的理想 breakCount 和它的“真实”breakCount（即影子变量）的差异，如 OptaPlanner 的文档中所述，以强制执行更“公平”。

编辑：当然也递减 TimeGrain 的 breakCount 从 Timegrain 实例中删除 Break 实例...

使用时间粒度打破分配调度问题

Break distribution scheduling problem using time grains

optaplanner