基于JIT的多车间混流装配计划排序问题*

徐 兵，陶丽华，胡月梅

（长春工业大学机电工程学院，长春 130012）

基于JIT的多车间混流装配计划排序问题*

徐 兵，陶丽华，胡月梅

（长春工业大学机电工程学院，长春 130012）

为使JIT生产模式下多车间混流装配线敏捷、高效地运行，研究了具有供需关系的多车间混流装配线计划排序问题。以JIT车间混流装配线上车型切换次数、关键件型号切换次数、车身喷涂颜色变化和违反选装件的选装频率次数最少为优化目标，采用加权平均法建立了多目标优化数学模型。针对遗传算法容易陷入局部最优和提前收敛的问题，提出了求解多车间混流装配计划排序的自适应遗传算法。通过交叉概率和变异概率的自适应调整、局部寻优和保优策略，提高了算法的寻优能力。最后通过算例验证了算法的有效性。

多车间；混流装配；计划排序

0 引言

JIT生产模式以高效率、低在制、消除中断和浪费而被越来越多的混流装配企业所采用，它可以在基本不改变生产组织方式的前提下满足用户的多样化需求，具有很高的灵活性。混流装配生产模式已被越来越多的大型汽车制造企业所采用，与之相关的投产计划排序问题也日益成为研究的热点［1-3］。邵新宇［4］提出了基于部分属性序列的多车间计划排序问题。董义军［5］研究了面向ATP、没有供需关系的多工厂协同再调度问题。苏生［6］提出了多个没有供需关系的多工厂集成的计划调度问题。郑敏［7］研究了总装线线边物料消耗速率波动均衡、子装配工负荷均衡和涂装车间颜色切换问题。黄冈［8］提出了具有排序功能缓冲区的焊装车间、涂装车间、总装车间计划排序数学模型。但是，无论是数学建模还是算法研究对JIT生产要求的多车间协同的计划排序问题考虑的较少。

在JIT生产模式下，一汽解放卡车厂焊装车间、涂装车间和总装车间的生产工艺各不相同，其排序优化目标存在较大差异，甚至出现冲突，如果完全让各车间独立制定各自的排序计划，必然会导致车间之间的物料供应不上而影响日生产计划的完成。因此，文章主要根据一汽解放卡车厂多车间一个流的JIT生产需求，假定协调总装车间与各关键件分装线生产平衡的日生产计划已制订，研究日生产计划的优化排序问题。

1 多车间混流装配计划排序模型

1.1 问题描述

一汽解放卡车的生产具有多品种小批量的特点，卡车的生产过程依次要经过焊装车间和涂装车间，最后进入总装车间完成整车装配。为了提高各车间的生产效率，需要解决以下问题：

（1）在焊装车间车型的改变需要一系列的生产准备时间调整车身坐标，因此，焊装线要求尽量减少车型的变化。

（2）在涂装车间当两个连续生产的卡车被喷成不同颜色时，必须用油漆清洗剂对喷枪进行一次彻底地清洗［9］，当颜色变化频繁时，不仅浪费时间，还浪费资源。因此，要求尽量将相同颜色的车排列在一起，以减少车身颜色的变化。

（3）在总装车间，由于选装件需要耗费操作者较长时间，如果连续装配某种选装件过多，会导致操作者疲劳，造成生产任务难以完成，甚至导致整个生产线停线。每种选装件都设定一个选装频率，为了实现选装件的生产负荷平衡，计划排序必须要尽量满足所有选装件的选装频率，以提高总装线的生产负荷均衡要求。另一方面，随着总装配线上关键件型号的切换次数的增加，错、漏装问题随之而来，因此，总装配线要尽量减少关键件型号的切换次数。

为了保证一汽解放卡车厂日生产计划的顺利完成，实现混流装配的均衡化和准时化，焊装车间、涂装车间和总装车间需采用一个生产序列。因此，生产计划排序不仅要考虑总装车间的生产负荷平衡问题，还要考虑涂装车间和焊装车间生产效率的优化，最大限度地建立一个平衡的生产系统，实现一个流的生产，提高整车的生产效率。

1.2 符号定义

JIT生产方式下，一汽解放卡车多车间混流装配的前提条件为：

