基于遗传算法的装配车间调度问题的研究

醋蜜墅

基于遗传算法的装配车问调度问题的研究

王伟１，何纯１。刘庆云１，吴波１，王心红２

（１．华中科技大学机械科学与工程学院，湖北武汉４３００７４；２．南车青岛四方机车车辆股份有限公司，

山东青岛２６６１１１）

Ｒｅｓｅａｒｃｈ

ｏｎ

ＡｓｓｅｍｂｌｙＳｈｏｐＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍＢａｓｅｄ

ｏｎ

ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ

ＷＡＮＧＷｅｉｌ．ＨＥＣｈｕｎｌ，ＬＩＵＯｔｎｇ—ｙｕｎｌ，ＷＵＢ０１，ＷＡＮＧＳｉｎ—ｈｏｎ９２

（１．ＳｃｈｏｏｌｏｆＭｅｃｈａｎｉｃａｌＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＨｕａｚｈｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆ

Ｓｃｉｅｎｃｅ

ａｎｄＴｅｃｈｎｏｌｏｇｙ。Ｗｕｈａｎ４３００７４。ＣｈｉｎａＩ

２．ＣＳＲＱｉｎｇｄａｏＳｉｆａｎｇＬｏｃｏｍｏｔｉｖｅａｎｄＲｏＬＬｉｎｇＳｔｏｃｋＣｏ．，Ｌｔｄ．。Ｑｉｎｇｄａｏ２６６１１１，Ｃｈｉｎａ）

摘要：研究了装配车间调度问题，提出了一种基源、工艺流程、仓储及管理等多种动态信息的系统建于遗传算法的车间作业调度方法。根据车间调度系模分析方法ＣＨ。工艺规划和车间调度是计算机仿真‘统的特点，通过Ｄｅｌｍｉａ／ＱＵＥＳＴ软件建立了制造系模型中２个重要组成部分［２］。Ｄｅｌｍｉａ／ＱＵＥＳＴ是统仿真模型进行仿真分析。结合仿真系统，分析了一种基于离散事件的数字工厂仿真软件［３】。它能够ＱＵＥＳＴ软件的设计原理及应用方法。最后通过计精确、高效地按照生产工艺进行可视化仿真分析，为算机仿真模型实例验证了算法的有效性。

计算机仿真模型提供可靠的解决方案。

关键词：遗传算法；物流调度；装配车间；仿真模

目前，应用于装配车间调度系统建模和仿真的型

方法主要有：ＧＲＡＩ法、ＩＤＥＥ法、ＧＩＭ法、ＳＩＭ法和中图分类号：ＴＨｌ６４Ｐｅｔｒｉ网等系统建模方法［．］。这些方法局限于仿真文献标识码：Ａ

过程的非可视化。而应用于车间作业调度的方法主文章编号：１００１—２２５７（２０１２）０４—０００３—０４

要有：人工智能法、局部搜索法、数学规划法、启发式Ａｂｓｔｒａｃｔ：Ａｎｊｏｂ—ｓｈｏｐｓｃｈｅｄｕｌｉｎｇａｐｐｒｏａｃｈ规则法、约束满足法和神经网络法等优化方法。这ｂａｓｅｄ

ｏｎ

ａ

ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｗａｓｐｕｔｆｏｒｗａｒｄｆｏｒ

些方法局限于建模程序的复杂化。

ａｓｓｅｍｂｌｙｓｈｏｐｓｃｈｅｄｕｌｉｎｇ．Ａｃｃｏｒｄｉｎｇ

ｔｏ

ｔｈｅｃｈａｒａｃ—

为此，提出一种以Ｄｅｌｍｉａ／ＱＵＥＳＴ软件为平ｔｅｒｉｓｔｉｃｏｆｔｈｅｓｈｏｐｓｃｈｅｄｕｌｉｎｇｓｙｓｔｅｍ，ａｃｏｍｐｕｔｅｒ

台，基于遗传算法的装配车间调度问题的研究方法，．ｓｉｍｕｌａｔｉｏｎｏｆ

ｍａｎｕｆａｃｔｕｒｉｎｇｓｙｓｔｅｍ

