目前作业车间调度比较常用的方法有：基于规则的启发式算法、遗传算法、蚁群算法、粒子群算法、蜂群算法、以及将各种算法机制相结合形成的混合算法等等。其中，遗传算法与蚁群算法是应用较多的两种算法。

遗传算法主要通过改进编码方式或改进适应度设置方法来进行优化，如Driss等提出一种采用新的染色体表达方式的遗传算法，并在一系列基准数据集的基础上进行了验证。蚁群算法主要有一阶变量和二阶变量两类或衍生改进的算法。如Zhao等提出了一种用于灵活处理路线决策和任务排序的两代帕雷托蚁群算法，来生成一个可行的调度方案。混合算法通常是将另一个算法的机制融合到主算法中，对主算法进行改进，如混合遗传算法。

虽然这些算法在求解JSSP方面有较多成果，但也存在一定的局限，如调度规模较小，工序关系主要以串行为主等，对存在串行、并行、甚至嵌套关系的复杂关联约束调度问题，研究还比较少。JSSP求解时搜索范围之所以庞大和复杂，是因为其设备分配和工序排序之间有复杂且紧密的相互干涉，导致较低的搜索效率和收敛可靠性。尤其当问题规模较大、并且存在复杂关联约束时，其解空间的复杂度呈几何级数上升，这种情况下，即使寻找可行解也有较大的困难。

针对上述问题及难点，本研究以包含复杂关联关系并具有一定规模的JSSP为研究对象，将问题分解为“设备分配”和“工序排序”两个相互耦合的问题，分别发挥遗传算法在求解配置问题方面的优势和蚁群算法在求解排序方面的优势，构造将两种方法集成到一个完整循环体的二级嵌套混合算法，以在可接受的迭代次数内求得比较满意的设备分配和工序排序方案。

2. 研究的基本内容与方案

由于可行域性状十分复杂，求解包含复杂关联约束的作业车间调度问题(JSSP: Job Shop Scheduling Problem)，依然是难点问题。本毕业设计计划将该问题分解为“设备分配”和“工序排序”两个相互耦合的问题，分别发挥遗传算法求解“设备分配”和蚁群算法求解“工序排序”的优势，构造集成遗传算法与蚁群算法于同一循环体的二级嵌套混合算法。

本次毕业设计的主要任务与要求如下：

（1）广泛阅读相关文献，了解国内外现状；

（2）实现基于工序的整数编码策略；

（3）实现基于设备类型的多节点交叉策略；

（4）实现基于逆向遍历的可行路径形成策略；