如何使用 docplex.cp（约束编程）对可中断任务的调度问题进行建模？

Question

我想使用约束编程（Python API of CPLEX : docplex.cp）对调度问题建模，我有机器可以分配给活动。活动是在轮班期间进行的，一些任务最多可以分为 3 个部分，但也不能分成几个部分。我使用区间变量对活动进行建模，并使用可选的区间变量（具有“替代”约束）对设备分配进行建模。给定任务的不同部分可以使用不同的设备或相同的设备来执行。

一个天真的方法可能是强制划分长时间的活动，但我想确保模型只在必要时选择划分。

提前感谢您的想法和帮助！

Answer 1

最好的方法是创建一个间隔链，并在需要少于全部段数时使用逻辑基元来使用较低索引的基元。这是一个代码：

from docplex.cp.model import CpoModel

cp = CpoModel()

n = 3
total_duration = 100

itvs = [ cp.interval_var(optional=True, name="I_{}".format(i)) for i in range(n) ]

for i in range(1, n):
    cp.add(cp.end_before_start(itvs[i-1], itvs[i]))
    #cp.add(cp.presence_of(itvs[i-1]) >= cp.presence_of(itvs[i]))
    cp.add(cp.if_then(cp.presence_of(itvs[i]), cp.presence_of(itvs[i-1])))

cp.add(cp.sum(cp.length_of(itvs[i]) for i in range(n)) == total_duration)

cp.export_as_cpo("chain.cpo")

然后您将在 chain.cpo 文件中包含以下内容：

#line 11 "chain.py"
I_1 = intervalVar(optional);
I_0 = intervalVar(optional);
I_2 = intervalVar(optional);

//--- Expressions ---
#line 11 "chain.py"
endBeforeStart(I_0, I_1);
#line 13
presenceOf(I_1) => presenceOf(I_0);
#line 11
endBeforeStart(I_1, I_2);
#line 13
presenceOf(I_2) => presenceOf(I_1);
#line 15
sum([lengthOf(I_0), lengthOf(I_1), lengthOf(I_2)]) == 100;

如何使用 docplex.cp（约束编程）对可中断任务的调度问题进行建模？

How to model a scheduling problem with interruptible tasks using docplex.cp (Constraint programming)?

python

cplex

cp

docplex