ｗａｓｂｕｉｌｔ

从而实现了车间调度问题的优化、简化及可视化的ｂａｓｅｄ

ｏｎ

Ｄｅｌｍｉａ／ＱＵＥＳＴ

ｓｏｆｔｗａｒｅｉｎ

ｏｒｄｅｒ

ｔｏ

综合目标。ｍａｋｅ

ａ

ｓｉｍｕｌａｔｉｏｎａｎａｌｙｓｉｓ．Ｔｈｅｄｅｓｉｇｎｐｈｉｌｏｓｏｐｈｙ

１

系统模型

ａｎｄｔｈｅｉｍｐｌｅｍｅｎｔａｔｉｏｎｔｅｃｈｎｉｑｕｅｓｏｆＱＵＥＳＴ

ａｒｅ

ａｎａｌｙｚｅｄｂｙｃｏｍｂｉｎｉｎｇｔｈｅｓｉｍｕｌａｔｉｏｎｓｙｓｔｅｍ．Ｆｉ—在生产过程中，由于加工设备的不同而将不同

ｎａｌｌｙｔｈｅｒｅｓｕｌｔｏｆｃｏｍｐｕｔｅｒｓｉｍｕｌａｔｉｏｎｍｏｄｅｌｉｎｄｉ—

的加工过程组合在一起，导致了不同的零件具有不ｃａｔｅｓ

ｔｈｅｖａｌｉｄｉｔｙｏｆｔｈｅｊｏｂ—ｓｈｏｐｓｃｈｅｄｕｌｉｎｇａｐ—

同的工艺流程。车间调度的目的在于满足各个零件ｐｒｏａｃｈａｌｇｏｒｉｔｈｍ．

工艺流程的同时，确定具体的加工顺序，以便使生产Ｋｅｙｗｏｒｄｓ：ｇｅｎｅｔｉｃ

ａｌｇｏｒｉｔｈｍ；ｌｏｇｉｓｔｉｃｓｃｈｅｄ—

效率在固定的时间内达到一定的生产计划［５］。图１ｕｌｅ；ａｓｓｅｍｂｌｙｓｈｏｐ；ｓｉｍｕｌａｔｉｏｎｍｏｄｅｌ

为典型计算机仿真模型的模型框架图。

Ｉ虚拟环境ｋ广＿—二∑、匕二，／ｌ数据分析ｌ

枣乒

０

引言

ｌ加工设备ｒ。——歹７．≮＝－一、Ｉ优化仿真Ｉ

计算机仿真模型提供了一种新型的包含生产

几丽面邓、１琵面卯

收稿日期：２０１１—１１—０９

——℃剜——

基金项目：“十一五”国家科技支撑计劫（２００９ＢＡＧｌ２Ａ０１一Ｇ０１—３）图１计算机仿真模型

《机械与电子３２０１２（４）

万方数据

车间作业系统的主要特点为离散加工过程。面向对象的仿真设计方法能够通过声明对象特征、对象行为及相互关系实现离散制造模型的逻辑连接、信息处理和决策制定［６］。

１．１

生产模型

根据生产情况，计算机仿真模型对象主要分为

厂房类、生产线类、设备类、信息类和控制类口］。图２为典型生产线仿真模型结构。

设备类

信息类

控制类

图２生产线仿真模型网络对象

一一一一一一一一一

ａ．生产线类。一个系统物理模型包含至少一条生产线，每条生产线内又包含设备类、信息类和控制类模型。

ｂ．设备类。设备类又可以分为加工设备类、吊装设备类、输送设备类和场地设备类等。加工设备类是指用于进行装配、生产的各类加工机器；吊装设备类是指用于吊装零部件的各式吊车、起重设备；输送设备类是指在系统中用于运输零部件的各种载体运输工具；场地设备类是指系统中的零部件、外购件及产品的仓储、缓存区域。

ｃ．信息类。记录某一产品的生产工序、生产工位的完整工艺信息及总体生产计划纲领。

