利用时间粒度的中断分配调度问题

Question

下面有一个时间调度优化问题：

有n个休息时间要安排。每次休息要花费15分钟的时间。我所看到的总地平线是m个时间颗粒。每次谷物都有一个理想的休息时间来优化。开始中断的范围是在每次中断时定义的，您不能随意选择范围。

为了使其更全面我需要输出一个结果，它将尽可能地与这个期望的分布保持一致。我被允许在特定的范围内，例如1小时的边界内移动每一次突破。

我看了一下TimeGrain模式作为起点，这里描述了https://www.optaplanner.org/blog/2015/12/01/TimeSchedulingDesignPatterns.html，在这个视频中描述了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])

BreakAssignment：

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

正如您所看到的，我需要对所有的谷物进行迭代，以确定哪些需要更新以保持刚才移动的中断。这在一定程度上否定了约束流的概念。

另一种看待我所面临的问题的方法是，我不能想出一种方法，通过影子变量将BreakAssignment规划实体与相应的TimeGrains连接起来。中断分配跨越多个时间谷类。作为回报的时间分配包含多个中断分配。对于软约束，我需要将所有赋值分组在同一个粒度中，访问所需的谷物目标中断计数，同时对我时间范围内的所有粒度进行分组。因此，我的方法是把每一个谷物作为一个计划实体，这样我就可以自己存储任务开始时间的每一次变化上的所有中断的信息。我最终得到的基本上是任务和时间之间的多到多的关系。根据我的理解，这不适合于影子变量的逆机制，因为它需要一对多的关系。

我想找出正确的模型，是不是走错了方向？

Answer 1

如果我正确理解您的意思，那么在概念上，在TimeGrain类中，我将保留一个(自定义的)阴影变量，保持(仅)与TimeGrain (实例)重叠的中断实例的计数。为了简单起见，让我称它为breakCount。让我称x为TimeGrains的数目，一个中断范围。

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

剩下的将由分数计算来计算。但是，请注意，我自己也会消除TimeGrain的理想breakCount和它的“实”breakCount (即影子变量)的差异，就像OptaPlanner的文档中所解释的那样，以执行更多的“公平”。

编辑:当然，在从时间谷物实例中删除一个中断实例时，也会减少时间谷物的breakCount .