获取更多资讯，赶快关注公众号(名称：智能制造与智能调度，公众号：deeprlscheduler)吧！

0 为什么要分级

柔性作业车间调度问题(Flexible job-shop scheduling problem, FJSP)是传统作业车间调度问题(Job-shop scheduling problem, JSP)的扩展。在作业车间调度问题中，每道工序仅能选择一台设备加工，加工时间也是固定的，调度只需要确定工序的先后顺序。而在求解柔性作业车间调度问题时，每道工序可以有多台可选设备，并且在不同的设备上加工时间也可以不同，这就增加了调度的柔性和问题的求解空间，因此柔性作业车间调度更符合实际生产需求，是亟待解决的一类调度问题。

在智能制造生产环境中，因其规模大、目标多、约束复杂、扰动频繁等特点，希望将所有因素考虑到自动计算中非常困难，因此调度人员往往不太相信计算机的自动计算结果，而调度人员可以整合所有实际因素，根据已有的经验知识，确定任务批次的同时，将任务优先或禁止安排在某些设备，并设置希望完工的里程碑节点等，通过这样的设置来干预调度结果。如果能将这些经验和偏好作为约束嵌入到调度优化算法中，既保证了调度人员的意愿又能得到一个较优的调度结果。但是目前研究大多解决的是经典的FJSP标准问题，并没有将调度人员的偏好和经验作为约束融合到算法中，因而无法满足实际调度问题的需要。

因此分级的目的就是实现将交互式操作与自动优化相结合，人的智能与机器智能相集成，在满足多重约束的前提下优化调度结果。

1 分级调度策略

将采用人机交互约束设置进行调度优化求解前的预处理，提出一种适应于柔性作业车间的两级调度求解策略。

第一级：结合灵活的交互式约束设置手段，利用基于优先级的规则算法快速获取满足交互约束的可行解，调度人员可以依据对可行解的分析，不断调整约束设置，直至得到较为满意的调度结果然后进入下一级的优化求解。

第二级：在第一级的数据、边界、约束进行了充分设置后，已经对部分决策变量的取值进行了约束设置，降低了问题求解的搜索空间，并得到具有一定质量的初始解。在此基础上，智能优化算法以基于优先级的工序编码和基于偏好的设备编码对工序进行分派，利用算法的进化策略，不断更新工序的优先级和设备选择，使得结果收敛于最终结果。

2 基于优先级的启发式分派算法

2.1 人工干预策略

调度员的经验和偏好通过人工设置约束而影响调度结果的方式体现，约束的设置如表1所示。

2.2 基于优先级的任务分派

基于优先级规则的任务分派方式主要计算过程如算法1所示。

3 基于约束的智能优化算法

在第一级中的调度构造中，工序任务是按照固定规则得到的优先级高低确定分派顺序的，虽然这些规则可以很容易地被调度人员理解和接受，且在实际生产中也有一定的合理性，但这个过程因其短视性并不一定能得到一个性能较优的解，实际上也没有进行优化搜索，所以在第二级中需要利用智能优化算法，对工序直接采用优先级编码，对设备则采用整数编码表示设备在工序可选设备集合中的序号。利用第一级中满足交互约束的调度构造方法进行解码，快速得到调度方案并进行目标评估，通过迭代对工序优先级数值进行优化搜索，从而实现满足交互约束的调度优化求解。

3.1粒子群-遗传混合算法

粒子群算法主要通过粒子间的位置和速度来更新自己，故求解速度很快，但其寻优能力主要来自粒子之间的相互作用和相互影响，粒子本身没有变异机制，从而PSO容易陷入局部最优解，导致算法的收敛精度不高。而遗传算法利用交叉和变异算子对解空间进行搜索，交叉算子组合了父辈个体的特征，是产生新个体的主要途径，它和选择算子相集合，构成遗传算法中交换信息的主要方法，同时也加强了其全局搜索能力。因此将粒子群算法与遗传算法相结合，利用粒子群中信息的处理模式和遗传算法中的遗传操作，提出一种改进的混合算法（Modified Segmented Encoding Based Particle Swarm Genetic Algorithm,简称MSE-PSGA）。

MSE-PSGA算法的流程主要是对遗传算法的个体数据结构和交叉方式进行改造。根据粒子群算法的个体数据结构，MPSGA算法也在个体的数据结构中添加个体经验信息，来保留个体在搜索过程中的最优适应度及其编码；粒子群算法在迭代过程中，个体更新受到自身经验和群体经验的双重影响。同样，在MSE-PSGA中也设计了一种保留自身经验的方式的交叉算子，使得这种交叉操作不仅可以融合其他粒子的信息，也可以融合该粒子的自身经验信息。

具体算法流程，添加公众号后回复“分级调度”查看。

4 实验结果

为了验证分级调度策略的可行性，首先对比分析了在随机样本下MSE-PSGA与其他算法的计算结果，然后针对具体案例说明分级调度策略的调整和优化过程。

具体实验结果，添加公众号后回复“分级调度”查看。

5 结论和展望

本文提出了一种适用于复杂作业车间调度中具有复杂约束和调度员参与求解需求的两级调度求解策略，在第一级求解中利用了满足多重约束环境的基于优先级规则的快速调度构建算法，作为调度人员交互式约束调整的快速响应求解算法。在第二级调度中以基于工序优先级的快速调度构建方法为目标评估的函数，利用MSE-PSGA混合算法对优先级数值进行优化和设备选择进行搜索,实现了满足第一级调度中设置的多重约束的优化求解算法。该方法较好地融入了调度人员的经验知识和偏好，反映了调度人员的交互操作，增加了调度求解结果的可信度，另外结合了优化搜索求解算法，使得调度求解结果更加具有合理性和优化性。该方法已在多家航空制造车间进行了应用验证，取得较好的应用效果。

随着传感器、RFID数据采集技术的发展以及CPS等先进理念的提出，通过集成先进的感知、计算、通信、控制等信息技术和自动化技术，可以实现“信号-数据-信息-知识-决策”，因此未来的研究将着重考虑如何根据车间内自动获取的信号，通过提取、分析得到真实的状态，进而自动决策影响调度。