ｄ．控制类。即逻辑对象类，其主要功能是设计控制策略和选择决策规则，从而对系统进行动态调控。逻辑对象类在生产线系统中可分为作业时间类、故障修复类以及资源调度类等。作业时间类负责控制系统中设备的工作安排，如机器开工时间、停工时间和中途休息时间等；故障修复类则控制设备故障的发生时间概率及故障修复时间概率；资源调度类用来控制车间内各项生产资源的整体调度规则及调度方法。

上述各基本对象类均拥有属性与操作，利用类的继承与封装机制，可以快速生成生产线的制造环境，而且在生产线的生命周期内，这些对象类也并非孤立存在，而是紧密联系形成一个不可分割的整体，

４

万方数据

它们为生产模型的建立提供了基础。

１．２

生产方式

流水线生产方式采用流水线生产方法或者材料

转移法，即固定加工手段而移动材料的生产方式。节拍是一种重要的流水线评价标准，是指流水线上同一工位连续产出２个相同产品之间的时间间隔。流水线生产方式中，生产计划下的加工单元必须与其加工工位及加工对象保持一致，各工位加工工时为子节拍，生产线产品输出时间间隔为总节拍。在加工工位数量一定时，子节拍与总节拍趋近程度越高，生产线作业越流畅，生产效率越高。

节拍式生产方式即移动加工手段而固定材料的生产方式。节拍式生产方式中，生产计划下的加工单元与加工工位及加工对象多数情况下保持一致且固定不变。此时的产品输出节拍为第一个加工方式

开始与最后一个加工方式结束的时间间隔。

按节奏连续均衡生产是精益化制造的显著标志［８］。生产线加工单元按照成组工艺进行布置，同时生产作业与生产计划的对象按照相似性进行分类。按照生产线的均衡性，各个工位的加工工时及生产节拍应基本相等，节拍差异较大时，可以通过分解工位内容进行调整，某些工位生产过程无法分解时，其工时也应当为标准工时的整数倍，借助增加同型号加工单元使该工位加工工时趋近生产线节拍。

无论是何种方式的加工作业，都必须以一定的速度，具有连续性地在既定场地重复作业。以一定的速度加工，可稳定动力费及劳动力费用，降低成本；连续性生产，可稳定加工时间、保证工期；在相同场地进行同一作业，可以提高作业者的熟练度和作业水平，保证品质。也就是说，大量生产的四大特征（定速、连续、定位置和定作业）可使成本、工期和质量保持相对稳定。因此，不能采用大量生产方式的企业，难以降低成本、保证工期和质量，难以满足客户的要求，最终被市场的激烈竞争所淘汰。

模型生产采用混合式生产形式，即流水线生产方式与节拍式生产方式相结合的生产方式。１．３数学模型

柔性车间调度问题主要研究工件、机器和加工工艺的组合问题。工件每道工序可以在不同的机器上加工，因此，首选要选择加工工件的机器。

建立的柔性车间主要研究Ｎ个工件在Ｍ台机器上的加工过程，工件竹有ｍ道工序的加工问题。

《机械与电子｝２０１２（４）

每道工序可以在不同的机器上加工，工序的加工时间因使用机器不同而不同。要求确定与工艺约束条件相容的各机器上所有工件的各道工序在每台机器上排序，以达到加工性能最佳，既满足目标要求的最小实际值。

模型约束条件为：

ａ．同一零件在各机器上的加工工序有顺序约束，不同零件在各机器上的加工工序无顺序约束。

ｂ．每台机器一次只能加工一个零件，且加工一旦开始就不能发生中断。

‘

ｃ．零件在某一时刻只能在一台机器上加工。ｄ．所有加工工件优先级相同。ｅ．忽略一切机器故障。

遗传算法ＧＡ（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ）是一种模拟自然界生物进化过程的仿生算法［８］。它通过模仿生物的进化过程来优化解的集合，其基本操作是通过选择、交叉和变异搜索解的空间。其对空间的搜索具有隐含并行性，它不同于随机搜索（解空间中的枚举搜索），它的选择机制可以大大减小搜索空间，因而可以在有限时间内得到二个最优解或较优解，并且遗传算法还是一种具有全局优化能力的搜索方法。