（1）根据日生产计划，假定日生产不同型号的卡车共n辆，每辆车都具有型号、颜色属性，n辆车的所有可能排产序列的集合为X，x∈X表示某一具体计划排产序列，即x=（x1，x2，…xj…，xn），1≤j≤n，简称为排序x，xj表示排产序列x中的第j辆车。

（2）每一种车型都由0个或多个选装件、若干关键件组成。每辆车只能为一种车型，喷涂一种颜色。每一种配置方案包括车的型号定义和颜色定义，即每一配置方案对应一种具体的车型和一种具体的颜色。

（3）装配生产中所涉及的零部件分为两类，第一类是选装件零部件，这类零部件仅在一部分型号的产品选配，第二类关键件零部件，所有产品均需要装配此类零件，但不同型号的产品装配该类零部件可能型号不同。

根据以上假设条件，定义如下参数：O：选装件集合，o∈O表示某选装件；

K：关键件集合，k∈K表示某关键件；

F：喷涂颜色集合，f∈F表示一种颜色；

T：车型的集合，t∈T表示一种车型；

P：配置方案的集合，p∈P表示某一种配置方案；

No：Mo表示选装件o的选装频率，表示在生产序列x中的任意Mo个连续的车辆中，至多只能有No辆车装配选装件o。

定义以下0-1变量：

1.3 多车间混流装配线数学模型

依据1.2节的定义，根据焊装车间、涂装车间和总装车间计划排序的要求，分别建立各车间生产计划排序的优化目标，最后采用加权平均法建立JIT生产模式下的总装车间计划排序数学模型。

定义车型的变化次数为Z1，为了满足焊装车间尽量减少车型变化的需求，生产计划排序x的优化目标为式（1）。

其中，式（2）表示每一个排序位置只能为某一种车型。式（3）表示每一排序位置只能为某一种配置方案。式（4）表示在排序x中若某一位置车型发生变换时记为1，否则为0。

定义车身喷涂颜色的变化次数为Z2，假定喷涂车间连续喷涂同种颜色车的能力足够大。为了满足涂装车间尽量减少车身颜色变化的次数，计划排序x的优化目标为（5）。

其中，式（6）表示每一位置只能喷涂某一种颜色。式（7）表示i位置车辆是否喷涂f颜色，若bfi为1，表示i位置喷涂f颜色；若bfi为0，表示i位置不喷涂f颜色。式（8）表示在排序x中某一位置发生颜色变换时zfi记为1，否则为0。

定义总装配线违反选装件选装频率的次数为Z3，为了满足总装车间各选装件的选装频率，生产计划排序x的优化目标为（9）。

式（10）表示每辆车只能有一种配置方案。式（11）表示i位置车辆的配置方案中是否包括选装件o，1表示i位置车辆配置方案包括o选装件；0表示i位置车辆配置方案不包括o选装件。式（12）表示在排序x中从j位置开始的连续M0辆车违反o选装件选装频率的次数。

定义总装配线关键件型号切换的次数为Z4，为了满足总装车间尽量减少关键件型号变化的需求，生产计划排序x的优化目标为（13）。

在JIT生产模式下，一汽解放卡车总装配线生产计划的优化要尽量满足式（1）、式（5）、式（9）和式（13）各目标，是一种多目标的优化排序。加权法以其简单易行、计算过程无需人工干预的特点广泛应用于多目标求解问题。采用加权平均法确定生产计划优化排序总目标如式（14）所示。

其中，wi分别为各目标Zi的权重。由于违反选装件频率会引起操作者疲劳，导致总装线停线，因此，Z3目标比其它目标重要它是保证卡车总装配线正常运行的关键。而喷涂颜色的变化主要影响喷涂效率和成本，车型的变化及关键件型号切换导致错装和漏装情况可通过智能识别等手段克服。因此，Z2比Z1和Z4目标重要，本文采用层次分析法确定各目标的权重如表1所示。

表1 各目标的重要程度及权重

2 混流装配计划排序的自适应遗传算法

混流装配计划排序问题属于组合优化问题中的NP难题，遗传算法（GA）对求解这类问题提供了有效手段。由于基本遗传算法容易陷入局部最优和提前收敛，文章采用自适应遗传算法［10］求解第1节提到的混流装配计划排序问题，通过自适应交叉和自适应变异可提高最优解的搜索能力；通过局部寻优和保优策略可及时将优良个体保存起来，以避免遗传算法的提前收敛。混流装配计划排序的自适应遗传算法流程如图1所示。

