改进遗传算法求解混合流水装配作业调度问题

本资料包含pdf文件1个，下载需要1积分

在汽车、液晶面板等产品装配生产过程中，其生产线通常是混合流水式生产，特点是多品种，小批量，产品类型和尺寸不断变换。在这-类混合流水装配生产线的运作过程中，最关键的问题是装配生产线的平衡问题 以及相关的作业调度问题。本文只研究混合流水装配生产线的调度问题。

装配作业调度是-类较复杂的作业调度，与-般的研究较多的作业车问调度和流水车间作业调度这类将每个工件看作-个统-的整体的调度问题不同的是，装配作业是由不同的零件组装完成的，它不仅包含了工序之间的约束关系，还包含了不同装配组件加工过程的约束关系。鉴于装配作业调度的复杂性，现有的文献中，对装配作业调度的研究很少。

文献 提出了用 petri网规范装配工艺流程，基于人机集成求解调度问题。文献 研究了同时包含加工与装配生产过程的作业调度问题，并采用两种不同的解码方式得到最优解。

文献 在提出了基于时区处理的流水装配生产计划的基础上解决了基于产品队列的流水装配线调度问题。

本文将以液晶面板装配工艺生产线的作业调度问题为例，研究混合流水装配生产线的工艺特点。这类问题是-类NP问题，常用的求解方法有模拟退火算法、蚁群算法、遗传算法等。普通的遗传算法容易导致局部最优 ，本文采用精英保留策略和不同解码算法结合的遗传算法求解，增强了全局搜索能力，避免早熟。并给出实例验证。

1混合流水装配作业问题描述1.1典型工艺流程混合流水装配作业生产线的产品通常由很多零件组成，这些部件的装配过程可能是串联方式或者并联方式，这种并联方式的工艺调度过程称为带生产支线的装配作业调度。

以液晶面板显示器 TFT-LCD的单元装配工艺 CelAssembly Process为例，其生产工艺流程，如图 l所示：图 1 TFT-LCD Ce11生产阶段工艺流程H 竺- - - - 讲 鹏 肼 l 竺竺1 /器- 匝- - 触 序5 怖 ilr洋ll 下牟10 T序9 r序8图 1是-个典型的带生产支线的装配工艺，可以将整个生产流程分为前工程和后工程在对位贴合之前的工程包括对位贴合 称为前工程，从切割结束这部分工程称为后工程。

Cel生产阶段是 TFT-LCD生产过程中-个承上启下的重要的阶段，因此-个合理的生产计划和调度方案对提高资源利作者简介：徐 锋1989 ，男，l 夯通大学软件学院，硕士研究生，研究方向：制造业信息化，上海，200240步丰林1961-，男，上海， 二夯通大学软件学院，副教授，研究方向：软件工程、信息系统建模，上海，200240· 58·MicrocomputerApplications Vo1.29，No.9，2013 技术交流 微型电脑应用 2013年第29卷第9期用率，优化企业效益具有非常重要的价值。由于 TFT-LCD生产设备非常昂贵，即使是-个很小的改进也能带来很大的收益。

1.2假设条件和参数说明如上的混合流水装配作业问题可以描述如下：N种不同类型的产品，每种产品由原料 A和原料 B各自经过若干工艺后装配成产品 C，每种产品的原料 A与原料 B 是--对应的，在实际生产中以批量Lot为基本单位进行生产，每-批由若干相同零件组成，每道工序可在若干台相同的机器上加工，假设条件如下：1任意产品任意批次的任意工序-旦开始运作，不可以被中断；2不考虑设备生产过程中可能出现的损坏延误问题；3不考虑次品返工问题；f4不考虑产品在各道工序的机器之间的搬运时间；5同-台机器连续生产的两批产 品如果属于同种类型，则不需要设备准备时间，否则在生产第二批产品前需要- 定的准备时间；6初始时间设为 0时刻，投料类型为静态投料，原料 A和原料 B在 0时刻同时投入加工。