加工时间目标函数定义如下：

Ｔ＝ｍａｘ｛ｍａｘｔ“｝

ｌ≤ｔ≤ｎ

ｌ≤Ｊ≤研。

式中，以为待加工的零件数；优为加工机器数；％为第ｉ种零件在第ｊ个机器完成加工的时闻。

遗传算法流程如图３所示。

厂网

、

ｉ开始】

．任务约束ｌ秽

Ｉ时间约束１

计数个竿适应度卜＿掣

．设备约束Ｉ

ｏ≥

．工序约束ｌ

输出结果

工艺约束Ｉ

Ｌ（结束】／

图３遗传算法

ａ．适应度函数。遗传算法在搜索过程中以适应度函数作为依据，通过适应度函数评价每个染色体的性能。适应度函数一般由目标函数变换而成，如

＜机械与电子｝２０１２（４）

万方数据

果目标函数可以直接利用，则目标函数即为适应度函数，否则需要对目标函数的值域进行映射，进而获得相应的适应度函数。

ｂ．个体编码。常用的编码方式有二进制和十进制２种编码方案。这里采用二进制编码，即用一个二进制向量作为一个染色体，表示为五。该向量的长度依赖于区间长度和要求精度，这里取精度为小数点后２位数。

ｃ．群体初始化。由于遗传算法群体型操作的需要，必须为遗传操作准备一个由若干初始解组成的初始群体。在确定群体规模后，为了提高算法的效率和质量，初始种群采用基因空间均匀分布算法

ＧＳＢＳ（ｇｅｎｅｓｐａｃｅｂａｌａｎｃｅ

ｓｔｒａｔｅｇｙ）［９１产生初始种

群，使初始种群大致的均匀分布于解空间中。这种方法可以在一定程度上缓解遗传算法局部收敛的问题，从而改善最优解的质量。

ｄ．选择策略。选择的目的是从当前的群体中选出优良个体，使他们有机会成为父代，以便繁殖后代。判断个体优良与否的准则是各自的适应度值，这里采用轮盘赌选择方法，其公式为：

Ｃ

Ｐ（ｉ）＝ｆ（ｉ）／∑，（ｆ）

ｉ＝ｌ

式中，Ｐ（ｉ）为个体ｉ的选择概率；，（ｉ）为个体ｉ的适应值，其取值为个体解码取得的最大完工时间的倒数，即厂（ｉ）＝１／Ｆ（ｆ）。这种方法有助于算法快速收敛，从而获得最优解。

ｅ．交叉与变异。在初始种群中，按照染色体适应度值折算的概率选取染色体进行交叉或者变异操作，适应度大的染色体被选择的概率较大，从而保证

优势个体在种群中以更大的概率存活。

交叉是主要的遗传操作，新染色体大部分由交叉获得，交叉操作能够有效地保留父项信息，这里交叉算子采用部分映射交叉方式。

变异操作的目的是通过随机改变染色体某些基

因来引入新个体，提高种群多样性，这里变异算子采用逆序操作。

２仿真及结果分析

２．１问题描述

产品生产过程由零件部装及部件总装２部分构成，共包含６个部装区，每个部装区分别由若干个可以拆分但具有工序约束关系的工艺过程组成。每个

５。

部装区对应一个总装工位，共计６个总装工位。当零件完成部装后，由天车将部件运输到相应的总装线加工工位；总装线各工位完成后，输送到加工终端，由加工终端完成加工后输出产品。产品生产车间物料流向如图４所示。图中所示各部装区工艺过程组合而成的加工工时及相应总装线工位加工工时

如表１所示。

３结束语

研究表明，通过遗传算法可以对装配车间进行作业调度优化。基于Ｄｅｌｍｉａ／ＱＵＥＳＴ的计算机制造仿真模型对于改进与验证生产车间工艺规划起到了辅助验证的作用。车间作业调度方法与计算机仿真模型的结合可以在车问工艺规划过程中起到优化与验证的效果，从而在实际生产前完成了车间优化设计，达到了节约成本、提高效率的最终目的。参考文献；

［１］Ｘｉｏｎｇ

