论文部分内容阅读
生产调度是影响企业生产效率的关键因素,合理有序的调度可以有效缩短生产周期,提高设备利用率,减少在制品库存和资金占用,从而提升企业竞争力。生产调度种类繁多,方法多样,其中传统的作业车间调度(Job Shop Scheduling Problem,JSP)是最基本、最著名的机器调度问题,同时也是典型的NP-hard问题,几十年来得到国内外学者的广泛研究,促进了大量算法的发展,如遗传算法、禁忌搜索算法、模拟退火算法、移动瓶颈算法、邻域搜索及相关混合算法等。传统的JSP问题只针对产品的加工阶段,不考虑其装配阶段,适用于相同产品的大批量生产。本文研究的产品加工与装配综合调度问题(简称为产品综合调度问题)将加工与装配过程一同考虑,适用于多品种小批量的生产过程,能快速响应社会对个性化产品需求日益增多的情况,其研究具有较强的实际意义。同时产品综合调度问题作为JSP问题的扩展,也是典型的NP-hard问题。JSP问题的研究已经积累了大量的高效求解方法,而产品综合调度问题的研究方法尚不成熟,原因在于产品综合调度问题比JSP问题多了更加复杂的装配约束关系,导致已有的各种编码技术和局部搜索保障技术均失效,因此研究产品综合调度问题的高效求解方法迫在眉睫。首先,本文综述了产品综合调度问题的研究现状,总结分析了现有研究方法的不足,进而提出本文的研究内容。通过分析传统JSP问题中常用的优化目标,并结合产品工艺树给出了产品综合调度问题的数学模型。分别阐述了基本遗传算法和移动瓶颈算法的基本流程与算法特点,为后续遗传算法和移动瓶颈算法的改进研究奠定基础。然后,针对文献中所提基于虚拟零部件级别分区编码方法存在的不足,设计了一种基于工序约束链的编码方法,以弥补其不足之处,并给出了具有工件加工装配顺序约束关系的主动解码方法;针对交叉、变异操作产生的不可行解,设计了一种基于邻接矩阵的修复方法;进而提出一种基于工序约束链编码的遗传算法,实验测试结果验证了所提算法的有效性。其次,为弥补单一算法的不足、进一步提高算法的求解性能,提出一种融合改进扩展移动瓶颈算法和遗传算法的混合求解方法。混合遗传算法采用基于工序约束链编码的遗传算法实现全局搜索,基于改进扩展移动瓶颈算法实现局部搜索。在扩展移动瓶颈算法的改进研究中,给出了产品综合调度问题对应的扩展析取图模型,研究了基于扩展析取图的工序头尾长度计算方法,以及关键工序的查找方法,采用带扰动的Schrage算法求解单机调度子问题,增加了瓶颈机器的选择标准,设计了一种贪婪式的瓶颈机器再优化过程。结合文献中给出的相关算例进行测试分析,验证了所提改进扩展移动瓶颈算法和混合遗传算法的有效性。最后,基于上述理论研究成果,结合实际案例开发了产品综合调度软件原型系统。介绍了原型系统的应用背景、系统开发环境和主要功能模块,通过测试实际案例,简介系统运行过程,验证了原型系统的有效性。