图1 JIT作业排序自适应遗传算法流程

（1）编码。将每种车型及其对应的颜色作为一种配置方案用唯一的自然数作为配置号表示，车型和颜色都相同的车配置号是相同的。采用整数编码，以生产计划的序列作为染色体，配置号作为基因，在解码时可以直接根据染色体进行解码，方便适应度值的计算。

（2）初始种群。随机改变染色体中基因的顺序生成初始种群。

（3）适应度函数。为了避免算法提前收敛，在遗传的初期，为了增加种群中下一代个体的多样性，限制高适应度个体的复制数量，应降低适应度的幅度，以降低种群中个体适应度的差异程度；在遗传操作的后期，为了提高个体之间的竞争性，以便于对最优解的进一步搜索，需要对适应度幅度适当拉伸，放大个体间适应度的差异，因此，适应度函数依据式（14）和遗传代数设计为式（15），其中gen为当前的遗传代数。

（4）选择。采用轮盘赌方法选择繁殖个体。控制每代中种群被替换的比例（代沟）为90%，种群中的10%较优个体直接作为繁殖个体。

（5）自适应交叉概率和自适应变异概率。交叉概率Pc和变异概率Pm选择过大，利于新个体的产生，但易破坏种群中的优良个体；而选择太小，不利于新个体的产生，影响问题的进一步求解，难于搜索到最优解。因此文章根据个体的适应度设计Pc、Pm。对于每代的精英个体，即适应度等于该代种群的最大适应度的个体，设计Pc、Pm为0，对于适应度小于精英个体而大于平均适应度的个体，以及小于等于平均适应度的个体，分别采用自适应Pc和Pm，根据适应度函数（15）设计自适应交叉概率Pc和自适应变异概率Pm如式（16）和式（17）所示。其中，Pac、Pam为适应度等于平均适应度的个体的交叉概率和变异概率，Plc、Plm适应度大于平均适应度或小于平均适应度的个体相对Pac、Pam的适应度变化的最大幅度值；Favg为平均适应度值，Fmax为最大适应度值，Fmin为最小适应度值，F为两个待交叉个体中较高个体的适应度值。

（6）交叉方法。在配对的父染色体A1和A2中随机选取一个交叉位，将A1交叉位置及左侧的基因值作为子染色体A1′对应位置的基因值，并在配对的另一个父染色体A2中随机删除这些基因值；然后，将父染色体A2中的基因从左向右依次填入子染色体A1′中的空白基因位。同理可得到子染色体A2′。其操作实例如图1所示。

图1 交叉操作实例

（7）变异。采用变换变异法，即在父染色体中随机选取两个基因位，交换其基因值。

（8）局部优化。为了提高遗传算法的局部搜索能力，对每代遗传操作后生成的染色体，若该染色体的适应度小于最优个体的适应度，还需通过数次反转变异法基于该染色体进行局部搜索。方法是随机选取该染色体中两个基因位，然后将其之间的子基因串反转，若反转后的染色体的适应度大于该染色体的适应度，则用反转后的染色体替换该染色体，否则，该染色体不变，直到满足反转的次数为止。通过局部搜索，可以提高后代染色体的质量。

（9）保优策略。为了防止遗传进化过程中最优个体的丢失，在每代进行遗传操作后，若种群中的最佳个体比最优个体好，则将该最佳个体替换最优个体保存起来。若种群中的最佳个体比最优个体差，则将最优个体替换种群中的最差个体，以防止最优个体流失。

3 算法示例及结果分析

JIT生产模式下一汽解放卡车总装配线日生产计划需要生产牵引卡车、载货卡车、自卸卡车3种车型、6种配置共25辆卡车，日生产计划如表2所示，各车型对关键件和选装件的需求及选装频率如表3所示。

表2 日生产计划

采用自适应遗传算法进行日生产计划优化排序，参数设置为种群大小40，遗传代沟90%，Pac=0.92，Plc=0.3，Pam=0.03，Plm=0.01，各优化目标的权重如表1所示，遗传进化80代，总目标及各车间子目标随进化代数的变化过程如图2所示。

表3 投产汽车配置

图2 自适应遗传算法各优化目标搜索过程

