论文部分内容阅读
作为当代制造业生产系统中的核心内容和关键技术,车间调度对制造系统性能有着极其重要的作用。合理且高效的调度策略能够极大的提高制造企业的生产效率,进而增强制造企业的市场竞争力。多数的生产调度问题较为复杂,是典型的NP-hard问题。而随着问题规模的不断增大,传统的方法已经无法满足实际生产中的需求。因此,对于车间调度问题理论的研究以及对有效的调度方案的设计仍然是本领域的研究热点。生物地理学优化算法(Biogeography-based Optimization,BBO)是一种受生物地理学理论启发而得的新型群体智能优化算法。BBO算法因其独特的运行机制、相对较少的参数以及较强的局部搜索能力等优点受到了广泛的关注。本文针对BBO算法进行了深入的研究,并通过理论和实验分析了BBO算法的优缺点,针对不同的车间调度问题对BBO算法进行改进,平衡了算法的全局搜索能力和局部搜索能力。本文的主要研究内容如下:(1)针对标准BBO算法在函数优化问题中探索能力较弱且过度依赖坐标系的问题,本文提出了一种基于两阶段迁移模型的差分生物地理学优化算法(Two-stage Differential Biogeography-based Optimization,TDBBO)。在TDBBO算法中,首先通过两阶段迁移模型维持进化早期的种群多样性并在进化后期加快种群收敛速度。其次,针对算法过度依赖坐标系的问题,设计了改进的迁移算子并将其用于增强算法的旋转不变性。并引入了高斯变异算子使得种群能有效地跳出局部最优解。最后通过引入贪婪选择策略加速收敛。此外,本文还应用Markov模型对TDBBO算法的全局收敛性进行了分析。在CEC2017标准测试函数上的实验结果表明,相比于一些先进的BBO算法的变体,TDBBO算法具有更快的收敛速度以及更高的精度。(2)针对零等待流水车间调度问题(No-wait Flow Shop Problem,NWFSP),设计了一种混合生物地理学优化算法(Hybrid Biogeography-based Optimization with Variable Neighborhood Search Mechanism,HBV)进行求解。在HBV算法中,首先使用MNEH和NN机制产生较优的初始种群。其次,将路径重定向技术和基于块的自我提升策略嵌入到迁移算子来加快HBV算法的收敛速度。并且设计了基于迭代贪心算法(IG)的变异算子探索潜在的搜索区域,最后应用基于块邻域结构和插入邻域结构的变邻域搜索策略对每一代最佳的候选解进行局部搜索。此外,运用Markov模型对HBV算法的全局收敛性能进行分析。仿真结果和统计分析表明HBV算法在求解NWFSP问题是具有较高的效率和较好的精度。(3)针对经典的作业车间调度问题(Job Shop Scheduling Problem,JSSP)设计了基于反向学习和模拟退火的生物地理学优化算法(Oppositional Metroplis Biogeography-based Optimization,OMBBO)。首先使用最小值编码规则(Smallest Position Value,SPV)将JSSP问题域转换为连续问题域,并运用活动调度解码规则计算makespan以缩减搜索空间。其次,使用混沌理论和反向学习策略初始化种群。并引入了改进的迁移算子和高斯变异算子增强标准BBO算法的全局搜索能力。此外,设计了基于模拟退火的接收准则控制种群的多样性。最后使用基于关键路径的变邻域搜索在全局最优解的附近进行搜索。仿真结果表明OMBBO算法显著优于经典的JSSP算法。