排班问题——NurseRosteringProblem（NRP）实战

背景

上次周末碰到女朋友在排班表&＃xff0c;花了快一个小时&＃xff0c;就想着看用代码帮她节省点时间。

问题调研

上网查了一下&＃xff0c;看了几篇论文了解了背景。

http://citeseerx.ist.psu.edu/viewdoc/download?doi&＃61;10.1.1.1030.5363&rep&＃61;rep1&type&＃61;pdf
https://arxiv.org/pdf/1804.05002.pdf

排班之类的问题都统称为 Nurse Rostering Problem&＃xff08;NRP&＃xff09;问题&＃xff0c;就复杂性而言&＃xff0c;这是一个NP-hard问题

P问题是在多项式时间内可以被解决的问题&＃xff0c;而NP问题是在多项式时间内可以被验证其正确性的问题

多项式时间指的是什么&＃xff1f;我理解就是平时计算的算法复杂度

O(1) – constant-time
O(log_2(n)) – logarithmic-time
O(n) – linear-time
O(n^2) – quadratic-time
O(n^k) – polynomial-time
O(k^n) – exponential-time
O(n!) – factorial-time


关于NP问题的描述可以看看我找到的这篇文章

提及复杂性理论&＃xff0c;是因为更精准地分析问题后&＃xff0c;才能找到合适的工具。

这类问题我们就会想到用计算机科学里面的方法去处理&＃xff0c;例如machine learning。

工具查找——找巨人的肩膀

机器学习的技术栈&＃xff0c;我学过的就是Python中的scikit-learn、TensorFlow和Keras上去做选择

据我了解&＃xff0c;这是一个研究了多年的课题了。既然这样&＃xff0c;应该是会有现成训练好的模型去做这类事情。

最后的最后&＃xff0c;我就找到了Google开发的OR-Tools&＃xff08;Official Site&＃xff09;。它已经有训练过的模型去处理这类排班问题了。

Action

Code example

官方例子Source Code

主要就是对源码做调整了&＃xff0c;以满足现实需求。

or-tools的基本用法

摘抄的伪代码&＃xff0c;用于了解工作方式

// 选择和定义一个model&＃xff0c;然后设置所需的前置数据和限制条件
model &＃61; cp_model.CpModel()
model.NewBoolVar(...)
model.AddExactlyOne(...)
model.Add(...)// 选择和定义一个solver&＃xff0c;然后针对model进行optimizate
solver &＃61; cp_model.CpSolver()
status &＃61; solver.Solve(model, solution_printer)// 创建一个矩阵进行拟合
work &＃61; {}
for e in range(num_employees):for s in range(num_shifts):for d in range(num_days):work[e, s, d] &＃61; model.NewBoolVar(&＃39;work%i_%i_%i&＃39; % (e, s, d))
// 下面是打印结果的算法
if status &＃61;&＃61; cp_model.OPTIMAL or status &＃61;&＃61; cp_model.FEASIBLE:print()header &＃61; &＃39; &＃39;for w in range(num_weeks):header &＃43;&＃61; &＃39;M T W T F S S &＃39;print(header)for e in range(num_employees):schedule &＃61; &＃39;&＃39;for d in range(num_days):for s in range(num_shifts):if solver.BooleanValue(work[e, s, d]): // NOTE: 获取优化算法出来的结果schedule &＃43;&＃61; shifts[s] &＃43; &＃39; &＃39;print(&＃39;worker %i: %s&＃39; % (e, schedule))print()


参数调整

例子源码中参数注释都很清楚地标明了用法了&＃xff0c;适当对现实问题的需要作出调整就行了。下面伪代码只是针对参数作了一些说明。