ＧＬ．Ａｐｐｌｉｃａｔｉｏｎａｎｄｄｅｖｅｌｏｐｍｅｎｔｏｆｓｉｍｕｌａｔｉｏｎ

ｔｅｃｈｏｌｏｇｙｉｎ

ｆ医吁咱匣Ｈ甄乎匮日岖匿悃

韶裴线

崮自岖童卜雹西．压叁卜《摘

总装线

ｍａｎｕｆａｃｔｕｒｉｎｇ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｙｓｔｅｍＳｉｍ—

ｕｌａｔｉｏｎ，１９９９，１１（３）：１４８—１５０．

图４产品生产车间物料流向衰１产品生产原始生产节拍裹

工位号

１

２１９７０３３８０

３１０５０２１２０

４１６１０９６０

５４３５８４０

Ｙｚ］Ｓｕｇｉｍｕｒａ

ｒａｉｎ

６０３６２０

Ｎ．ＨｉｎｏＲ．ＭｏｒｉｗａｋｉＴ

Ｉｎｔｅｇｒａｔｅｄｐｒｏｃｅｓｓ

ｐｌａｎｎｉｎｇａｎｄｓｃｈｅｄｕｌｉｎｇｉｎｈｏｌｏｎｉｃｍａｎｕｆａｃｔｕｒｉｎｇｓｙｓ—

ｔｅｍｓ［Ａ］．ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍ

ｏｎ

Ａｓｓｅｍｂｌｙ

部装４７０总装

３３２０

ａｎｄＴａｓｋＰｌａｎｎｉｎｇＳｏｆｔ２００１．３６—４１．

Ｒｅｓｅａｒｃｈ［Ｃ］Ｆｕｋｕｏｋａ，Ｊａｐａｎ，

２．２解决方案

由节拍表可知问题如下：工位５部装及总装节拍与其余５项严重不均；工位２及工位３总装节拍与其余工位差异较大。经遗传算法优化重组，优化后产品生产过程中零件部装工位数量未发生变化，但对部装工位５进行了拆分处理。而对应的总装工位数量也未发生变化，但总装工位２与总装工位３进行了合并处理，而总装工位５进行了拆分处理。经过优化处理，各工位工时趋于平衡。

生产模型优化后的生产节拍如表２所示，生产模型优化前后产能对比如图５所示。

衰２产品生产优化生产节拍寰

工位号部装总装

ｌ＾

１４７０１８１０

２１９７０１５１０

３１０５０１８１０

４１６１０ｌ５１０

５４５５１８１０

［３］ＤａｓｓｕｌｔＳｙｓｔｅｍ．Ｄｅｌｍｉａ／Ｑｕｅｓｔ

ｒＺ］．Ｄａｓｓｕｈｃ。．，２００４．

Ｄ５Ｒ１２ＵｓｅｒＭａｎｕａｌ

［４３壬煜．物流系统的仿真研究综述．制造业自动化［Ｊ］．

２００４，２４（９）：５—８．

Ｉｓ］Ｗａｎｇ［６］Ｈｏｕ

Ｌ．Ｓｈｏｐｓｃｈｅｄｕｌｉｎｇｗｉｔｈｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ［Ｃ］．

Ｂｅｉｊｉｎ：ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ．２００３．

Ｙ．ＦａｎＸＭ．Ｓｉｍｕｌａｔｉｏｎ—ｂａｓｅｄｍａｎｕｆａｃｔｕｒｉｎｇ

ｓｙｓｔｅｍｏｂｊｅｃｔ４６．

ｍｏｄｅｌｉｎｇ［Ｊ］．ＣＩＭＳ．２００１，７（５）：４２—

ｉｎｔｒｏｄｕｃｔｉｏｎ［ＥＢ／０１．］．ｈｔｔｐ：／／

［７］ＶｉｒｔｕａｌＲｅａｌｉｔｙＡｓｈｏｒｔ

ＷＷＷ—ｖｒｌｕｍｉｃｈ．ｅｄｕ／ｉｎｔｒｏ／ｉｎｄｅｘ．ｈｔｍｌ，２００８．

