《面向制造物流路径规划的超立方链接算法研究121214》由会员分享，可在线阅读，更多相关《面向制造物流路径规划的超立方链接算法研究121214（29页珍藏版）》请在金锄头文库上搜索。
1、 面向制造物流路径规划的超立方链接算法研究仁寿一中（北校区） 张与弛1. 绪论.21.2国内外研究现状及发展动态.31.2.1制造物流作业规划与动态调度的研究发展.31.2.2 可重构制造系统的研究发展.3 1.3 本文研究的主要内容.11 1.4项目的研究目标.112. 超立方链接算法的研究.12 2.1 超立方路径链接算法的提出.122.2 超立方路径链接算法的基本思想.13 2.2.1 超立方体及其链接展开图.13 2.2.2 超立方路径链接算法的基本设定.143. 基于超立方路径规划的可重构制造物流组织形态研究.17 4.1 超立方路径链接的物理结构17 4.2 超立方路径链接算法物流
2、组织结构的实现形式.184.本项目的特色与创新之处.225.基于超立方链接算法的车间复杂物流仿真平台的介绍246.总结与展望.246.2 总结.24 6.2 展望.25附录：超立方链接算法程摘 要：为解决具有多变性和极多品种特征的复杂制造系统中物流作业调度控制的实时调度和敏化传导问题，建立了超立方路径动态规划的数学模型，提出了对所建数学模型的求解方法，研究了超立方路径规划的物流传导型模态研究路径，通过实例建立了与物流作业组织形态对应的超立方链接组织模型。相对于已有物流作业调度控制的规划方法，本文建立的数学模型可实现因生产组织重构所要求的路径规划自主性动态传导和生产物料的主动配送。关键词：超立方
3、；可重构；复杂制造；路径规划；动态调度1.绪论1.1问题的提出及研究意义降在当今社会,在航空航天，武器制造，舰船动力，精密机床等高端特种装备的制造系统中，积极引入智能化，规模化，可重构的现代制造理念，已经逐步被人们所接受和重视。然而，现在的高端特种装备极多型号品种，极多精度配合，极多工艺序列等所要求的复杂制造物流配送，已经成为制约其生产组织方式向规模化，可重构化形态转移升级的主要因素，严重影响了系统产能的提高和产品成本的低。例如，仅一种型号的航空发动机控制装置的在制造，所涉及加工，修复的零部件多达数千种，工艺序列有6000多种，工装有3000多套，而更换一种型号品种不仅会引发制造工艺序列的连锁
4、更异，还会带来生产组织形态的重大变化，这就要求车间物流作业执行系统能够实时传导这种变化。因此，具有极多型号品种，极多精度配合，极多工艺序列特征的复杂制造系统如何实现规模化生产的组织方式，以及在可重构，可嵌入物流结构形态中实现生产物料的自组织主动配送，是现代制造系统所面临的新课题，尤其是在高端装备制造领域更是亟待解决的新问题。为此，本文研究，主要面向具有多变性，多重性，嵌套性特征的复杂制造系统的规模化生产组织方式，针对车间物料动态调度，研究面向全域物流作业多任务协同规划调度的超立方路径链接算法理论，为解决复杂制造系统的规模化生产与物料主动配送提供了基本的理论与技术方法。1.2国内外研究现状及发展
5、动态1.2.1制造物流作业规划与动态调度的研究发展制造系统中的车间作业调度包括两个方面，一是把加工任务（或作业集）合理地安排到各个生产单元（如机床，装配，检验，仓储等装置），二是对加工物料（毛坯，共建，工具等）有序地运送到各个生产单元。在现代制造系统的生产组织中，车间作业调度与物料调控是由生产执行系统来完成的。换言之，车间物流作业通常被归并于车间生产作业，并通过生产执行系统的统一规划与调度来完成。生产执行系统的核心任务，就是根据生产资源（物料，机器，传送器等）来合理调配车间作业，并对生产过程进行优化控制和有效管理。从数学规划的角度看，车间调度问题的实质，就是在一定约束条件下对目标函数的优化。在
6、规模化生产发展的初期，并没有作业规划与生产物流调度的概念，对于多品种零件加工的制造过程，更多地是通过长期积累的经验来对各种加工作业进行调控。之所以要进行作业调度1.2.2 可重构制造系统的研究发展制造系统中的车间作业调度包括两个方面，一是把加工任务（或作业集）合理地安排到各个生产单元（如机床、装配、检验、仓储等装置），二是对加工物料（毛坯、工件、工具等）有序地运送到各个生产单元。在现代制造系统的生产组织中，车间作业调度与物料调控是由生产执行系统来完成的。换言之，车间物流作业通常被归并于车间生产作业，并通过生产执行系统的统一规划与调度来完成。生产执行系统的核心任务，就是根据生产资源（物料、机器、
7、传送器等）来合理调配车间作业，并对生产过程进行优化控制和有效管理。从数学规划的角度看，车间调度问题的实质，就是在一定约束条件下对目标函数的优化。在规模化生产发展的初期，并没有作业规划与生产物流调控的概念，对于多品种零件加工的制造过程，更多地是通过长期积累的经验来对各种加工作业进行调控。之所以要进行作业调控，是因为生产作业的任务远远超出生产设备所承受能力，这就是作业调度问题出现的基础。上世纪初，规模化生产的作业调度问题受到重视，人们开始研究各种产品规模化生产调度的问题，但当时的研究只是停留在一些简单的技术方法上，并没有上升到理论层面。直到在1954年，Johnson对两台机床流水作业调度问题的研
8、究，标志着车间调度理论研究的开始。60年代至70年代，是经典调度理论发展的重要时期，许多任务调度算法，如运筹学中的纯整数规划、动态规划和分枝定界法、启发式算法等被用来解决生产作业的调度问题。特别是上世纪80年代以来，许多跨学科的理论方法被引入到该领域研究中，其中最引人注目的就是以卡内基梅隆大学M.Fox教授为代表的学者们所开展的基于约束传播的ISIS研究，这意味着人工智能开始应用于车间任务调度问题。随后，智能调度逐渐成为生产调度研究的主流，代表性的理论技术有：神经网络、Petri网、模糊数学、遗传算法、多代理技术和分布式人工智能技术等，其中分布式人工智能技术与多代理技术在车间调度研究中，已经成
9、为该领域的一个新的发展方向。国内外学界在经典规划调度理论与现代智能调度理论被广泛应用的几种典型技术方法中，我们从所要解决的实际问题来考察，可以窥见这些理论方法的主要技术路径和学术思想数学规划方法在车间调度中广泛应用的数学规划法，是将调度问题转化为NP问题，并用整数规划法、混合整数规划法和动态规划法来描述。由于这种方法的计算复杂性，其应用受到一定限制，后来随着启发式规则的引入以及数字计算能力的发展，才使得这种方法又焕发了活力。在制造系统中应用得最多的数学规划方法是分解技术和枚举方法。分解技术将车间调度分成两层，上层详细说明每个零件加工的开始时间和结束时间，并考虑各子问题之间的约束关系；下层通过对
10、全域工序的规划来细化上述时间限制，并植入各子问题内的约束，进而通过一个数学规划框架来解析生产作业计划。枚举方法又叫分枝定界法，它主要采用整数约束的思想来解决复杂调度的问题，但需要花费大量的处理时间。为克服这一问题，又产生了拉氏松弛法。由于拉氏松弛法在时间约束条件下，对复杂规划问题能提供很好的次优解，并能对解的次优性进行评估，因而成为解决复杂车间调度问题的一种重要方法。人工智能技术（AI）AI调度问题的研究应用研究，是在专家系统和知识技术的基础上发展起来的，其学术思想的特点在于：1）在决策处理过程中采用定性和定量的知识；2）能生成启发式规则，这些规则比分配规则复杂；3）可以在整个车间信息的基础上
11、选择最好的启发式规则；4）能敏锐地获得信息之间的复杂关系。其不足之处在于：开发周期长，成本昂贵，需要丰富的调度经验和知识，对新的环境适应性差等。典型的AI调度方法有：1）专家系统/基于知识的系统，二者由知识库和推理机两部分组成，知识库包括一些规则、过程和启发式信息等，推理机用来选择、处理知识库中的知识，它有数据驱动和目标驱动两种方式，目前实际应用的有ISIS 、OPIS和SONIA等系统；2）分布式AI（智能体），由于单一的专家系统或基于知识的系统所具有的知识与处理能力有限，学者们又研发了分布式人工智能体调度系统，它由任务智能体和资源智能体组成。任务智能体负责处理调度中的各种任务型作业，资源智
12、能体负责单一或某一类资源。为保证任务智能体和资源智能体之间的有序工作，必须建立协同机制，但到目前还没有统一的规范来设计和实施协作。人工神经网络优化神经网络模仿了人类学习以及对事物预测的能力，它是一种并行处理模型。这种模型根据网络拓扑结构、节点特征和训练或学习规则的不同而变化。人工神经网络用于车间调度主要有三种方式：1）利用并行计算的能力，来求解优化调度，以克服调度的NP难题；2）利用学习能力，从优化轨迹中提取调度知识；3）用神经网络来描述调度约束或调度策略，从而实现对生产过程的可行或次优调度。Hopfield神经网络模型的提出，为求解各种有约束优化问题开辟了一条新途径，但这些方法计算效率较低，
13、常常会产生不可解的问题，因此目前还不能应用它来解决实际调度问题。遗传算法遗传算法的基本思想来源于分子遗传学和生物进化论，其基本原理是产生若干代表问题候选解的成员，并组成一个群体，按照某一评价函数或算法对群体中的每个成员进行评估，评估结果代表解的良好性。按照适者生存、优胜劣汰的原则，对群体中的成员进行遗传操作，产生新的后代，它能继承双亲的优势特征。对后代进行评估，并将其放入群体，代替上一代中较弱的成员。此过程反复执行就会得到一代又一代的群体。随着遗传过程的不断进行，可以获得越来越良好的解。研究表明，遗传算法比经典的启发式算法要好，同时遗传算法有更强的鲁棒性。它的优越性在于：1）遗传算法的工作问题
14、是编码，对搜索问题的限制极少，对函数的一些约束条件如连续性、可导性等不作要求；2）遗传算法是同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局部最优而获得全局最优解，与其它单点搜索方法相比，在计算时间上有较大的优势；3）遗传算法进行遗传操作时，是按概率在解空间进行搜索，因而既不同于随机查找，也不同于枚举查找那样盲目的穷举，而是一种有目标、有方向的启发式搜索。离散事件的动态解析模型由于制造系统是一类典型的离散系统，因而可以用研究离散事件的方法来研究调度问题，这类方法主要有排队论、极大极小代数模型、Petri网等，近年来学者们研究得较多是排队网络法和Petri网模型。排队网络法在随机库存系统、随机服务系统和Petri网络系统等三类典型的DEDS中有广泛应用，在车间调度系统，它可以分析系统生产率、平均生产时间等，但它很难将车间全域资源考虑进去，难以处理系统的异常情况。Petri网模型，是DEDS建模事件图技术中应用得最广泛的一类，其的核心思想是把DEDS表示成输入位置、输出位置、转移位置、转移节点和有向弧线连接起来的二元有向图，并建立以位置节点集合P、转移节点集合T，有向弧线集合F为变量的解析函
