论文部分内容阅读
随着市场竞争的日趋激烈,每个企业都在寻求更好的生产与运作管理方案,以提高企业的生产、经营和管理效率,从而提高企业的核心竞争优势。生产与运作管理的核心是车间调度问题能否高效地获得优化解,研究车间调度问题具有很大的理论意义和现实价值。车间调度问题是解决如何按时间的先后分配资源来完成不同的生产任务,使预定目标最优化的问题。作业车间调度(Job-Shop调度)问题是许多实际车间调度问题的简化模型,是一个典型的NP-hard问题。该问题具有约束性、非线性、不确定性、大规模性等复杂性,已被证明在多项式时间内得不到最优值。近年来,对于Job-Shop调度问题求解方式主要有启发式算法和元启发式算法,但各有其不足之处:元启发式方法的运行时间长,可获得较好的解,但其解不稳定;启发式方法可在较短的时间内得到鲁棒性较强的解,但是极少获得较优的解。为了更好地解决作业车间调度问题,将一些解决某类问题较好的算法组合起来。遗传算法具有快速随机的全局搜索能力,但对于系统中的反馈信息利用却无能为力,当求解到一定范围时往往做大量无为的冗余迭代,使得求精确解效率降低。蚁群算法是通过信息素的累积和更新收敛于最优路径上,具有分布式并行全局搜索能力,但初期信息素匮乏,求解速度慢。本文根据遗传算法和蚁群算法的特点,尝试将两个算法动态融合来求解Job-Shop调度问题。算法动态融合的思想是:在最佳点(遗传算法和蚁群算法融合时刻)之前利用遗传算法的特性,快速、全面地生成优秀染色体;从其中选出一部分比较优秀的染色体并将其转换为初始蚁群算法的信息素分布;在最佳点之后利用蚁群算法的正反馈性、高效性求取车间调度问题的最优解。最后,本文针对Job-Shop问题中经典问题的FT类和LA类的部分问题进行实验仿真计算。结果表明遗传蚁群混合算法的收敛率更高,具有更好的全局收敛性能,遗传蚁群混合算法在更少的迭代次数达到全局最优解,具有更高的收敛速度。