引用本文

吴旭辉, 杜劭峰, 郝慧慧, 于洋, 殷勇, 李冬妮. 一种基于协同进化的流水线向Seru系统转化方法. 自动化学报, 2018, 44(6): 1015-1027. doi: 10.16383/j.aas.2018.c160642

WU Xu-Hui, DU Shao-Feng, HAO Hui-Hui, YU Yang, YIN Yong, LI Dong-Ni. A Line-seru Conversion Approach by Means of Cooperative Coevolution. ACTA AUTOMATICA SINICA, 2018, 44(6): 1015-1027. doi: 10.16383/j.aas.2018.c160642

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160642

关键词

协同进化，流水线，Seru系统，转化 

摘要

Seru生产系统是一种被广泛应用于电子制造产业的新型生产模式，但由于流水线向Seru系统转化问题（Line-seru conversion）包含有Seru构建与Seru调度两个相互耦合的子问题，现有算法难以在同时兼顾解的质量与计算效率的情况下对问题进行求解.因此，本文针对流水线向Seru系统转化问题的特点，提出了一种协同进化算法，即在进化算法中加入了协同机制，将Seru构建与Seru调度子问题作为两个子种群利用该机制进行协同进化，从而弥补了现有算法的不足.并且，本文还针对问题特点设计了个体基因编码方式，从而使规划获得的Seru生产系统具有更优的生产性能及均衡性能.实验表明，采用加入了协同机制的进化算法比传统解决流水线向Seru系统转化问题的方法具有更好的性能，本文所提的方法在最小化产品流通时间和劳动时间有较好的性能表现，并且具有较高的计算效率.

文章导读

当前, 我国的制造业成本已达美国的90 %以上, 传统的劳动密集型制造业竞争力已逐渐消失[1], 产品多样性和定制化急剧增加, 产品生命周期显著缩短, 导致市场需求的波动性和不确定性随之加剧.日趋多变的市场环境要求企业具有更为强大和迅速的应变能力, 这种能力已经很难通过传统生产模式得到满足.

以索尼(Sony)和佳能(Canon)为例, 由于它们的生产具有多品种、小批量、高附加值的特点, 且产品频繁进行设计升级与更新换代, 因此在生产技术和配置上要求生产系统能够根据生产需要进行快速调整, 而传统的基于精益思想构建的同步式、集成式的流水线已不能满足这样的需求.因此索尼和佳能通过构建一种新型生产系统, 即Seru (单元)生产系统, 在多变的市场环境中脱颖而出[2-4].佳能与索尼对Seru单元的实践转化遵循以下步骤: 1)当顾客需求产生波动, 组装流水线的不足凸现出来, 为了获得响应能力, 可以采取战略上的重新选择; 2)拆除流水线, 通过资源集中放置和去除/替换、多能工培训, 获得独立性和自治性, 构建分割式Seru单元来取代流水线; 3)随着Seru单元系统的成熟, 构建起Seru生产系统来达到供需平衡.基于以上步骤, Seru生产系统在实践中取得了令人瞩目的成效.索尼在构建了Seru生产系统后, 累计拆除了35 000米的传送带流水线, 节约了71万平方米的场地空间, 节省了36 846个工作岗位(相当于其之前劳动力总数的1/4).佳能的54家工厂在应用Seru生产系统后的5年间拆除了20 000米的组装流水线, 释放出72万平方米的厂房(相当于12家大型工厂), 节省了35 976个岗位, 总计降低成本2亿3 000万日元, 平均生产效率甚至超过了丰田[5].

