基于Petri网的混流装配线建模与重构优化研究

- I 要 混流装配线是多品种、中小批量制造企业适应 市场需求变化的理想选择。但在实际生产过程中却存在着由于需求的短期大幅 度波动导致的混流装配线产能柔性不足问题。针对上述问题，本文意在寻求一种提高混流装配线产能柔性的重构方法。 本文主要的研究内容和所取得的成果如下： 在对混流装配线的工作站进行分类的基础上，运用面向对象赋时 建立了各类工作站的模型。模型建立时，将 方法与面向对象的建模技术相结合，加入了时间因素，并首次运用一维数组的形式将 时间因素赋予库所。模型建立后，对模型的性质和性能两方面进行了分析。 在对各类工作站的模型进行分析的基础上，提 出了采用平行机制、增加在制品数量和添加瓶颈设备这三种具有不同适应程度 的产能调整方式。每个工作站根据其内部工序间的工艺约束关系不同，其所能采用的产能调整方式各异。 结合工作站的三种产能调整方式，以工作站为 基本产能调整单位，对混流装配线的重构优化问题进行了研究。重构过程充分 考虑了时间、费用、重构后效果等因素，以交货期和费用界限作为重构的约束条件 ，保证订单的完成和重构的效益。以重构后的平衡效果和重构费用作为评选重构方 案的目标函数，其中平衡效果的衡量又综合考虑了负荷的均衡指数和平衡损失。 对上述混流装配线重构问 题进行算法设计，并运用 C+语言编程实现。通过对程序的多次运行，可以快速得到重构问题的最 优解。这一方法既可直接作为混流装配线重构的方案，也可作为混流装配线间线线 平衡和外协加工等其他产能调整方案的参考依据 。 关键词 ：混流装配线； ；建模；可重构 - is of to to in is of In to is to a to of of as a of of of We in of a of of of on of of to in as of of as as to of of as to of a of + of we of in be as a be as of - 录 摘 要 . I . 1 章 绪 论 .题背景及研究意义 . 课题背景 . 课题的研究意义 . 课题来源 .内外研究现状 . 研究现状 . 当前研究的不足 .文研究方法及框架结构 . 论文的研究方法 . 论文的框架结构 . 2 章 混流装配线与 相关理论 .流装配线概述 . 混流装配线的概念与分类 . 混流装配线的特点 .的基本理论 . 的定义 . 的动态性质 . 的分析方法 . 的几种扩展形式 .章小结 . 3 章 基于面向对象赋时 的工作站建模 .模方法的确立 .向对象赋时 的定义 . 系统层定义 . 工作站层定义 . 资源层定义 .究问题的条件假设 .流装配线工作站的 描述 . 混流装配线中事件基本关系和基本模块的 表示 .流装配线中工作站的分类及其 表示 .流装配线工作站的 建模方法与步骤 . 混流装配线工作站的 建模方法 . 混流装配线工作站的 建模步骤 .于面向对象赋时 的工作站建模实例 . 系统介绍 . 确定各资源类模块并建立其 模型 . 确定各工作站内工序间关系和所用资源间的消息传递关系 . 各工作站面向对象赋时 模型的确立 .作站 模型的性质分析 .于工作站 模型的混流装配线性能分析 . 工作站实际加工时间的计算 . 混流装配线的性能分析 .章小结 . 4 章 基于工作站产能调整的混流装配线重构方法 .构方法研究现状 .业当前运用的重构方法及其不足 .于工作站分类的产能调整方法 . 工作站层面的产能调整方式 . 各类工作站的产能调整方式 .于工作站产能调整的混流装配线重构方法 . 问题描述 . 混流装配线重构流程 . 重构优化目标函数 . 重构算法步骤 .例分析 .章小结 . 论 .考文献 .读硕士学位期间承担的科研任务与主要成果 . 谢 .者简介 .- 1 章 绪 论 题背景及研究意义 题背景 制造业的发展归根结底是由生产力发展驱动的 。对应各个时代，生产系统经历了手工工艺制造、流水线制造、柔性制造以及 大规模定制的发展变化。其发展过程如图 1示。 图 1造系统发展历程1但随着消费者的需求呈现出个性化、多样化、 易变性等特点。生产厂家很难把握需求的强度和方向。流水线不能满负荷运行的情况时常发生。据统计， 1999 年欧洲的流水线利用率只有 53%。改变以生产为中心，建立以客户为中心的生产理念是今后生产的追求。由数控技术兴起而产生的柔性制造系统虽然能满足多样化的需求，但由于其单件生产效率低和初始投资庞大等缺点2。实行大规模定制生产方式成为许多行业适应当前市场环境的唯一方法，混流装配线便是当前企业应用较多的一种。它可以通过标准化的方式，快速的生产标准化的产品。 混流装配线是一种面向产品族的具有较强柔性 的生产系统，同时它具备与流水式生产相近的生产效率。它可以在同一时间， 在系统内生产同族内不同数量的不同产品。产品的种类和数量可以根据消费者需求 在一定范围内快速调整，从而可以快速响应市场，减少在制品库存，提高资金流转 速度。当前企业能够脱颖而出的要素包括以下 3 个：质量、生产期限和产品成本。混流装配线可以很好的帮助企业达到以上 3 个目标。 电等行业主导生产模式，但它也有其自身的局限性。它的柔性局限于特定的产品族，对新产品的投 产响应速度要远弱于柔性制造系统，而且由于当前企业应用的混流装配线结构固定 ，面对短期内的大幅度需求波动，很难在不改变物理结构的情况下快速响应市场。 当前正在研究发展的可重构生产系统可以在理论上解决当前企业面临的问题，但由 于生产线过于昂贵，彻底抛弃当前混流装配线去购置可重构装配线很不经济，许多 中小企业也负担不起如此庞大的初始投资。网络的发展使得订单下达速度很快，这 些因素便可能导致企业的市场需求在短期内产生大幅度变化。对于采用混流装配线 这一生产结构相对固定生产系统的企业来说，很难在短期内大幅度变动自身生产能 力，当前企业大多采用在装配线的瓶颈环节添加平行工作站，用以解决产能不足的 问题。但平行工作站的添加需要一定的时间，而且可能由于下一时期的生产需求减 少而产生产能过剩的问题。这一方式不但增加了投资，还会造成维护费用的增多。 如何进一步提高混流装配线适应新产品和短期内大幅度需求波动的能力成为许多企业急需解决的难题。 题的研究意义 如何解决采用混流装配线生产方式的企业所面 临的上述问题已迫在眉睫，但国内外学者对这方面的研究却相对很少。对混流 装配线的研究大多集中在装配线的平衡和排序上，装配线的平衡可以较大幅度地调 整装配线的长期产能，装配线的排序可以调整短期产能，但是幅度较小。两者都无 法很好地完成混流装配线产能的短期大幅度调整。本文以各个工作站为最基本的研究单元，通过建立其 模型，对各生产线的加工能力进行分析，提出了根据企业当前订单实时调整产能的重构方法，该方法以满足订单交货期为前提，可以根据企 业现有资源和订单任务量对所有装配线的资源进行结构上的虚拟调整。能够随时根 据当前任务量计算出企业现有剩余加工能力。为企业赢取新的订单提供信息上的支 持。满足客户对不同产品的数量和生产期限上的要求。另外，本文提出的方法还可 以对现存系统进行结构和性能的分析和评价，充分挖掘企业的改善潜力。 题来源 本文所研究课题来源于导师教育部人文社会科学青年基金基于协同控制的随机混流装配过程重构优化研究 ，项目编号： ( 11 - 内外研究现状 究现状 当前国内外对混流装配线的研究目的为力求提 高装配线的效率和对市场变化的反应速度。装配线产能调整的研究主要包括混 流装配线的建模、平衡与排序等几个方面。下面分别给出这几个方面的研究现状。 流装配线建模研究现状 系统建模就是运用恰当的建模工具把系统特征 表达出来，通过模型对系统的结构特征和动态特征进行分析，优化系统结构和 性能。常用建模方法有两类：一个是基于离散事件动态系统的建模方法 ，另一个是基于运筹学的建模方法3。前一种主要运用多智能体 ( 等工具，后一种主要有马尔科夫链(型，排队网络模型等。 马尔科夫过程着重研究事物的状态转移理论， 时间与状态都为离散的马尔科夫过程称为马尔科夫链。它被广泛地应用到离散 事件动态系统的建模当中4。它的优点在于能够较好地获得系统的稳态解。而阻碍 其发展的重要因素就是动态数据较多的系统的状态数据组合爆炸问题。其另一个缺 点是需要对系统做许多条件假定，这会使得所建模型与实际研究系统间产生较大差异，无法准确反映系统的真实特性3。 排队网络法是在排队论的基础上发展来的，被 广泛地应用到生产和服务系统的建模和系统分析当中。其优点是可 以很好地得出系统的各项指标 (平均队长、平均服务时间、服务效率等 )。但该方法常需假设某些因子 (如顾客到达 )服从某种概率分布，这与实际系统的运行环境不符。 被看作对象的扩展，具有一定的反应性、自主性、社会性和预动性5。是具有并发、竞争和冲突等特性的离散事件动态系统主要形式化工具，并具有坚实的数学基础和图形化的表示方法等优点 。两种都是常用的建模方法，近几年来将两种建模方法相结合共同建立系统模型的 方式为众多学者所采用。郭峰、姚淑珍6提出了一种混合 构，并利用 建立了系统、个体两个层次上的模型。蔡远利、于振华等7利用面向对象 建立多 统体系的结构模型，并运用 和 演算分析系统的动态演化行为。 常用的 建模方法还有扩展 和面向对象 。黄银娣、卞荣花等8运用时间着色 建立了汽车混流装配线系统模型，并提出了对模型进行简 明海、白颖等9将赋时着色 与面向 术相结合建立了可重构装配线的模型，充分利用封装性来缩小系统模型的规模，并利用 交互协议消除模型中的死锁和冲突。 面向对象 献 10以面向对象 建立系统的模型， 该方法充分结合了 和面向对象两者的优点，充分利用对象的继承性和封 装性，降低模型维度的同时增强了模型的可重用性。文献 14给出了面向对象 的建模过程，提出了其动态特性的分析方法，对各种面向对象 的建模方法进行评述，并对其发展趋势进行了展望。 流装配线平衡与排序研究现状 混流装配线的平衡是指在满足工序约束的前提 下，将各工序分配到工作站上，使得各工作站加工时间尽可能相同并满足生产 节拍。混流装配线平衡问题分为以下三类15：已知节拍，求最小工作站数；已知工作站数，求最小节拍；工作站数和节拍已优化的前提下，使各工作站的负荷尽量平 衡。平衡问题的现有解决方法可分为三类16：最优化方法、启发式方法和工业工程方法。 最优化方法包括线性规划和动态规划等，其优 点是能够求解较小规模问题的最优解，缺点是对于复杂问题的求解能力不足。 该方面的研究重点是寻找方法扩大模型的应用范围。如查靓、徐学军等17通过计算各类约束条件的上下界以缩小模型规模，以提高所提模型解决平衡问题的范围。但这种扩展的程度有限。 启发式方法由于其较强的求解能力和较快的求 解速度而得到广泛地应用。主要有遗传算法、蚁群算法和禁忌搜索算法等。国 内外学者对该类方法作了大量的研究以期提高装配线的效率。陈晓峰、肖田元等18受鳗鱼效应的启发，针对平衡问题的特征，提出一种周期性自适应交换、变异算子 ，用以提高遗传算法对平衡问题的求解能力。 9以最大化生产效率和最小化平滑指数为指标，运用模拟退火算法求解第一类平衡问题。范维博、周俊等20应用遗传算法解决第一了装配线平衡问题，文中所提交叉、变异算子可以 有效提高可行解的产生几率，但无法避免非可行解的产生。 21提出了一种基于可行作业序列的初始种群产生方法，并利用特定的 变异算子保证各代群体都在可行解范围内，使得所提遗传算法可以在规定 的代数内寻求到最优解或近优解。 22提出了一种基于启发式的蚁群算法， 用以解决平行流水线的平衡问题。苑明海、李东波等23综合考虑工作站数量、负荷及装配线效率等因 - 5遗传算法与模拟退火算法相结合用以解 决混流装配线的平衡问题。由上述情况可以看出，结合两种甚至多种方法来解决平 衡问题已成为一种有效的方式。可以更好的平衡装配线。 工业工程的方法应用方法研究和作业测定等技 术，通过不断改善标准作业、物流、布局等方法改善装配线的平衡状况。其优 点是可以在零投资的前提下进行。如文献 24,25都是应用 5 析方法，通过对各工作站中作业元素的合并和拆分来平衡他们的作业时间已达 到装配线的平衡。何善平、奚立峰26在考虑疲劳作业约束这一因素的基础上，利用 工业工程的基本方法和自行改善的 正如前面课题研究意义中提到的那样，平衡只 能针对相对稳定的需求变动来调整产能。 27提出对于那些产品需求有明显季节变化的企业，可以根据需求的周期变化对装配线进行再平衡， 以提高装配线效率。但该方法并不适用于产品需求不呈现季节性变化的企业，而且 其产能调整是以季节变换为周期，时间仍旧较长。 混流装配线的排序可以解决短期内的需求波动 。近几年来，国内外对排序问题的研究也很成熟，而且大多体现出适应客户订 单的思想。如李苏珂、刘胜强等28根据淡季、旺季和正常季的订单数据，结合禁忌 搜索算法和遗传算法以获得所求问题的非劣解。唐秋华、席忠民等29提出了一种工位任务和投产序列系统调度的思想，并给出了对应不同目标的协同调度策略框架， 并用实例验证了所提方法的有效性。u 等30根据经过简化的转换网络流模型，应用动态规划的方法来解决混流装配线的排序问题。 1将准时制生产的思想引入混流装配线，根据订单实时对生产任务进行调 度，并强调物料供应对系统性能的重要影响。 生产调度对产能调整的实时性确实很好，但由 于它不能改变装配系统的布局和结构，所以其调整能力有限。有些学者将平衡 与排序综合考虑，以期在最大限度上提高装配线的效率32。近两年，国外有的学者初次将结构重构的思想引入装配线平衡问题，允许复制平行工作站的方式来提高装配线的产能。如 33应用分支定界法求解基于平行工作站的单一装配线平衡问题，文章假设可以根据需求复制任意数量的任一工作站。 4在允许添加平行工作站并充分考虑区域约束的前提下 ，应用混合遗传算法求解混流装配线 5在总结前人研究成果的基础上，不但充分考虑了区域约束并允许平行工作站的 添加，而且将混流装配线的平衡与排序综合考虑，较大幅度提高了装配线的柔性。 前研究的不足 已有学者提出将重构的思想引入生产线用以产 能调整，并将重构方法分为结构调整和逻辑调整36。现将当前所有可以应用于混 流装配线的重构技术予以归结，如表 1示。 表 1前可用重构技术 方法名称 重构类型 产能调节时间 (周期 ) 所需投资 产能调节能力混流装配线的平衡 逻辑重构 长 一般 大 混流装配线的排序 逻辑重构 很短 小 小 工业工程的方法 逻辑重构和结构重构 一般 很小 一般 构建新的生产线 结构重构 很长 很大 很大 当前企业大多采用添加瓶颈工件平行生产线的 方式，这虽然能大幅提高产能，但前期时间与资金投入很大，并且市场需求随 时都会发生变化，该方法不但需要大量的投资，还会由于需求减少而产生设备空闲和维护费用。 综合来看，工业工程的方法可以接受，但该方 法需要对产品的加工工艺和物流系统极为熟悉并具有极强创新意识的人员。平 衡可以较大幅度的调节产能，但是调节周期较长；排序可以快速调节产能，但是调整幅度有限。 从国内外研究现状中可以看到，研究人员试图 结合两种甚至多种重构方法来获取他们的优点。如文献 32是通过将平衡、排序和添加平行工作站等重构方法相结合来调整产能，但这些方法仍旧无法规避 平衡调整周期长、排序调整能力差的缺点，而且平行工作站的复制需要添加该工作 站所有工序加工设备的平行设备，还是会产生与添加平行装配线同样的缺点。 综上所述，我们可以看出各重构方法的结合仍 旧无法去除他们自身存在的本质缺陷。所以说目前还缺少一种高效、低成本并 且可以有力调节混流装配线产能的方法。 - 文研究方法及框架结构 文的研究方法 本文以混流装配线重构问题为研究对象，主要 研究内容和其对应的研究方法如表 1示。 表 1究内容及对应方法 研究内容 研究方法 工作站模型建立 扩展 基于订单的混流装配线的重构问题 一种启发式的重构方法 文的框架结构 第一章分析了当前生产环境背景，论述了当前 国内外对该课题的研究成果与不足。提出本文研究的内容和意义。 第二章对混流装配线和 的基本理论进行详尽的阐述，为第三章模型的建立奠定基础。 第三章以工作站为研究对象，运用面向对象赋时 建立工作站模型，并对模型的性质和性能进行分析。 第四章依据第三章中对工作站类型的划分，提 出了一种基于工作站产能调整的混流装配线重构方法。 章 混流装配线与 相关理论 面对越来越严峻的市场环境，如何提高企业根 据需求进行产能调整的能力成为许多管理人员急需解决的问题。本文以混流装 配线中的工作站为研究对象，探求进行产能调整的方法。为了充分了解工作站的性 质，首先，根据不同的特点对工作站进行分类，然后运用扩展 建立各类工作站模型。模型不但可以以图形化的方式展现工作站的部分特征，还可以利用 的分析方法，充分分析工作站的结构行者和动态性质。由于 元素可以携带一定的信息，这更使得所建模型可以更好地模拟真是工作站的各种特征。在建立模型之前，首先对混流装配线和 这一建模工具进行简要的介绍。 流装配线概述 流装配线的概念与分类 混流装配线是流水线在诸多因素的影响下慢慢 演变而来的，受客户化定制的影响，它可以在同一段时间能在系统内装配具有 一定相似性的不同数量的不同产品。与流水线生产一样，装配线也在同一工位上重复相同的作业。 通常按照装配产品品种和方式的不同，装配线 被分为单品种装配线、多品种轮番装配线和混流装配线。具体特点如图 2图示中可以看出，单品种装配线 单品种装配线 多品种轮番装配线 混流装配线 图 2配线分类 只能连续装配同一种产品；多品种轮番装配线 在一个生产计划期内轮番装配不同数量的不同产品，更换产品时需要较长的准备时 间；混流装配线可以在同一时间内装 - 9于混流装配线的工 作站相对于其他装配线的工作站具有较大的可变性，只需要调整相关组件便能适应 不同产品的装配要求，大大减少生产准备时间，从而提高了企业响应市场需求的速度。 根据装配的同步程度不同可将装配线分为同步 装配线和带有缓存的装配线。同步装配线中每个工作站的实际工作时间多要不 大于装配线的整体节拍 C，所以同步装配线具有一个固定的产率；而带有缓存的装 配线由于各个工作站具有较大差异的产率，需要在必要的不同工作站之间设置缓存区。 按照装配线的布局形状可将装配线分为直线型装配线和 U 型装配线。直线型装配线布局简单、容易组织，但柔性较差； U 型布局节省空间、便于人员沟通和学习，同时可以有效减少工作站数量，提高设备利用率37。 表 2配线分类 分类依据 装配线类型 单品种装配线 多品种轮番装配线 装配产品种类和方式 混流装配线 同步装配线 装配的同步程度 带有缓存的装配线 直线型装配线 装配线布局形状 U 型装配线 典型装配线 具有平行工作站的装配线 是否具有平行机制 带有平行机制的装配线 具有平行作业的装配线 按照装配线是否具有平行机制而分为具有平行 机制的装配线和典型装配线。具有平行机制的装配线又分为具有平行工作站的装配线和具有平行作业的装配线。具有平行机制的装配线可以有效的缩短全局节拍，尤其是当装配线中某一作业的作业时间超过整体节拍 C 时。还可以有效提高装配线的平衡程度。 我们将上述分类概括如上表 2表中可以看出，从单品种装配线到多品种轮 流装配、 U 型装配线、带有平行机制的装配线，这一发展过程都是为了提高装配线的柔性。可见，如何提高装配线的 产能调整能力一直为促进装配线发展的动力。 流装配线的特点 混流装配线的优点是能够同时装配同一类的不 同产品，而且具有与专业流水线相媲美的效率。混流装配线具有以下几个特点38。 (1) 专业化程度高。 虽然一般装配线的操作数较多，但作业先后顺 序相对固定，工人也只需负责固定到工作站的几个操作。不但提高了效率，而且有利于不合格率的降低。 (2) 具有固定的出产率。 即使技术人员尽量追求装配线的平衡，不同步 现象仍旧不可避免。但总装线上具有由生产计划制定的固定出产率。这有助于 按时完成订单，提高顾客满意度，避免任务堆积。 (3) 具有异步性和并发性。 各装配线间和各分装线在满足总体工艺先后顺 序的前提下，其装配操作具有异步性和并发性。这是装配线在不添加新设备的情况下进行产能调整的前提。 (4) 作业的连续化。 装配对象按照工艺规程，在各工作站间单向流动，完成产品的装配。 的基本理论 是由德国 授在其博士论文中首次提出的。由于能很好的表达离散事件动态系统并行、异步、竞争、 冲突等特征，并能用清晰的图形方式直观的模拟系统，还能运用状态方程等工具分 析所建模型的结构特性和动态特性，它以成为当前重要的建模工具之一39。 的定义 属于图论中无孤立结点的有向二分图。 的图形表示一般由库所、变迁、有向弧、和拖肯这四个元素组成。库所 与变迁之间由有向弧首尾相连用以描述系统的结构，而拖肯在系统中的流动来模拟系统的状态变化。 - 11可被定义为满足以下条件一个六元组 ),;,(0 ： (2 (2)()( (2 )()( (2 ),(:)( (2 ),(:)( (2其中 : ),(21 系统的库所集合， 0n 为系统的库所个数； ),(21 系统的变迁集合， 0m 为系统的变迁个数； ,2,1,0:0库所到自然数集的一个映射，用以描述系统的初始状态； ,3,2,1: 权函数，可用来描述拖肯的流动批量； 3,2,1: 容量函数，用来表示各个库所所能容纳拖肯的最大值； 式 (2示系统的流关系， 用以表征系统构件间的结构关系， 而式 (2式 (2确保系统中没有孤立结点的存在。 正如前面所说，我们可以通过网系统标识的变 化来分析系统的动态性质，标识的变化是