- 第f种产品类型，f，2，L，n。由于每种产品由原料 A和 B装配而成，所以用 表示装配产品C及原料 A，用 表示对应的原料 B；，- 产品类型 的第 批工件，J1，2，L， ，其中f表示第f种产品的待fill件总批量，定义r> 为所有ii产品待加工工件总批量。

其中0l，L， 表示原料A的加工工序，0 L， 表示原料 B的加工工序，其余为装配品 C的加工工序。

- 第 k道工序的第 m台机器，ml，2，L ， ，为 的机器总数。

S -工序 的同-台机器上加工工件的类型由其他产品更换到 时机器的准备时问。

P-产品 在工序 的某台机器上加工的时间。显然，对于同-种产品，同-道工序的加工时间相同。

c -工件Ju的工序 的完工时问；t -工件 的工序 的开始加工时间。

，- 工件 ，的加权延迟，是-个动态的衡量工件紧迫程度的参数，工件越紧迫，权值越大。

-. -工件 的工序 是否在机器 上加工，若是，则为 ，如不是，则为 0。

1.3约束条件f1m件与机器加工约束，∑Xi 1，Vi， ，k l如公式 1、2·59·2约束1表示-批工件的某道工序只能在该道工序若干台机器中的-台机ignm，约束2表示-台机器同时只能加工-批工件 -批原料 A和另外-批原料 B装配后只能算作-批工件。

2m艺顺序约束，如公式3～公式6ZXi ∑ Vi，-，k∈1，awbl， 3ml ml- 1∑Xi ∑Xi H ，V ， ，k∈口，6 4ml mlhbl∑Xi 川， ∑ ，Vf， 5ml 1∑Xi .61， ∑Xi '6' ，Vi， 6约束3表示原料 A和装配品C后-道工序所有机器加工总批数不多于前-道工序总批数，4为原料 B相应的约束条件，约束5和6分别表示装配品 C总批数-定少于组件 A和B的总批数。

3装配约束，如公式7、8Xi，，，61， Xi·，，，61， 7t油1 t ·肌l 约束7和约束8分别表示装配时A和 B必定在同-台机器上加工且具有相同的开始加工时间。

41时间约束，如公式9～公式12rax√ 。， .， ，q√， ，f≠f， ≠ 后∈ 司 9剐 略 讲 . ， ≠ 610nD 。l， - ，q ， ≠ ≠ 七∈ Z司 1 1m Ⅸ 1，0-， ， ， t %，， ，，，6，f≠f， ≠ 12约束9～约束11为 A、B、c 的加工时间约束，-批工件的开始加工时间由在同机器上的前-批工件的完工时间 如果不是同-种产品需要加上准备时间和此工件前-道工序的完工时间的最大值确定。约束121为 A、B、c装配时的时间约束，即开始装配的时间为该机器上-批装配的工件的完工时问 如果不是同-种产品需要加上准备时间、A和 B装配前各 自最后-道工序的完工时间的最大值。

5取值范围约束，如公式13、公式14f.，. ， ∈0，1 13，≥0 141.4目标函数作业调度通常有多个 目标函数，对应不同的评价指标。

常见的指标有最大完工时间最写加工完所有工件所需时间的最小值 等式15和所有工件的加权延迟的最小值等式16，定义Y maxy，0以及设备利用率等。

min∑∑ 15n l min∑∑WijCijs- 16i1 jl对含有不同目标函数的问题的最常见的解决方法是将Vvmt ∑∑Microcomputer Applications Vo1.29，No.9，2013 技术交流 微型电脑应用 2013年第 29卷第9期其转化为单目标处理，如有，2个目标函数 ， ，L， ，则令，OH 17fxalf，xOf2. L 17其 中 ， ，L ， 为 自定义指标，根据实际生产情况在0，1内取值，且需满足加和为 1。