继索尼和佳能之后, Seru生产系统在电子(如三星、松下、富士通等)、汽车零部件(如通用、丰田、本田等)以及食品行业得到推广并获得成功[2-8].在我国, 随着外资企业大量建厂, 带动了Seru生产系统这一新型生产模式的传播和推广.目前, 海尔、美的以及许多东部沿海的生活家电企业已经推行了Seru生产系统进行生产, 此外, 内蒙一机等企业在其小型零部件的装配中也开始实施Seru生产系统.这些令人瞩目的现象引起了研究领域的浓厚兴趣--为什么Seru生产系统不仅节约了资源, 还能够获得更快的响应速度、更高的效率和更大的利润？许多学者(包括INFORMS会士Stecke、Decision Sciences Institute (DSI)主席Swink、顶级期刊Production and Operations Management (POM)创始人Singhal、顶级期刊Manufacturing & Service Operations Management (M & SOM)主编Tang等)先后围绕Seru生产系统开展研究或将其作为一个新兴研究领域进行介绍[2, 9], 认为Seru生产系统代表了"下一代生产系统"的发展趋势[7].

目前的研究主要集中于两方面:

一方面是通过与传统生产方式的对比论证Seru生产系统的优势. Yin等[5]通过研究佳能企业的生产转型过程, 指出了将传统流水线改造为Seru生产系统的重要性. De Treville等[7]指出Seru生产系统在不确定市场环境下, 可使生产系统具备比现有的装配流水线更加强大的应变能力, Liu等[10-12]也提出了相同的观点. Manupati等[4]将Seru生产系统与传统流水线对比, 认为Seru生产系统更加节省人力资源, 并且更加规范和灵活. Liu等[13-14]认为, Seru生产系统是一种更为先进的生产模式, 其潜力远大于传统流水线, 同时也论证了Seru生产系统具有缩短提前期、降低库存的效果. Stecke等[2]在探索可以适应市场需求多变的生产模式时指出, Seru生产系统具有长期学习和进化的能力. Zhang等[15]指出, Seru生产系统可以节约大量的环境资源, 减少费用支出, 具有可持续发展性.

另一方面集中于如何将传统流水线改造为Seru生产系统. Luo等[16]研究了将传统流水线转为Seru生产系统过程中的人员分配问题. Yu等[17-19]在研究传统流水线向Seru生产系统转化的过程中, 提出了一种流水线分割与重组的数学模型, 他们还研究了转化过程中考虑时间成本、劳动力等多目标优化问题, 以及如何减少劳动力的问题. Liu等[10-12, 14, 18]提出传统流水线转化为Seru生产系统的框架与原则, 并且研究了多能工的培训分配问题. Zhang等[15]也研究了多能工对传统流水线转化为Seru生产系统的作用. Yu等[20]研究了Seru生产系统的形成与分配问题.

在对流水线向Seru系统转化(Line-seru conversion)这个问题的研究中, 可将问题简化为两个决策过程: Seru构建和Seru调度.将Seru生产系统投入实际生产的首要步骤是如何将现有流水线拆分为若干Seru, 以完成Seru生产系统的构建, 即Seru构建. Seru调度决策批次如何分配到Seru中.目前的研究都是对Seru调度阶段采用了例如FCFS (First come first served)等简单的启发式规则进行规划, 然后再设计算法来求解Seru构建的精确解或较优解.例如Yu等[21]通过修改原始NSGA (Non-dominated sorting genetic algorithm)-Ⅱ交叉、变异操作符的具体实现方式, 以适应Seru构建的特点, 从而将其运用在解决Seru构建问题上. Yu等[19]为了提高算法的知识利用能力, 将局部搜索算法与NSGA-Ⅱ相结合, 以提高Seru构建的质量. Liu等[18]提出了一种三阶段启发式算法, 解决了Seru生产系统构建阶段中工人分配的问题.

但是, 上述研究并没有联合决策过程进行全局寻优, 因此通过这类方法规划出的Seru生产系统无法充分发挥系统的灵活性与均衡能力较强的优势.实际上, 求解流水线向Seru转化问题的最优解应该是联合考虑Seru构造和Seru调度两个问题, 但如果同时对Seru构建与Seru调度两个方面联合进行寻优, 那么问题的解空间就会变得过于巨大, 现有方法难以在可接受的时间内得到Seru系统的最优规划方案.所以, 如何在合理的算法运行时间内, 同时对两个方面进行规划以获得较优的规划方案, 是解决该问题的关键.

