摘要: 作业车间调度问题(JSSP)包含“设备分配”和“工序排序” 2 个相互耦合的子问题,目
前的研究主要集中于工序串行的小规模问题。如果工序之间还存在并行、甚至嵌套等复杂关联
约束,则可行域性状非常复杂,当规模较大时,甚至难以求得可行解。针对以上难点问题,在
分别发挥遗传算法求解“分配问题”和蚁群算法求解“排序问题”的优势基础上,提出了二级嵌套
模型及其基本思路。通过一系列改进策略,如:基于工序的整数编码策略、基于设备类型的多
节点交叉策略、设备类别区间内基因互换的变异策略、基于逆向遍历的可行路径形成策略、基
于最短加工时间的信息素播洒与更新策略等等,构造了集成遗传算法与蚁群算法于同一循环体
的二级嵌套混合算法。针对中等规模问题,分别采用遗传算法、蚁群算法、二级嵌套蚁群算法、
遗传算法与蚁群算法相结合的二级嵌套混合算法,进行了对比试验研究。结果验证了所提算法
的可靠性和优越性,为求解包含复杂关联约束的JSSP 提供了新思路和新方法。