时间戳

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

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

问题描述

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

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

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

标签： pythoncplexcpdocplex

解决方案

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

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;

推荐阅读