2求解过程2.1算法流程普通的遗传算法在选择、交叉、变异过程中，通常会造成具有最优适应度的个体丢失，导致其不是全局收敛的，精英保留策略则是将种群 中的最优个体保留到下-代，因此具有良好的全局收敛性 。本文所采用的方法是父种群中的最佳个体 x不参与遗传操作，然后其他个体产生经过遗传操作后产生新种群，找出新种群中的最佳个体Y和最差个体 z，如果 Y优于 x，则保留Y，否则仍保留x，删除Z恢复种群规模，进入下-代。

2.2算法设计2.2.1编码与初始种群为将混合流水装配作业调度问题的每个可行解表述成染色体，本文在-般矩阵编码的基础上结合此调度问题的特征，提出如下新的编码方法：表 1-个简单的示例2用-个二维矩阵 表示 A、B、阵AArs：1K a1M 0 Ma，l L 日元素 a 表示工件 ，的第k道工序在对应的机器上加工。a跳必须是位于1， 1之问的随机实数 hk表示工序 的机器总数，向下取整。如取值为 3.2，则表示在该工序的第3台机器上加工。k1，2，L，a时，此时b代表原料 A，k 1，a2，L，b时代表原料 B，其余取值代表产品C。然后将二维矩阵转化为-维数组：a L als 0，a2l，L a2 ，0L ，1L a ，将不同行之间的数据合并到-行，彼此用 0隔开。

3种群初始化：设种群规模为 N，由以上步骤 12产生 n个满足条件的染色体构成初始种群。

2.2.2适应度函数适应度函数是为了用于对遗传过程 中的个体进行评价，在本文中，将 fx转化为求最大值的函数厂 CN-厂 ，其中cN为自定义常数，根据实际生产情况取值。

2.2.3解码将染色体表示成可行调度的过程称为解码。当相同工序的不同工件在同-台机器上加工，需要确定工件的加工顺序。

本文采用两种解码方法，第-种是静态解码方法确定·60·某台机器的加工顺序，即根据染色体同-台机器上加工的不同工件的对应基因的值来判断，值越小越先加工，若值相同则根据工件编号顺序加工，如 1，2，3都在机器 2上加工，若对应基因为 2.23，2.55，2.23，则实际加 Jil序是1，3，2。

第二种是贪婪解码方法，在满足各约束条件 的基础上，采用具有最早完成时间的方法确定某台机器的加工顺序。设机器 待加工的工件为Yl Y2，L，Y ，定义数组z1q，当k≠bl时即为非装配步骤时，将Zi初始化为各 工件上 -道 工序 的完 工 时间 ，若 为 装配 步骤 即kb1，则将Z1f初始化为装配前各组件最后-道工序的完工时间的最大值。设z2 为实际加工的工件顺序，当k≠b1，时，安排加工顺序的算法如下：1选 择具有最 早完成 时间 的工件 Yi加 工 ，即令Z21Yi，并将zli记为-1；2更新zi1L Zli-1，Z1f1L zln，若Y，与属于同-种产品类型，则zl 为原来的值加上Y，在本机上的加工时间，若 Y，与.， 不属于同-种产品类型，则等于原来的值加工更换产品类型所需要的准备时间和加工时间之和。

3选择 Z11L zlf-1，Z1i1L Zl，2中最小值对应的工件Y，，令z22 ，。

4同样处理剩下的工件直到该机器上的所有工件处理完毕。

经过这样的处理，可确定每-台机器上不同工件的加工顺序，最终得到-个可行调度。

2.2.4选择种群需要优胜劣汰，那么优秀的个体必须以较大的概率保留，同时为了避免算法过早收敛，最优个体不参与选择操作～种群中的其余个体按适应度排序，然后多次产生 0，1之间的随机数，根据选择概率确定剩余的被选择个体。

2.2，5交叉和变异采用分段交叉和变异的方式对染色体进行遗传操作。

对 于 任 - 矩 阵 元 素 a船 ， 需 要 保 证 位 于 区 间1， 1，因此对于非最优的两个父代个体，随机选择在矩阵编码中位于同-行的若干元素，进行交换，产生子代1和子代 2。

变异的方法为：对非最优个体，为了保证 位于区间1， 1，