如何在未建模为变量的时间范围内添加 PuLP 约束

Question

我目前正在处理涉及大量参数和决策变量的复杂调度问题。简而言之，我正在尝试根据容量、复杂性、可用时间和潜在完成时间为任务安排资源。

我有一个矩阵 Av,j,t 确定在时间 t 为项目 v 的工作 j 分配了多少资源，以及确定开始和结束时间的变量 Sv,j 和 Ev,j每个项目的工作。从数学上讲，这些约束都是有道理的，但我在建模时遇到了很多问题，特别是一些。

为确保作业分配仅发生在作业的开始和结束期间，我强制执行了以下限制：

pulp.lpSum([A[t][v][j] for t in [t0 for t0 in T if t0 >= S[v][j]]]) == P[v][j]
pulp.lpSum([A[t][v][j] for t in [t0 for t0 in T if t0 <= S[v][j] - 1]]) == 0
pulp.lpSum([A[t][v][j] for t in [t0 for t0 in T if t0 >= E[v][j] + 1]]) == 0

其中 Pv,j 是任务使用单个资源所花费的总时间。我对此类约束的主要问题是开始和结束时间是模型变量，而 T（时间集）不是。试图在模型中强制执行此约束证明是有问题的，因为在设置约束时 Sv,j 并未真正“初始化”，因此此约束实际上并未执行任何操作，因为 set

[t0 for t0 in T if t0 >= S[v][j]]

不随型号变化。我还有一个指标集来跟踪作业完成情况 Xv,j,t，当 t > Ev,j 时为 1，否则为 0。我已经尝试以多种方式强制执行此操作，但所有这些都依赖于 T 中 t 集合的总和，当模型调整时它们不会调整。

有人知道我如何强制这些集合随模型本身进行调整吗？

Answer 1

所有约束都需要是线性的。您尝试指定的是 non-linear，因此不允许。

相反，您需要建模如下：

                       t   1 2 3 4 5 6 7 8 9 10 11
   job is executing  x(t)  0 0 0 0 1 1 1 1 0 0 0 
   job is starting   s(t)  0 0 0 0 1 0 0 0 0 0 0

这可以建模为：

   s(t) >= x(t)-x(t-1)
   sum(t, s(t)) <= 1      (one start allowed)
   sum(t, x(t)) = joblen

获取开始和结束时间：

   S = sum(t, t*s(t));
   E = S + joblen - 1

这是一个相当标准的方法。可能在你的教科书里有提到。

如何在未建模为变量的时间范围内添加 PuLP 约束

How to add PuLP constraints over time ranges which aren't modeled as variables

python

mathematical-optimization

pulp