python - 有效计算给定开始/结束时间之间的 IntervalVars
问题描述
有没有一种有效的方法来计算给定开始时间和结束时间之间的 IntervalVar 数量?
我正在尝试实现员工排班脚本。我们已经产生了一个需求,它告诉我们在给定的时间间隔内应该有多少员工工作。
我想最终得到的是i
在 24(小时)间隔内为每个人提供一个 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()
解决方案
一些评论:
# calc start
model.Add(start == (end - dur)).OnlyEnforceIf(pres)
这已经由间隔 var 强制执行(实际上正是这个约束)。
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)
应该做的伎俩
推荐阅读
- python - 根据python中另一个字符串元素的数量删除字符串元素
- r - 将两个数据框组合在一起以创建具有所有组合的长数据框
- go - 从gorm数据库返回结构列表的函数返回nil?
- java - 接收导出 XML 映射时无法从 BOOLEAN 单元格获取 NUMERIC 值
- angular - Spring Boot 和 Angular 应用程序中的跨域问题
- flutter - Flutter Stepper 提交 onStepContinue
- flutter - Flutter: How to add space between two buttons in a row
- python - 通过另一列中每个值的平均值更改一列中的空值
- firebase - Firebase 函数在部署时不构建 Next.js 项目
- python - 在字典中通过引用传递值