排班问题 | 您所在的位置:网站首页 › 航班排班时间怎么算 › 排班问题 |
文章目录
背景
问题调研
工具查找——找巨人的肩膀
Action
Code example
or-tools的基本用法
参数调整
画甘特图
总结
背景
上次周末碰到女朋友在排班表,花了快一个小时,就想着看用代码帮她节省点时间。 问题调研上网查了一下,看了几篇论文了解了背景。 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1030.5363&rep=rep1&type=pdf https://arxiv.org/pdf/1804.05002.pdf 排班之类的问题都统称为 Nurse Rostering Problem(NRP)问题,就复杂性而言,这是一个NP-hard问题 P问题是在多项式时间内可以被解决的问题,而NP问题是在多项式时间内可以被验证其正确性的问题 多项式时间指的是什么?我理解就是平时计算的算法复杂度 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问题的描述可以看看我找到的这篇文章 提及复杂性理论,是因为更精准地分析问题后,才能找到合适的工具。 这类问题我们就会想到用计算机科学里面的方法去处理,例如machine learning。 工具查找——找巨人的肩膀机器学习的技术栈,我学过的就是Python中的scikit-learn、TensorFlow和Keras上去做选择 据我了解,这是一个研究了多年的课题了。既然这样,应该是会有现成训练好的模型去做这类事情。 最后的最后,我就找到了Google开发的OR-Tools(Official Site)。它已经有训练过的模型去处理这类排班问题了。 Action Code example官方例子Source Code 主要就是对源码做调整了,以满足现实需求。 or-tools的基本用法摘抄的伪代码,用于了解工作方式 // 选择和定义一个model,然后设置所需的前置数据和限制条件 model = cp_model.CpModel() model.NewBoolVar(...) model.AddExactlyOne(...) model.Add(...) // 选择和定义一个solver,然后针对model进行optimizate solver = cp_model.CpSolver() status = solver.Solve(model, solution_printer) // 创建一个矩阵进行拟合 work = { } for e in range(num_employees): for s in range(num_shifts): for d in range(num_days): work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d)) // 下面是打印结果的算法 if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print |
今日新闻 |
推荐新闻 |
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 |