基于可重构思路的智慧车间优化布局算法

丁穗庭 王智伟 王思扬

（南京航空航天大学，南京 210000）

随着智慧车间概念的提出，在多品种小批量的生产方式推动下，车间布局整体规划越来越重要，日益强调可重构性，即根据生产要求快速调整设备和产线布局[1]。据Francis与White统计，固定而低效的车间设备布局会使搬运成本提高10%～30%，这不仅是企业巨大的浪费，也与当今智慧工厂追求高效敏捷的观念不符[2]。

车间设备布局问题最早由Meller、Narayanan和Vance在1999年提出，定义设备布局问题是指对n个矩形设备在给定的矩形车间内面向同一方向进行布间，使基于距离d的目标函数值最小[3]。近年来研究不断深入，Kia R等当作多行布局进行研究，建立了一个群组布局设计模型[4]。曹阳华等对相关物流量划分了物流等级，依据系统化设施布置（SLP）方法优化车间布局[5]。朱永国等充分考虑零件的生产工艺，提出基于加工工艺的连杆类零件柔性制造车间设备布局方法[6]。但归纳起来，以往的解决方案存在两个问题，一是优化目标比较单一，通常只考虑物流成本最小一个因素，忽略了其他目标，如布局规整程度、空间占用率等的实现；二是由于车间设备布局问题是一种非线性规划问题，也是一个NP难问题，用传统启发式算法如图论法、构造法很难得到最优解[7]。

针对这两方面的问题，本文在构建布局模型时，重点考虑了布局规整程度等因素，以增强车间的布局冗余能力；在模型求解时，利用遗传算法突出的寻优能力，运用Matlab软件进行求解[8]。

1 问题描述

本文进行布局优化时，重点考虑物流费用以及布局规整程度。首先，毋庸置疑，物流费用要作为最主要的目标，根据已知的各产品的工艺路线，合理安排设备的摆放位置使物流成本最小；其次，考虑布局的规整程度，对于多品种小批量式生产车间，对设备布局的柔性要求较高，布局时应尽可能规整（最终布局方案近似矩形），以增强车间的布局冗余能力。

假设有n台设备，生产a种产品，每台设备形状均规则，长宽尺寸各不相同且已知，车间的长宽已知。在生产的过程中，设备与设备之间有不同的当量运输量和运输频次。车间设备布局考虑的就是在生产a种产品的情况下，如何把这n台设备安放在合理的位置，以满足在一定的工序流程条件下，整个车间系统的面积利用效率最好。

2 布局模型

2.1 目标函数

设备布局问题为在布局尽可能规整的情况下要求物料运输费用最优化问题，即假设车间有n台设备、a种产品，则问题可描述为以下数学模型。

式中，k表示产品的种类，一共有a种产品；i、j表示任意单次运输的前后两设备，一共有n台设备；Qkij表示第k种产品从设备i到设备j的当量物流量；fkij表示产品k从设备i到设备j之间物流量发生的频次；（xi，yi）、（xj，yj）表示设备i和设备j的中心点坐标；P是单位物流量的运输成本（常数）。

2.2 约束条件

2.2.1 布局规整程度大于60%

布局规整程度用所有设备面积之和S0与布局占地面积S1之比表示。

其中，S0是所有设备面积和；S1是在最终布局方案中，一个能容纳所有设备的最小矩形面积，该矩形的特点是顶点是由最左、最右、最上、最下设备的中心点决定。li、lj表示设备i、j的长；hi、hj表示设备i、j的宽。该约束的效果是最终的布局中，用最外围设备（最左、最右、最上、最下）所确定的矩形尽可能小。

2.2.2 每台设备只能出现一次

共有N台设备，排列成R行，n=1，2，…，N，组成设备集合，r=1，2…，R，组成行数集合。设一个开关变量为：

满足Ozr=1的设备构成了第r行的设备集合，则第r行的设备数为：

r（z）表示第r行的第z个设备，z=1，2，…，S（r），则每台设备只出现一次表示为：

2.2.3 设备不出现重叠和交叉

行内的约束条件为：

xr（i）表示第 r行设备 i中心点的横坐标；lr（i）表示第r行设备i的长；d表示相邻两设备之间必须保持的最小间距，d≥0（常数）。此时将两端墙壁视为设备r（0）和r（s（r）+1），则 l0=0，l（s（r）+1）=0，x0=0；x（s（r）+1）=L。

r=1，2…，R；Yr表示第r行对应的y坐标。

同一行中，设备的中心点位于同一水平线上，即中心点的y坐标相同。因此，列方向上不重叠表示为：

r=1，2，…，R；yr+1（i），yr（j）表示相邻两行各机床的纵坐标；hr（i）表示第r行设备的宽；h表示相邻两行设备之间必须保持的最小间距，h≥0（常数）。此时，两端墙壁视为设备，y0=0，yR+1=H，y0和yR+1分别指始端和终端墙壁的y坐标。当r=0时，对于i=1，2，…，s（r），有hr（i）=0；当r=R 时，对于 i=1，2，…，s（r），有 h（r+1）（i）=0。

2.2.4 设备不超出车间范围

行内的约束条件为：

xs（r）表示第 r行中的最后一个的横坐标；xr（1）表示第r行中的第1个的横坐标；ls（r）表示第r行中的最后一个的长；lr（1）表示第r行中的第1个的长（r=1，2，…，R）；d表示相邻两设备之间必须保持的最小间距，同时也是距离墙壁的x方向最小距离，d≥0（常数）。

列内的约束条件：

R表示所有设备最终布局的行数；h表示相邻两行设备之间必须保持的最小间距，同时也是距离墙壁的y 方向最小距离，h≥0（常数）；hR（i）表示最后一行中的第i个的宽，h1（i）表示第1行中的第j个的宽。

