时间戳

首页 > 解决方案 > 不可行的解决方案，绝对可行 - CPLEX

cplex - 不可行的解决方案，绝对可行 - CPLEX

问题描述

基本上，我有两名员工，他们每个人都可以分配到两种花名册模式中的一种，这反过来又为每个员工分配一组轮班。

为员工分配一个花名册模式-> 该员工只能工作该花名册模式中规定的轮班，并且必须全部工作。

为此，我有一个约束，它基本上指出每个员工所做的所有班次的总和应该等于 input shiftsPerRP。因此，如果为比如说员工 Allan 选择了一个轮班模式，例如 0，那么 Allan 应该正好工作 45 个班次。

但是，此约束不断失败并导致不可行的解决方案。我无法弄清楚我在这里缺少什么。任何帮助表示赞赏。

相关数据：

days={
    1, 2, 3, 4, 5, 6, 7
}

People = {
    Allan,
    Joe,
};

rosterPatterns = {
    0,1
};


shiftsPerRP = {
    <0,45>
    <1,5>
};

Skills= {
    A, 
    B, 
    C
};

相关代码：

dvar boolean Assign[days][Hours][People][Skills];   // Indicates a shift assignment

range Hours = 0..23; 

forall(h in Hours, d in days, p in People, rp in rosterPatterns, shiftsInRP in shiftsPerRP : shiftsInRP.ID == rp)
      sum(s in Skills)
            Assign[d][h][p][s] == shiftsInRP.shifts;

标签： cplexopl

解决方案

为了分析这一点，请标记您的约束（请参阅添加的“c1”）：

forall(h in Hours,
       d in days,
       p in People,
       rp in rosterPatterns,
       shiftsInRP in shiftsPerRP
       : shiftsInRP.ID == rp)
c1:
      sum(s in Skills)
            Assign[d][h][p][s] == shiftsInRP.shifts;

使用该 OPL 应该计算一个最小冲突，以显示哪些约束是不可行的。这样做（在命令行上）我发现生成的第一个约束是不可行的。约束的左侧只有三个变量，但右侧是 5。这永远无法满足。

鉴于您的 set 中只有三个元素，Skills约束的左侧将始终有 3 个变量。因此它可以取 {0, 1, 2, 3} 中的值。如果对于任何元组shifts的值大于 3，则显然不能满足此约束。

编辑：看起来你可能混淆了应该进入的forall内容和应该进入的内容sum。为了正确制定，我认为您将需要一个辅助变量

dvar boolean RosterAssigned[People][rosterPatterns];

如果一个人被分配到一个名册模式，则为 1，否则为 0。有了它，您可以将约束表述为

forall(p in People)
  sum(h in Hours, s in Skills, d in days)
     Assign[d][h][p][s]
     == sum(rp in rosterPatterns, shiftsInRP in shiftsPerRP : shitsInRP.ID == rp) (RosterAssigned[p][rp] * shiftsInRP.shifts);

左侧给出了一个人p实际工作的班次数。右侧给出了轮班模式所需的轮班次数。当然，您还必须添加约束以保证每个员工都被分配到一个名册模式。

推荐阅读