［８］王凌．车同调度及其遗传算法［Ｍ］．北京：清华大学

ｒａｉｎ

６０１８１０

出版社，２００３．

［９］胡建军，唐常杰，段磊，等．基因表达式编程初始种群

的多样化策略［Ｊ］．计算机学报，２００７．３０（２）：３０５—

３１１

、…

“ｍ“Ｐ《■｝ＰⅢ＃■“№‘Ｐ№

作者简介：王伟（１９８５一）．男．天津人，硕士研究生，研究方向为虚拟仿真制造技术Ｉ何纯（１９８９一）．女，湖北监利＾．硕士研究生．研究方向为虚拟仿真制造技术Ｉ期庆云（１９８５一）．士．天津人，硬士研究生．研究方向为计算机交互设计技术；吴波（１９６３一），男 期北监利人，教授．博士研究生导师．研究方向为设备智能监溯与控制．信息处理、制造自动化和智能制造｝壬心红（１９６２一）．女．山东荣成人，高级工程师．研究方向为机车车辆工程。

‰ＩＢ盐誓＿

万方数据

《机械与电子｝２０１２（４）

基于遗传算法的装配车间调度问题的研究

作者：作者单位：刊名：英文刊名：年，卷(期)：

王伟， 何纯， 刘庆云， 吴波， 王心红， WANG Wei， HE Chun， LIU Qing-yun， WU Bo， WANG Xin-hong

王伟,何纯,刘庆云,吴波,WANG Wei,HE Chun,LIU Qing-yun,WU Bo(华中科技大学机械科学与工程学院,湖北武汉,430074)， 王心红,WANG Xin-hong(南车青岛四方机车车辆股份有限公司,山东青岛,266111)机械与电子

Machinery & Electronics2012(4)

本文读者也读过(10条)

1. 唐金金.周磊山.佟路.周艳芳.TANG Jinjin.ZHOU Leishan.TONG Lu.ZHOU Yanfang 单列高速列车运行仿真模型与算法[期刊论文]-中国铁道科学2012,33(3)

2. 陈倩清.陈艳 基于工作过程的“船体分段模型制作”课程改革与实践[会议论文]-2011

3. 潘军.马登哲.蒋祖华 虚拟产品开发及其仿真模型的研究与应用[期刊论文]-计算机集成制造系统2002,8(9)

4. 张靳.胡霏凌.郭聪.陈丹.王鹏飞.ZHANG Jin.HU Fei-ling.GUO Cong.CHEN Dan.WANG Peng-fei 基于Delmia/Quest的煤机生产线规划仿真与应用[期刊论文]-机械工程与自动化2012(2)

5. 陈顺立.CHEN Shun-li 基于人工神经网络的动态系统仿真模型和算法研究[期刊论文]-煤炭技术2012,31(1)

6. 廖湘辉.刘欢.谭宗柒.姜雨.陈文琛.LIAO Xianghui.LIU Huan.TAN Zongqi.JIANG Yu.CHEN Wenchen 基于Simulink的穿行式钢模台车液压系统的性能分析[期刊论文]-机床与液压2012,40(1)

7. 李成博.王小明.柳强.LI Cheng-bo.WANG Xiao-ming.LIU Qiang 基于遗传算法的WMSNs多路径多目标优化路由算法[期刊论文]-计算机应用研究2012,29(6)

8. 蒋国璋.曹俊.孔建益.李公法.张华.Jiang Guozhang.Cao Jun.Kong Jianyi.Li Gongfa.Zhang Hua 基于轧钢生产知识网系统生产过程控制模型研究[期刊论文]-冶金设备2008(6)

9. 郭亚芬 生产过程控制模型化方法探讨和应用实例[期刊论文]-宝钢技术2004(z1)

10. 翁小雄.黄德剑.黎升福.Weng Xiao-xiong.Huang De-jian.Li Sheng-fu 公共建筑行人交通仿真性能分析[期刊论文]-华南理工大学学报（自然科学版）2012,40(2)

本文链接：/Periodical_jxydz201204001.aspx

本文来源：https://www.bwwdw.com/article/2bn4.html