num_employees &＃61; 4 // 员工数&＃xff0c;改为目标的员工数
num_weeks &＃61; 5 // 工作天数&＃xff0c;目标是排一个月的班表&＃xff0c;改为5周
shifts &＃61; [&＃39;O&＃39;, &＃39;M&＃39;, &＃39;A&＃39;, &＃39;N&＃39;] // 班期&＃xff0c;和目标一样# Fixed assignment: (employee, shift, day).
# 固定前两天的&＃xff0c;排班前得动态调整下
fixed_assignments &＃61; [(0, 0, 0),(1, 1, 0),(2, 2, 0),(3, 3, 0),(0, 0, 1),(1, 1, 1),(2, 2, 1),(3, 3, 1),
]# Request: (employee, shift, day, weight)
# 员工想要固定休息的时间&＃xff08;位置&＃xff09;&＃xff0c;权重值我理解为代表拟合时可调整的优先级
requests &＃61; [# Employee 3 does not want to work on the first Saturday (negative weight for the Off shift).(3, 0, 5, -2),# Employee 2 does not want a night shift on the first Friday (positive weight).(2, 3, 4, 4)
]# Shift constraints on continuous sequence :
# (shift, hard_min, soft_min, min_penalty,
# soft_max, hard_max, max_penalty)
# hard_min: 硬性限制&＃xff0c;在周期内最少连续要上的班期天数
# soft_min: 软性限制&＃xff0c;在周期内最少连续要上的班期天数
# soft_max和hard_max同上去理解
shift_constraints &＃61; [# One or two consecutive days of rest, this is a hard constraint.(0, 1, 1, 0, 2, 2, 0),# betweem 2 and 3 consecutive days of night shifts, 1 and 4 are# possible but penalized.(3, 1, 2, 20, 3, 4, 5),
]# Weekly sum constraints on shifts days:
# (shift, hard_min, soft_min, min_penalty,
# soft_max, hard_max, max_penalty)
weekly_sum_constraints &＃61; [# 每周最少要休息的天数(0, 1, 2, 7, 2, 3, 4),
]# Penalized transitions:
# (previous_shift, next_shift, penalty (0 means forbidden))
penalized_transitions &＃61; [# 尽量避免午班换晚班(2, 3, 4),# 晚班不能接着早班(3, 1, 0),
]# daily demands for work shifts (morning, afternon, night) for each day
# of the week starting on Monday.
# 每个班期最少要有多少人&＃xff0c;我这里的现实问题是有一个人就行了
weekly_cover_demands &＃61; [(1, 1, 1), # Monday(1, 1, 1), # Tuesday(1, 1, 1), # Wednesday(1, 1, 1), # Thursday(1, 1, 1), # Friday(1, 1, 1), # Saturday(1, 1, 1), # Sunday
]# Penalty for exceeding the cover constraint per shift type.
excess_cover_penalties &＃61; (2, 2, 5)num_days &＃61; num_weeks * 7
num_shifts &＃61; len(shifts)


画甘特图

技术栈中&＃xff0c;选择了matplot去画甘特图&＃xff0c;也是现学现卖。

# Generate plot image. [reference: https://www.geeksforgeeks.org/python-basic-gantt-chart-using-matplotlib]shifts_colors &＃61; [&＃39;white&＃39;, &＃39;tab:green&＃39;, &＃39;tab:orange&＃39;, &＃39;tab:blue&＃39;]if status &＃61;&＃61; cp_model.OPTIMAL or status &＃61;&＃61; cp_model.FEASIBLE:offset &＃61; 2# Declaring a figure "gnt"fig, gnt &＃61; plt.subplots()# Setting Y-axis limitsgnt.set_ylim(0, num_employees * 15)# Setting X-axis limitsgnt.set_xlim(1, num_days &＃43; offset)# Setting labels for x-axis and y-axisgnt.set_xlabel(&＃39;Dates&＃39;)gnt.set_ylabel(&＃39;Employees&＃39;)# Setting ticks on y-axis# gnt.set_yticks([15, 25, 35, 45])gnt.set_xticks(list(range(1, num_days &＃43; offset, 1)))gnt.set_yticks(list(range(15, (num_employees &＃43; 1) * 10 &＃43; 5, 10)))# Labelling tickes of y-axisgnt.set_yticklabels(employees_names)# Setting graph attributegnt.grid(True)for e in range(num_employees):for d in range(num_days):for s in range(num_shifts):if solver.BooleanValue(work[e, s, d]):gnt.broken_barh([(d&＃43;1, d&＃43;2)], (10*(e&＃43;1), 9),facecolors&＃61;(shifts_colors[s]))plt.savefig("gantt1.png")


结果&＃xff1a;

总结

• 业界很强大
• 充分理解问题才能便于找到工具
• 幸运的是这个topic已经有研究&＃xff0c;通过已经有研究过的课题&＃xff0c;熟悉工具和解决方法的思路&＃xff0c;才能更好地去解决其他问题

实战代码&＃xff1a;https://github.com/pascallin/NRP-solver