关键词:
作业车间调度
柔性作业车间调度
工艺规划与作业车间调度集成
群体智能算法
蚁群算法
差分进化算法
人工蜂群算法
多目标优化
摘要:
柔性作业车间调度问题是著名的NP-hard组合优化问题。由于减少了机器的约束,所以比传统作业车间调度问题的复杂性更高。同时,柔性作业车间调度问题更接近于实际的制造业情况,具有很强的工业背景。此类问题的复杂性、求解的困难性和应用的可行性使该问题一直都是学术界和工程界的热点问题。
本文针对具有不同约束条件的柔性作业车间调度问题,分别建立了数学规划模型,研究了问题的动态运行规律和结构特性,探索了蚁群算法、差分进化算法和人工蜂群算法解决调度问题的关键理论与技术,从车间调度问题的优化方法和优化目标两个方面进行了深入研究。在优化方法方面,提出了一系列具有创新性的优化调度方法,并设计了多种高效的改进群体智能优化算法。在优化目标方面,分析了柔性作业车间调度和工艺规划与作业车间调度集成的多目标优化问题,建立评价指标体系,从多方面改进多目标群体智能优化算法,进一步增强柔性作业车间调度优化方法的实用性和有效性。取得的主要成果如下:
1.针对作业车间调度问题,采用具有全局收敛性的混合蚁群算法求解。提出了关键工序的概念,在此基础上设计了一种基于关键工序的邻域结构,从而减小了邻域的搜索空间,使邻域空间更优,避免了无用的搜索,使搜索过程向着更优的方向进行。然后,将基于关键工序邻域选择策略的禁忌搜索算法嵌入蚁群算法。利用禁忌搜索算法较强的局部搜索能力,提高了蚁群算法的开发能力,改善了作业车间调度问题解的质量。运用马尔科夫链理论证明该混合算法具有全局收敛性。最后,通过对13个Benchmarks难题进行测试,验证了该混合算法是一个求解作业车间调度问题的有效方法。
2.针对柔性作业车间调度问题,采用动态多种群差分进化算法求解。设计了一种多目标多规则Giffler&Thompson算法,实现初始种群的构造;提出一种新颖的变异、交叉、替换算子,实现个体在优化过程中信息的交换和利用;采用聚类划分方法,将整个种群划分为若干个子种群,并根据搜索到的反馈信息动态调整子种群大小;提出了两个新的搜索方程,设计了一种动态多种群策略,为每个子群分配具有不同特性的搜索方程,并根据每种方程生成保留候选解的成功率动态调整每种方程的选择概率。最后,通过对15个Benchmarks难题进行测试,验证了该算法优于相关文献中的智能优化算法。
3.针对工艺规划与作业车间调度集成问题(即,具有不加工路径的柔性作业车间调度问题),采用自适应多策略人工蜂群算法求解。设计了一种三向量结构的编码机制,以及相应的邻域结构,实现在搜索空间中直接生成可行解;提出了基于改进Giffler&Thompson算法的解码方案,解决了上述编码机制在解码过程中出现不可行解的问题;设计了两个新的搜索方程并有机组合,实现对探索和开发的动态调整,解决人工蜂群算法开发性不足的问题,在保证其探索性的基础上增强开发性;构建面向目标特性的局部搜索策略,进一步提高算法对不同优化目标的开发能力。最后,通过对24个Benchmarks难题进行测试,该算法优于相关文献中的智能优化算法,并具有很强的多目标搜索能力。
4.根据排产优化调度系统的需求,设计了面向服务的软件架构。提出一种聚类方式对排产优化调度软件进行重构,以纵切的方式提取基于调度功能的核心业务关注点模块,进一步提高系统的通用性;为构建面向切面的调度系统构件库,设计了一种采用面向切面技术横切业务模块的方法,实现调度系统的横切关注点构件化,提高代码的可重用性。以上技术已实际应用到某军工企业的“智能部装单元生产管理系统(MES)—计划排产子系统”。