流水车间批量流调度问题求解方法研究

批量流是实现最佳生产技术的一种有效手段,能够缩短机器等待闲置时间,降低在制品库存,加快工件在生产过程中的流动。流水车间批量流调度问题是经典流水车间调度问题的扩展,也是最困难的组合优化问题之一。该问题具有重要的实际意义和理论价值,引起了越来越多的学者和技术人员的重视。论文以入侵性杂草优化算法(Invasive Weed Optimization algorithm, IWO)和人工蜂群算法(Artifical bee colony optimization, ABC)为主要技术手段,对流水车间批量流调度问题进行深入研究,提出了与问题特征有机结合的高效智能优化调度算法。 针对等量分批流水车间批量流调度问题,建立了数学规划模型,运用IWO和ABC分别优化最大完工时间和总流经时间。首先,采用基于加工批次序列的编码和针对批次序列的操作算子,设计了IWO和ABC的新解产生方法,使之作用于离散域,直接产生可行邻域解,得到了离散IWO(Discrete IWO,DIWO)和离散ABC (Discrete ABC, DABC)。然后,基于启发式算法提出了一种初始化方法,该方法能够产生质量高、分散性好的种群,为DIWO和DABC提供了好的搜索起点；基于邻域解的相似性和问题特征设计了一种插入邻域快速评价算法,有效地降低了邻域搜索的时间复杂度；分析了DIWO和DABC的优化机理,从新解产生、选择算子、进化机制等方面提出了改进算法性能的措施,并嵌入局部搜索算法来增强算法的局部搜索能力。最后,采用ANOVA和试错法对所提DIWO和DABC进行参数标定。大量的仿真试验结果表明,所提算法在解决等量分批流水车间批量流调度问题上显著优于相关文献中的其他智能优化方法。 针对批次内零空闲等量分批流水车间批量流调度问题、机器零空闲等量分批流水车间批量流调度问题、零等待等量分批流水车间批量流调度问题和序列相关准备时间的等量分批流水车间批量流调度问题,分别建立了数学规划模型。采用DIWO和DABC分别优化最大完工时间和总流经时间。针对问题的不同特征,设计了DIWO和DABC的操作算子、解码方法和插入邻域快速评价算法,使之能够求解不同的调度问题。仿真试验表明了所提算法的有效性和优越性。 针对流水车间批量流集成调度问题,同时考虑批次分割和批次排序,提出了一种数学规划模型。以最小化最大完工时间为目标,设计了一种改进DIWO集成调度算法。采用分段编码方法表示批次分割和批次排序两个子问题。针对批量分割部分,设计了±1变异和随机变异两种邻域算子。针对批次排序部分,设计了插入操作、互换操作和随机操作三种邻域算子。研究了六种不同的邻域解产生方式和提高算法局部搜索能力的方法。提出了一种改进DABC集成调度算法优化总流经时间,引入一个新的控制参数平衡雇佣蜂和观察蜂的搜索能力,改进了侦察蜂的随机搜索策略以引导算法向优良区域探索。仿真试验证明了所提算法的有效性。 在算法研究的基础上,根据某汽车发动机公司连杆加工车间的生产过程,分析了实际存在的流水车间批量流调度问题,将所提算法应用于实际生产,验证了所提算法的可行性和有效性。 最后,对全文所做的工作进行了总结,并对未来的研究方向进行了展望。