论文部分内容阅读
流水车间是一类典型的混合生产线系统;这类混合生产线系统的相关调度问题,即排序流水车间调度问题(PFSP),广泛存在于制造企业中。随着需调度工件数目的增加,该类问题求解空间的可行解数目将呈现指数式的增长;显然,这类问题是典型的NP问题,所以这类问题是理论研究最为困难的问题之一。基于“总的加权延迟”最小化优化准则下考虑工件顺序依赖准备时间的PFSP问题(SDST-PFSP-WT)和基于制造期最小化优化准则下的零等待PFSP问题(NWPFSP)是分别在一个具有现实优化意义的优化准则下、考虑一个广泛存在的现实约束条件的两个PFSP问题。本文首先研究解决的就是这两个调度问题。多品种、中小容量的混合柔性生产线系统(FMS)当前广泛应用于制造企业中。因为具有工件传输路径柔性、生产节点服务方式柔性及服务选择柔性等共性特征,所以该类型生产系统能够满足企业多品种产品生产的目的。由于购买设备配置一个FMS系统需要花费企业大量的资金成本,所以优化布局这类系统是企业决策者需要重点解决的一个资源调度问题。FMS系统性能分析问题是FMS系统布局优化问题一个重要的基础子问题,数值仿真技术是解决这一基础问题的主要技术手段及方法。针对该类型生产系统的共性特征及面临的共性问题,本文研究解决了FMS系统数值仿真关键技术问题。本文主要的研究内容如下所示:针对SDST-PFSP-WT问题,经过调研国内外相关研究文献发现:插入搜索是一种高效的局部搜索算子;NEH_EWDD启发式算法及迭代贪婪智能算法(IG)分别是当前解决该问题最好的启发式及智能算法,并且上述两个算法都是基于插入搜索实现的。基于插入搜索,本文首先提出了一种有效的回溯算法及启发式算法(HPIS);并且,在此基础上,本文提出了两种具有较高算法性能的基于NEH_EWDD的启发式算法(NEH_EWDD_HPIS和NEH_EWDD_HPIS_ACC)。其次,基于综合上述提出的所有算法或方法,本文对IG算法进行了改进。最后,经过基准实验测试发现:提出的两种基于NEH_EWDD的启发式算法及改进的IG算法在性能上远优于相应的原始算法。针对NWPFSP问题,本文提出了一个混合IG算法解决该调度问题。首先,为了获得具有更好性能的初始解,本文进一步改进了提出的NEH_EWDD_HPIS算法,并将这改进的启发式算法作为混合算法的初始化方法。此外,本文提出了一种基于“块”的解“破坏“策略,并且引入了已经被其它作者证明在解决当前问题中比较有效的基于禁忌的重构方法。此外,本文提出了一种高效的、混合变邻域下降及变邻域搜索等两种搜索策略的局部搜索算法,该算法集成了插入移动搜索、置换移动搜索及块插入移动搜索等三个当前已被证明在解决该问题中比较有效的局部搜索算子。最后,实验证明:提出的算法在性能上优于当前存在的最有效算法。针对复杂FMS数值仿真关键技术问题,在分析这类系统所具有的共性特征及面临诸如工件传输阻塞、工件路由选择及设备多处理选择等共性问题的基础上,本文提出了一种基于拓扑及面向事件的FMS数值仿真技术。基于该数值仿真技术所实现的FMS数值仿真系统能够实现较通用的仿真具有路径柔性、服务方式柔性及服务选择柔性等柔性特征的一类FMS系统。