论文部分内容阅读
Job Shop调度是计算机集成制造系统(CIMS)工程中的一个重要组成部分,它对企业的生产管理和控制系统有着重要的影响。同时,Job Shop调度问题(Job Shop schedulingproblem,JSP)又是一个典型的NP Hard问题,是组合优化问题中最难求解的问题之一。将优化方法的理论研究引入到Job Shop生产调度领域中,改进算法性能、拓宽算法应用领域,完善算法体系,是一个同时具有理论意义和应用价值的课题。本文分析总结了一些现有的调度算法,针对它们的不足,基于免疫理论和遗传算法,设计了一种新颖的自适应混合免疫遗传算法SIGA(Self-adaptive Hybrid Immune GeneticAlgorithm)。为了更有效地求解JSP,基于SIGA提出了改进的调度算法SIGAⅡ。本文的主要工作如下:1.针对传统免疫遗传算法存在过早收敛及后期搜索效率低的问题,提出一种基于浓度的自适应混合免疫遗传算法(SIGA),该算法有效融合多种群遗传算法与模拟退火算法的优点,同时在算法中引入生物免疫系统中抗体多样性的维持机制,提出了基于浓度的自适应交叉变异算子和选择策略,通过仿真实验,证明了算法的有效性;2.将该算法应用于求解JSP,给出了一种基于免疫遗传算法的求解方法,以及染色体的编码方法和相应的免疫遗传操作,针对Job Shop调度问题的特殊复杂性,本文将转换瓶颈算法(Shifting Bottleneck)和禁忌算法(Tabu)两者相结合,提出了一种瓶颈禁忌算法(STA),并将瓶颈禁忌算法引入SIGA中,提出改进的自适应混合免疫遗传算法(SIGAⅡ),加强算法在求解JSP的局部搜索能力,从而进一步提高算法的性能。3.通过对JSP中的经典Benchmarks算例问题进行仿真实验,系统地分析了一些关键参数和算子对算法性能的影响,结果证明改进的自适应混合免疫遗传算法优于其他四种算法,具有更好的全局收敛性能。最后将SIGAⅡ应用于实际的生产调度,满足企业的生产需求,验证算法的实用性。