本文参考Kaku等[22]研究, 引入了两项评估指标对Seru生产系统的性能进行评估, 即产品流通时间(Total throughput time, TTPT)和总劳动时间(Total labor hours, TLH)作为优化目标. TTPT即为系统中所有产品批次加工完成所花费的时间, 用来评估系统的生产率. TLH即为系统中所有工人的累计劳动时间, 用来评估系统的人员劳动效率.

基于以上分析, 本文提出一种多目标协同进化算法(Multi-objective cooperative coevolution, MOCC), 用以解决流水线向Seru转化的联合优化问题.本文方法在传统进化算法思想的基础上, 加入了子种群间的协同机制.算法针对流水线向Seru转化问题的特点, 建立两个子种群分别对应Seru构建与Seru调度两个子问题.通过协同机制, 两个子种群便可相互协同进化, 即在进化过程中同时考虑Seru构建与Seru调度且不增加算法运行时间, 以此解决现有方法存在的不足, 获得更优的转化结果.另外, 本文在解的基因编码中引入了冗余码, 以期在规划过程中获得更优的均衡性能.通过应用MOCC, 转化后的Seru生产系统在灵活性与生产能力上都会获得较大的提升.

本文其余部分组织如下:第1节介绍了在进化算法中引入协同机制的相关研究; 第2节给出了流水线向Seru生产系统转换问题抽象出的问题模型; 第3节提出了一种带有协同机制的进化算法; 第4节通过仿真实验验证该算法的性能; 第5节给出结论并展望下一步工作.

图 1  Seru构建编码示例1

图 2  Seru构建编码示例2

图 3  Seru调度编码示例1

本文针对流水线向Seru生产系统转化问题的特点, 从实际应用的要求出发, 提出一种基于个体编码内部交换的MOCC算法, 并针对问题特点, 加入了种群间协同机制, 解决流水线向Seru生产系统转化问题.由于所考虑的问题可分为Seru的构建和Seru的调度两个子问题, 并且子问题之间存在着交互作用, 所以该方法使用了两个子种群互相协作共同进化, 最后进化出协同效果较好的完整解.通过这样的方式, 该方法可以在兼顾计算效率的前提下, 获得良好的优化能力.实验结果表明, 与子问题单独进化相比, 协同进化能够有效扩大算法搜索范围, 充分发挥Seru生产系统的柔性与灵活性, 最终生成的规划方案也能够在实际生产中取得更好的应用效果.与应用NSGA-Ⅱ等传统算法求解该问题的方法相比, MOCC不仅在生产指标(如TTPT等)上优于传统算法, 所产生规划方案的均衡性能也有较为突出的表现.这种差异的原因在于, 通过子种群间的协同机制, 本方法同时考虑了Seru构建与Seru调度两个方面, 而传统方法往往将关注点置于Seru构建的规划上, 仅使用例如FCFS的启发式规则对Seru调度阶段进行规划, 虽然降低了问题的复杂性, 但也忽视了Seru调度阶段的重要性.并且, 我们在编码方案中引入冗余码, 增加了解的多样性, 从而提高了算法的优化性能.由此可见, MOCC同时兼备计算效率和优化性能的优势, 可以在实际应用中高效地解决复杂性高, 产品批次大小波动较大的流水线向Seru生产系统转化问题.

作者简介

吴旭辉

北京理工大学计算机学院硕士研究生.主要研究方向为演化计算和生产调度.E-mail:harry_wxh@163.com

杜劭峰  

特种车辆及其传动系统智能制造国家重点实验室主任.主要研究方向为数字化与智能制造

郝慧慧 

特种车辆及其传动系统智能制造国家重点实验室成员.主要研究方向为数字化仿真技术

于洋 

东北大学信息科学与工程学院副教授.主要研究方向为工业工程, 绿色物流.E-mail:yuyang@ise.neu.edu.cn

殷勇 

同志社大学大学院商学研究科教授.主要研究方向为Seru制造与工业4.0.E-mail:yyin@mail.doshisha.ac.jp

李冬妮 

北京理工大学计算机学院副教授.主要研究方向为智能优化, 企业计算, 物流管理.本文通信作者.E-mail:ldn@bit.edu.cn