有效计算给定 start/end 次之间的 IntervalVars

Question

有没有一种有效的方法来计算给定开始时间和结束时间之间的 IntervalVar 数量？

我正在尝试实施员工排班脚本。我们有一个已经生成的需求，告诉我们在给定的时间间隔内应该工作多少员工。

我想最终得到的是 24（小时）间隔内每个 i 的 IntVar，给员工总数 starttime <= i <= endtime。

下面是一个简单的例子。

from ortools.sat.python import cp_model

def main():

    # init model
    model = cp_model.CpModel()

    emps = range(0,3)

    emp_intervalvars = []
    for e in emps:
        start = model.NewIntVar(0,24,'st_e%i' % e)
        end = model.NewIntVar(0,24,'et_e%i' % e)
        dur = model.NewIntVar(0,24,'dur_e%i' % e)
        pres = model.NewBoolVar('pres_e%i' % e)
        interval = model.NewOptionalIntervalVar(start, dur, end, pres, 'interval_e%s' % e)

        # calc start
        model.Add(start == (end - dur)).OnlyEnforceIf(pres)

        # make sure to set start/end to 0 if not present
        model.Add(dur == 0).OnlyEnforceIf(pres.Not())
        model.Add(start == 0).OnlyEnforceIf(pres.Not())
        model.Add(end == 0).OnlyEnforceIf(pres.Not())

        # make sure to set start/duration to > 0 if present
        model.Add(dur > 0).OnlyEnforceIf(pres)
        model.Add(end > 0).OnlyEnforceIf(pres)

        # all emps between 8am and 6pm
        model.Add(start >= 8).OnlyEnforceIf(pres)
        model.Add(end <= 18).OnlyEnforceIf(pres)

        if e == 0:
            # lets say emp0 works mornings
            model.Add(end <= 14)
        elif e == 2:
            # and emp2 works evenings
            model.Add(start >= 11)

        emp_intervalvars.append({
            "present":pres,
            "start":start,
            "end":end,
            "duration":dur,
            "interval":interval
        })

    # simple objective
    durations = list(map(lambda v: v["duration"], emp_intervalvars))
    model.Maximize(sum(durations))

    solver = cp_model.CpSolver()
    solver.parameters.num_search_workers=8
    solver.parameters.max_time_in_seconds=30
    solver.parameters.log_search_progress=True
    status = solver.Solve(model)
    print(solver.StatusName(status))

    for i,field in enumerate(model._CpModel__model.variables):
        if field.name == '':
            continue
        print("{} : {}".format(field.name,solver._CpSolver__solution.solution[i]))

    return


if __name__ == '__main__':
    main()

Answer 1

一些评论：

    # calc start
    model.Add(start == (end - dur)).OnlyEnforceIf(pres)

这已经由间隔变量强制执行（实际上正是这个约束）。

    model.Add(end > 0).OnlyEnforceIf(pres)

很可能没有用。但是你可以保留它。

现在，回答您的问题：

给定 start 和 end 变量和时间 i

overlap_i = model.NewBoolVar('overlap_%i' % i)
before_i = model.NewBoolVar('before_%i' % i)
after_i = model.NewBoolVar('after_%i' % i)

model.Add(start <= i).OnlyEnforceIf(overlap_i)
model.Add(end > i).OnlyEnforceIf(overlap_i)  # Intervals are open ended on the right

model.Add(end <= i).OnlyEnforceIf(before_i)
model.Add(start > i).OnlyEnforceIf(after_i)

model.Add(overlap_i + before_i + after_i == 1)

应该可以解决问题

有效计算给定 start/end 次之间的 IntervalVars

Efficiently count IntervalVars between given start/end times

python

constraint-programming

or-tools