3 模型求解

遗传算法是一种通过模拟自然进化过程搜索最优解的方法，从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。本文中的车间布局优化算法即采用遗传算法，结合生产数据实例，利用MATLAB编写代码求解模型。

3.1 染色体编码

染色体编码是利用遗传算法求解车间布局重构问题的关键，它不仅影响遗传算子的设计，还决定了搜索空间基因向解空间转换的对应关系[9]。本文中，按照设备的编码如A、B、C、D、E、F等的顺序进行编码，将设备的位置坐标对应为二进制编码，例如，设备A（2，6）对应的编码为0010 0110。

3.2 染色体初始化和适应度函数值

在初始化工作中，首先进行染色体初始化，在MATLAB编码中，人们设随机生成的中心位置对应解空间。初始随机生成各个设备位置点的x、y值，在给定的空间范围内，适应度函数（Fitness Function）值=成本值+边缘设备围成的最大面积值，描述如下：适应度函数值越低，则种群的适应度越高。初始化种群数为50。

3.3 选择算子

遗传算法中的基因，如果简单地进行杂交，很可能破坏较好的基因组合，达不到累积较好基因的目的。而精英保留策略可以避免最优个体因为杂交操作而被破坏[10]。在本文中，采用排序选择算子产生下一代，对适应度高的种群进行选择，适应度最佳的前10%直接进入下一代，并在其中随机选择20%进行交叉变异。采用精英保留策略以加快收敛速度。

3.4 交叉算子

交叉时采用多点杂交，设置交叉概率为0.8。根据算例的数据跨度，第一个点与第二个点之间的长度设为10以内的数以增加算法的稳定性与鲁棒性。比如，第一个点为第17个数，第二个点为第24个数，将这两点之间的片段进行交换，即两个染色体第3个位置片段交换。这里的位置选择也是随机的。交叉过程为：随机选择两条染色体，随机选择设备，随机选择交叉位置，如选择设备C的第3个位置进行交叉。

同时，在MATLAB中进行测试，保证交叉后设备不重叠，若交叉后有位置重叠则重新进行交叉过程，直至完成交叉过程。

3.5 变异算子

随机选择一条染色体的随机一个位置进行变异，确保变异位置在编码范围内。设置变异概率为0.3。

4 算例验证

4.1 算例背景

以某工厂智慧车间生产情况为数据来源。该车间主要负责装配件A各零件的加工与成品组装。采用半自动流水线作业方式，车间长度12m，宽度10m。车间各设备的主要参数如表1所示。

表1 车间各设备的主要参数

所有设备在X轴、Y轴方向上需要保持1m的最小间距。各个设备之间的当量物流量如表2所示，单位为（个•次）。

表2 各设备间当量物流流转量

由于当量物流量已经根据零件A的不同配件搬运难度进行了量纲化处理，所以将所有设备之间的搬运费用设为1元/m。

4.2 目标优化

选择最小物流成本作为车间布局问题评价的依据，车间规整度作为可行与否的评价条件。遗传算法的基本参数设置包括：种群大小size=50、最大代数m=1000、变异概率p=0.3、交叉概率o=0.8。在这种变异率和交叉概率中，采用遗传算法作为求解策略时，目标函数在100代成本显著减小，在400代以后成本趋于平稳，满足收敛特性，如图1所示。

4.3 优化前后对比

在MATLAB中设置最大迭代次数为1000，图2和图3为优化前和优化后的布局结果。

图1 1000代目标函数变化曲线

图2 1000代优化前车间设备布局

图3 1000代优化后车间设备布局

优化后，设备E、F、A、B、C、D的坐标分别为（6，13）、（14，13）、（18，13）、（6，10）、（10，10）、（18，10），E、F、A摆放在同一行，B、C、D摆放在另一行。目标函数值即综合成本降低90时，可以节约15.2%的物流成本，在车间规整程度节省50%的占地面积。构建的数学模型可以符合组装式车间的布局要求，优化结果可观。

[1]朱硕，江志刚，张华，等.面向再制造工艺单元重构的设备布局模型研究[J].制造技术与机床，2013，（12）：32-35.

[2]Francis R L，While J A.Facility Layout and Location：an Analytical Approach[J].Prentice Hall，1974，27(2)：112.

[3]Meller R D，Narayanan V，Vance P H.Optimal Facility Layout Design[J].Operations Research Letters，1999，（23）：117-127.

[4]Kia R，Baboli A，Javadian N，et al.Solving a Group Layout Design Model of a Dynamic Cellular Manufacturing System with Alternative Process Routings，Lot splitting and Flexible Reconfiguration by Simulated Annealing[J].Computers & Operations Research，2012，39（11）：2642-2658.

[5]曹阳华，康秀翠.基于SLP思想的车间设备布置改善研究[J].现代制造工程，2015，（8）：75-80.

[6]朱永国，何自璋，孙士平，等.多品种小批量连杆类零件的柔性制造系统构建及其车间设备布局[J].机械制造，2014，52（11）：78-81.

[7]徐双燕，丁祥海，陶俐言.多目标动态车间设施布局研究综述[J].机械研究与应用，2012，（6）：40-45.

[8]V Madhusudanan Pillai，Kankata Subbarao.A robust Cellular Manufacturing System Design for Dynamic Part Population Using a Genetic Algorithm[J].International Journal of Production Research，2008，46（18）：5191-5210.

[9]王正林，龚纯，何倩.精通MAT LAB科学计算[M].北京：电子工业出版社，2007：360-364.

[10]朱灿，梁昔明.一种多精英保存策略的遗传算法[J].计算机应用，2008，28（4）：939-941.