浅谈计划排程常见算法

“计划排程：Planning and Scheduling，用于几乎所有制造业，尤其流水线。产品越多样化的企业，计划排程就越复杂。不少公司都有自己的工具，利用算法实现排程。今天就浅谈一下算法这个黑匣子。”

作者之前做过一些模拟和实验，采用了三个算法：①爬山算法 ②模拟退火算法③遗传算法，使用了100个产品订单进行试验（试验期间担心订单太多会导致算力不足），本文就来浅谈一下这三个算法的一些规律。

①爬山算法（局部探索、浅尝辄止）

      它的核心在于寻找局部最优解，比如有一片山峰（如图），探险队需要寻找最高的山峰A（最优解），但是探险队出发点位在B，他们经过一段旅程（局部）以后找到了山峰C，于是就停止了寻找。搜寻范围有限，得到的解大概率不会是全局最优解，而是局部最优解。

这种算法在一些公司早期开发的排程项目中得到应用，这些排程系统在相同的目标函数/制约条件下得到的解都不同，而且都不是最好的，但在当时，也算完成了排程工具从无到有的转变。

②模拟退火算法（局部探索、机会主义）

它的核心在于虽然是局部最优解，却会有一定概率在周围随机寻找，尝试找到更优解。还是刚才那个例子，探险队寻找到局部最优解C后，会随机进行寻找更优解，有可能找不到，有可能找到D，比C解更好。

③遗传算法（优胜劣汰、不断进步）

它的核心在于全局寻找最优解，即便第一次寻找不到，它会记住这次失败，并在下一次得到最优解后把第一次的失败经验排除在外，不断成长。还是刚才那个例子，好比在山峰之中的不同地点随机安排了很多探险队，一起寻找，隔一段时间进行对比，淘汰掉一批寻找到次优解的探险队，留下寻找到局部最优解的队伍，并让他们随时在线交流心得，为了在下一次探险中寻找到更高的山峰，最终不断接近全局最优解A。

总的来说，通过实验和模拟，我们发现排程中使用遗传算法效果还是很不错的，但是对算力要求很高，毕竟我们才模拟了总量为100的产品订单，很多企业的产品日产量可远远不止这些。