图2 中每个子图括号里左侧数据为子目标达到最优的代数，右侧数据为最优子目标值。随着遗传代数的增加，总目标值到72代以后趋向平稳；车型变化次数经过57代达到最优，由17次减少到10次；颜色切换次数经过72代达到最优，颜色切换由12次减少到1次；选装件冲突次数经过48代达到最优，违反选装件频率的次数由11次减少到0次，保证了总装配线的均衡生产；关键件型号切换次数经过57代达到最优，关键件型号切换次数由54次减少到30次。JIT生产模式下25辆卡车混流装配日生产计划优化排序结果如图3所示。

图3 混流装配线日生产计化优化排序

由图3可见，混流装配计划排序的自适应遗传算法可最大限度地减少总装配线的负荷冲突，完全能满足焊装车间、涂装车间和总装配车间计划排序的生产需求，提高了生产计划排产效率。

4 结束语

混流装配线计划排序问题是保证装配线平衡、高效、准时化的关键问题之一。文章为了实现多车间生产的负荷均衡，保证JIT生产的平顺性和高效型，将焊装、涂装和总装车间的生产计划排序目标综合考虑，采用层次分析法确定各目标的权重，并从违反选装件的选装频率次数、车身喷涂颜色变化、车型切换次数、关键件型号切换次数四个方面出发，采用加权平均法建立多目标综合优化数学模型。提出了混流装配计划排序的自适应遗传算法，通过交叉概率和变异概率的自适应调整，可在遗传进化的初期减少种群中个体的差异，提高种群的多样性，在遗传进化的后期通过增加个体的差异，保证最优解的进一步搜索，并通过局部寻优和保优策略提高了算法的寻优能力，避免了提前收敛。最后，通过算例，验证了自适应遗传算法可最大限度满足多车间混流装配线的准时化生产实际需求。

［1］Xiaobo Z，Ohno K.Algorithms for sequencing mixed models on an assembly line in a JIT production system［J］.Computers and Industry Engineering，1997，32（1）：47-56.

［2］宋春雷.混流装配线平衡与投产排序研究［D］.大连：大连理工大学，2012.

［3］李同正，杨才君，孙林岩.混流装配线平衡和排序问题研究综述［J］.河南科学，2012，30（7）：900-909.

［4］邵新宇，饶运清.制造系统运行优化理论与方法［M］.北京：科学出版社，2010.

［5］董义军.多工厂协同生产计划与调度方法研究［D］.上海：上海交通大学，2010.

［6］苏生.多工厂生产计划与调度优化模型与求解算法［D］.哈尔滨：哈尔滨工业大学，2007.

［7］郑敏，董明.考虑转换约束的汽车混流装配线投产排序研究［J］.工业工程与管理，2012（2）：85-89.

［8］黄刚.混流装配生产的计划排序及其执行过程管理［D］.武汉：华中科技大学，2007.

［9］邢永庆.轿车涂装线生产准备过程分析及改进［D］.长春：吉林大学，2012.

［10］刘敬宇，朱朝艳.改进自适应遗传算法的结构优化设计［J］.辽宁工学院学报，2007，26（5）：308-311.

（编辑 李秀敏）

Research on Mixed-Model Assembly Line's Sorting of Multiple Workshop Based on JIT

XU Bing，TAO Li-hua，HU Yue-mei
（School of Mechanical and Electrical Engineering，Changchun University of Technology，Changchun 130012，China）

In order to agile and efficient operation of mixed-model assembly line's sorting of multiple workshop based on JIT，this essay research the supply and demand between the multiple workshop.Multi-objective was present：minimizing model switching times，key-module type switching，color switching times and violating optional frequency.Then the weighted average method was used to build the multi-objective mathematical model.The paper presents the adaptive genetic algorithm to solve mixed-model assembly line's Sorting of multiple workshops，which according to genetic algorithm easy to fall into local optimum and convergence problems in advance.Improving the searching capability of the algorithm which by means of adaptive crossover and mutation，local optimization and optimal policy.Finally use example to verify the efficiency of the algorithm.

multiple cooperating workshops；mixed-model assembly；sorting

TH162；TG65

A

1001-2265（2015）01-0153-04 DOI：10.13462/j.cnki.mmtamt.2015.01.043

2014-06-09；

2014-08-09

国家高技术研究发展计划（863计划）（2007AA04Z1A4）

徐兵（1965—），男，黑龙江延寿人，长春工业大学副教授，博士，硕士生导师，研究方向为柔性制造技术和制造业信息化，（E-mail）xubing1965@126.com。