复杂的排班问题
我曾经做过一个复杂的排班系统，企业里有近万名员工，分成近百个团队，团队规模从10-500人不等。他们需要24小时轮班工作，每一个团队都有多个班次，最常见的是 早班、常班、晚班、小夜班、大夜班，每个团队都有自己的月度班表。在长达1个自然月的排班表里需要满足一些规则：
通用规则（示例）
1、每个时间段需要的排班人数能够满足业务的需求，比如11月1日早班必须要超过8个人；
2、女生不上大夜班；
3、任何人不允许连续休息超过2天；
4、任何人不允许连续工作超过6天；
5、两个连续班次之间休息超过8小时；
6、所有人在1个自然月内休息天数接近平均值；
7、每个男生在各个不同班次数量接近平均值，比如所有男生的大夜班数量都是3；
8、每个女生在各个不同班次数量接近平均值，比如所有女生的大夜班数量都是11；
9、两个不连续的休息日之间至少工作3天；
10、两个不连续的休息日之间班次尽量相同；
11、小夜班最多连续上3个；
12、每个人每月休息至少9天；
13、两个大夜班至少间隔4天；
14、A 同学在本月 3、4、5、6、7 请了5天年假；
…
特殊规则（示例）
1、A 同学在特定日期一定排 早班；
2、A 同学在特定日期一定不排 早班；
3、由于 A同学和 B同学住在一起，所以 A 和 B 两位同学在所有排班日期班次都要相同；
4、由于 A同学和 B同学关系不好，所以 A 和 B 两位同学在所有排班日期班次都不能相同；
5、某个班次的所有在班人员，男生必须占 50%以上；
6、某个班次的所有在班人员，熟练员工必须占 50%以上；
7、A 同学的班次必须是 早-晚-小夜-大夜-休息-休息 这样循环组合；
...
一个团队的排班规则一般都有 20-30 条，如果按照 50人 30天的班表，系统需要计算1500个单元格，同时受到 20-30 条规则约束，技术上是非常复杂的。
还有一个更头疼的问题 —— 规则之间互相冲突，比如下面3条规则就互相冲突了；
1、任何人不允许连续休息超过2天；
2、A 同学在本月 3、4、5、6、7 请了5天年假；
3、所有人在1个自然月内休息天数接近平均值；
规则和规则之间存在网状冲突，20条规则也许存在上百个冲突的case，也就是说，很多排班的计算不存在“可行解”。在真实的排班过程中，排班人是很灵活的，他有一套潜意识中的规则优先级，会下意识判断每个冲突发生的 case 如何解决，也许在不同的单元格，对同一种 case 的处理方式不一样，所以一个熟练的排班人可以快速地手动排出班表。不过公司很难批量培养这种人才，所以希望用系统来解决这个问题。
复杂班表示例
我们的算法同学很给力，前后做了几种解决方案，最后在理论上我们发现遗传算法是最佳解决方案。遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。排班本质上是一个多约束条件下寻求最优解的问题，系统用遗传算法是可以很好解决的。
用遗传算法解决排班问题
我们首先要建立评估体系，一种是局部评估，一种是全局评估。
每一条排班规则都是一个局部评估单元，比如“女生不上大夜班”是一条约束条件，系统会检测当前班表中有多少个违反次数。如果在1500个单元格中违反1次，那么满足度就下降 0.67%，只有99.33%，违反越多，这一条规则的评分越低。
假设我们的班表有10条规则，每一个规则都是一个局部约束条件，存在各自的局部评估值。而全局评估就是每一个局部评估加权平均之后的值，如果每1条规则的权重都是均等的，那么把10条规则的局部评分值加总除以10即可。
但在实际的业务中不同规则是有权重的，比如 “女生不上大夜班”比“小夜班最多连续上3个”更应该遵循，所以前者的权重应该大于后者，甚至要“一定实现”，它的局部评估值必须是100%，不可以被违反。排班人员在列出20条规则的时候，是能够判断出规则优先级偏好的，他需要告诉系统每条规则的权重值，比如权重的范围是 1-10 分：
在建立好评估体系后，系统首先会随机在1500个单元格中给出一个班次值，成为 g1（generation），即第一代的初始结果，系统会计算 g1 初始结果的局部评估值和全局评估值，如下表：
我们会发现初始结果是29%的整体满意度，在此基础上，系统会随机改变单元格中一些班次，变成 g2，然后对 g2 进行评分，如果分数小于或等于 g1，那么系统会在 g1 的基础上做出另一次改变，如果 g2 的分数比 g1 高，则会在 g2 的基础上继续迭代下去，无穷代遗传之后，会达到一个不可以再优化的最优解，我们一般在10万次计算内可以得到最优解。
排班系统设计
这个最优解不一定是可行解，当排班规则之间存在冲突，不能同时有满足所有条件，那我们只能得到一个不是可行解的最优解。下图是遗传算法的一个示例
遗传算法图示
在引入遗传算法之后，我们发现只要任何一条排班规则是可以被语言描述，并且可以进行量化评估，那么系统一定能给你排出最优解班表来，采用遗传算法在战略上就几乎立于不败之地了。
引申到现实生活
遗传算法对我的影响很大，不仅仅是对于排班这个项目本身，它对于我们生活中常见的“多约束条件下寻求最优解问题”提出了解决方法。
其实我们在工作和生活中经常会纠结一些事情，下一步到底该怎么做？这样做会不会捡了芝麻丢了西瓜？那样做会不会更好？这样会导致三种问题：
1、决策时间过长，外部环境不断变化，失去了最佳决策机会；
2、放弃决策，维持现状，选择保守的方式对待风险；
3、做了决策后没有信心，太容易知难而退；
也许这样写，大家不是很有感触，我们反过来看，如果做到这样是不是很有吸引力呢：
1、决策时间很短，每次都抓住了关键机会；
2、不害怕决策，积极寻求拥抱变化；
3、做了决策后非常有信心，坚持到底，每次都达到了预期效果；
我想大多数人都希望做到以上三点，不过在现实生活中我们经常瞻前顾后，没有做到这样。就像我们手工排1个大班表，每次在新的单元格写下一个班次，都要前前后后计算违反了哪些规则，我们要填完1500个单元格，但是每1个单元格都有几种填法，我们很担心填了一个单元格导致新增加几十个冲突，所以我们明知填好1500个单元格就是走到终点，但是不敢走。更可怕的是，很多事情我们会花大量时间研究如何走第一步，然后就放弃了。
遗传算法的告诉我们可以从另一个角度思考问题：
1、通过可量化的指标定义一个事务好坏的评估体系，即使是多个互相冲突的目标也是可行的；
2、随机选择一个“不太差”的方案去做，得到第一步结果；
3、在第一步的方案基础上做一些改进尝试，得到一个指标优于第一步的第二步结果；
4、不断迭代、优化、积累，时间久了就会趋向于最优解。
以前玩《植物大战僵尸》的时候有一个无尽版，玩得好不好的衡量标准就是谁能挺过更多的关卡数，当时网上出现了很多教程，有玉米加农炮流、西瓜投手流等等，不过从大家的实践来看，最终都会趋向于固定的某种阵型，它就是最优解。
8个玉米加农炮阵型
一个新手玩家是很难直接计算出使用这种组合是最优解，但是当他不断尝试方案、迭代阵型之后，是能够找出最优解的，遗传算法。
