0

情况如下：我正在为工作场所创建每日时间表。每天都被划分为时间段，在每个时间段我都知道必须有多少员工在场。时间表是使用两个整数决策变量创建的，这些变量描述了每个员工的到达和离开时间段。

目前，我使用一个额外的变量来判断员工i在时间t是否在工作，然后我将它们与每个时间段的员工相加，以与需求进行比较。我的代码可以归结为以下内容：

using CP;

tuple TimeSlot {
    key int id;
    int minEmploy;
}
{TimeSlot} TSlots = ...;
{int} timeSlots = {t.id|t in TSlots};
int tMax = max(t in timeSlots) t;
range dayRange = 0..tMax;

range allEmployees = 1..10;

dvar int dayStart[allEmployees] in dayRange;
dvar int dayEnd[allEmployees] in dayRange;
dvar int workTimeT[allEmployees][timeSlots] in 0..1;

minimize ...;

subject to {
    /*Indicator constraints*/
    forall(i in allEmployees){
        forall(t in timeSlots:t>0){
            dayStart[i] <= t && t <= dayEnd[i] => workTimeT[i][t] == 1;
            dayEnd[i] < t || t < dayStart[i] => workTimeT[i][t] == 0;
        }
    } 
    /*Must satisfy requirement*/
    forall(t in timeSlots:t>0){
        sum(i in allEmployees) workTimeT[i][t] >= item(TSlots,<t>).minEmploy;
    }
}

有没有办法绕过这个额外的变量？添加#employees乘以#timeslots变量只是为了检查一个数字是否在两个决策变量之间，这不可能是有效的。

4

1 回答 1

0

我会将其写为与您所做的相反 - 我将转储整数变量（dayStart[i] 和 dayEnd[i]）并用布尔值替换它们（dayStart[i][t] 和 dayStart[i][t] ）。CPLEX 和其他求解器非常擅长使用此类布尔值集，尽管存在更多变量，但它实际上求解的速度可能比您尝试的要快。

它还可以更容易地找出有多少人在工作 - 这是已经开始工作的人数减去已完成工作的人数（假设没有环绕墓地轮班，你一天开始晚到第二天早上结束，你的提法似乎假设永远不会发生）。

dvar int dayStart[allEmployees][timeSlots] in 0..1;
dvar int dayEnd[allEmployees][timeSlots] in 0..1;

forall(i in allEmployees) {
    /* Every employee starts exactly once */
    sum(t in timeSlots) dayStart[i][t] == 1;

    /* Every employee stops exactly once */
    sum(t in timeSlots) dayEnd[i][t] == 1;

   /* You must start before you stop */
   forall(t in timeSlots) dayEnd[i][t] <= sum(tstart in timeSlots: tstart < t) dayStart[i][tstart];
}

/* the number of employees working is the number who have started minus
   the number who have stopped */
dexpr int NumWorking[t in timeSlots] = 
    sum(tstart in timeSlots: tstart <= t) dayStart[i][tstart] 
    -
    sum(tend in timeSlots: tend < t) dayEnd[i][tend];

/* Make sure we've got enough people working */
forall(t in timeSlots)
    NumWorking[t] >= item(TSlots,<t>).minEmploy;

如果你真的想要整数开始和结束时间，你可以很容易地用布尔值来写它：

dvar int+ employeeStartTime[allEmployees];
dvar int+ employeeEndTime[allEmployees];

forall(i in allEmployees) {
    employeeStartTime == sum(t in timeSlots) t*dayStart[i][t];
    employeeEndTime == sum(t in timeSlots) t*dayEnd[i][t];
}
于 2017-04-17T23:14:17.467 回答