基于Petri网和混合遗传算法的双资源车间调度

发布时间：2020-05-31 05:04

【摘要】：生产调度是制造系统的基础,有效的调度方法和优化技术的研究与应用,是实现先进制造和提高生产效益的基础和关键。车间调度是一类典型的生产调度,从数学规划的角度看,车间调度可以表达为:在等式或不等式约束下,优化目标函数。几十年来,车间调度问题的研究得到了快速的发展,然而研究的重点大多集中在单资源车间调度问题,即只考虑机器设备的车间调度问题而忽略了具有操作能力工人的限制。现实生产中为了完成一个工作,往往机器和工人是同时需要的。我们把机器设备和操作工人两个资源都受到限制的车间调度问题称为双资源车间调度问题。车间调度的核心问题是模型和算法,本文则利用Petri网建模,应用混合算法优化求解。Petri网作为一种图形化和数学化的建模工具,与传统的建模、分析和控制方法相比,能够提供一个集成的建模、分析和控制环境,它能较好地描述离散事件的动态过程,为车间调度的设计提供便利。对于混合算法的设计,相关研究表明遗传算法和模拟退火算法在求解大规模复杂调度问题时显示出强大的优势,但也都有其局限性。遗传算法采用群体并行搜索,算法倾向于扩大搜索空间以在大范围内搜索,但其局部搜索能力差,容易过早收敛;模拟退火算法采用串行优化结构,其搜索策略可以避免搜索过程陷入局部最优,但对整个搜索空间的状况了解不多,不便于大范围的搜索。我们通过设计混合遗传算法,整合两种算法的优点,同时又克服两种算法的缺陷。 本文以Petri网和将遗传算法与模拟退火算法相结合的混合遗传算法为工具,对具有多条加工路径的双资源车间调度问题进行研究。通过算例的验证,证明了混合遗传算法的优越性。 本文的主要研究工作可以概括为以下几个方面; 1、用赋时Petri网对双资源车间调度问题进行建模,对所建立的模型进行死锁和资源竞争分析。 2、基于目标函数和Petri网模型,使用变迁的激发序列对染色体进行编码,使得混合遗传算法操作都是对Petri网的基本元素进行操作,和空间元素无关,克服了空间状态爆炸问题。 3、最后以具体的双资源车间调度系统为例进行求解,以c++为工具,实现所提出的算法,对比混合遗传算法和遗传算法的结果,用实验数据验证算法的优越性。
【图文】：

图 5-4 工人与设备关系窗口Fig 5-4 Relation window between workers and machines当然我们通过随机算法设置的工人加工信息和我们现实的需求是有差别的，这里我们引入修改机制，通过一个录入模块如图 5-5 所示，对工人工人的加工信进行修改，通过工人号、机床号和操作信息的录入，添加、修改或者删除工人加工信息。

列代表机床，关系矩阵中的元素为加工关系，1 表示该工人可以操该机器，0 则表示该工人不可以操作该机器。图 5-4 工人与设备关系窗口Fig 5-4 Relation window between workers and machines当然我们通过随机算法设置的工人加工信息和我们现实的需求是有差别的，这里我们引入修改机制，通过一个录入模块如图 5-5 所示，，对工人工人的加工信进行修改，通过工人号、机床号和操作信息的录入，添加、修改或者删除工人加工信息。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2010
【分类号】：TP301.1;TH186

【引证文献】

相关硕士学位论文 前1条

1 杨旭;船舶企业车间作业计划方法与系统[D];哈尔滨工业大学;2011年

本文编号：2689336