邱胜海，陈曙鼎，王云霞，贾晓林
(南京工程学院机械工程学院，江苏 南京 211167)
摘要：分析了在先进制造模式下车间布局对企业生产效率的影响，针对传统SLP方法设计的车间设施布局方案存在的不足，使用遗传算法(GA)对设计方案进行优化，描述了GA求解的一般过程，建立了运用GA优化的目标函数，结合螺杆制造车间的布局参数及物流量等信息，给出了GA的具体实现过程。实例分析表明，GA在车间布局优化中具有高效性。
关键词：遗传算法；车间布局；设计；物流量；SLP方法
现代市场竞争日趋激烈，为了提高市场竞争力，越来越多的企业采用云制造等智能制造方式进行生产，先进制造模式迫使企业对生产车间进行重构或重新布局。车间设施的布局将对工艺流程、生产物流、公用动力的布置以及厂房的面积利用率等产生影响，因此现代车间设施的布局及优化成为了研究的课题之一[1]。
据统计，在产品的生产周期中，物料传输和等待的时间所占比例高达90%～95%[2]，而真正用于产品加工的时间所占比列很小，另外物料搬运等处理的费用大约占总费用的20%～50% [3]，因此生产过程中物料流动的时间是影响车间生产率的主要因素之一。改变车间内设施的布局，使设备尽可能科学、合理地布置，可有效减少搬运时间和降低生产成本。
传统的SLP(systematic layout planning)方法是一种根据物料加工工艺，将物流分析与作业单位相互间关系密切程度分析相结合,得出各个作业单位相关图，从而求得合理布置方案的方法[4-5]。SLP方法不适合用于小型车间布局的灵活设计，是因其设计过程繁琐，有较大的局限性，且很难获得最优评价方案[5-6]。遗传算法(genetic algorithm,GA)于19世纪70年代由美国的J.Holland教授首先提出，是计算智能的重要组成部分[7]。GA是模拟自然界生物进化的一种随机、并行和自适应搜索算法，它将优化参数表示成的编码串群体，根据适应度函数按照一定的概率进行选择、交叉和变异遗传操作。GA广泛应用于自动控制、规划设计、组合优化、图像处理、机器学习、信号处理、人工生命等领域[8]。为克服传统SLP方法设计的车间设施布置方案的不足，本文在SLP设计方案的基础上使用GA对设计方案进行优化，获得了较好的布局方案。
1.1 GA基本参数
GA成功的关键在于编码、遗传操作和设定遗传算法的运行参数，常见的参数包括群体(population)、基因(gene)、染色体(chromosome)、交叉(crossover)、变异(mutation)、选择(selection)、适应度(fitness)、编码(coding)等，其中群体是指选定的一组解，由一定数量的个体组成；交叉是指通过交叉原则产生一组新解的过程；变异是指编码的某一分量发生变异的过程；选择是对初始解进行初步筛查的过程；适应度是指各个体对环境的适应程度，即存活率；编码是指在二进制遗传算法中，自变量是用二进制字符串的形式表示，需要将空间坐标转换成相应的数字串；染色体是指与生物遗传规律对应的基因串，称为基因型个体，如10101100101011是某个体的染色体，其基因位数为14，染色体长度l=14。
1.2 GA运算步骤及要点描述
通常情况下，GA运行包括若干步骤，其中关键步骤是根据实际问题确定需要优化的目标函数，并确定适应度函数与适度值。适应度函数是为度量染色体的适应能力而引入的，一般可根据优化的目标函数转换得到。在车间设施布局优化的物流成本目标函数中，个体的适应度函数用来判断优化目标函数的结果是否符合物流成本最低的要求，其值等于优化目标函数的倒数，其中每个个体通过目标函数转换得到的值称为适度值，高适应度意味着有较低的总成本，低适应度代表个体会被淘汰。标准GA中，能够进入下一代的个体是适度值大的个体，通常采用赌轮选择策略得到，此方法的淘汰率较高，但易产生早熟收敛和搜索迟钝问题，因此本文采用一种改进选择方法，即按个体适度值大小排序选择算法替代赌轮选择方法，具体算法为：n个个体经过升序排列后从中选取前m(mn)个个体，定义为t，再在原群体经过降序排列后从中选取前m(mn)个个体，用t进行替换，原有中间若干个体保持不变，定义为t1，则生成的新群体s的排列方式为[t t1 t]。
在s中随机选择两个个体，确定为交叉算子并将其二进制化，位数为b。确定变异概率p，进行变异操作，结果生成新的两个交叉算子，对产生的两个新交叉算子，取随机数c(0cb)，将c位之后的数字对调，进行交叉操作；对生成的下一代群体检验其是否满足收敛要求，若不满足，用第(k+1)代代替第k代群体，直至新的群体满足收敛要求，对满足收敛要求的群体进行染色体基因编码，同时输出适应度最优个体。GA运算流程如图1所示。
2.1 算例描述
螺杆车间生产设施位置的变动往往会导致物料运输距离的改变，从而导致物料运输成本的变化。生产设施在车间中一般按照工艺配置的原则呈直线或者环形排列。已知螺杆车间的总布局为长20.0m、宽15.0m，车间内共有7处设施，螺杆的制造工艺路线为：领料(设施1：原料存储区)→下料(设施2：带锯)→粗车(设施3：普通车床)→精车(设施4：数控车床)→钻扩孔(设施5：数控钻床)→铣(设施6：加工中心)→检验(设施7：检验中心)，各个设施之间的物流量、设施尺寸及其初始坐标值见表1。根据螺杆制造工艺及切削率，运用传统SLP方法求得车间布局的初始解，如图2所示。图2的设施布局存在物流运输繁琐，效率偏低、物流搬运成本较高等问题，因此使用GA对其进行优化，以获得较为理想的布局方案。
图1 GA运算的流程图
表1 设施之间的物流量及其坐标值
设施编号物流量/kg1234567设施尺寸设施坐标(初始)168607005．0×5．012．0，15．0261741．8×2．04．0，16．0324072．3×1．22．0，13．0418663．2×1．78．0，11．5515283．1×1．714．0，10．0614412．7×3．218．0，3．572．0×2．018．0，5．0
图2 螺杆生产车间设施初始布局图
2.2 建立GA目标函数及约束条件
制造企业车间布局优化的最终目标是使不同设施之间物料的搬运成本之和最小，即单个设施与设施之间的物流量乘以相应两个设施之间的路径长度，将其作为一个目标因子，对所有的目标因子进行求和，并优化使所有的目标因子之和最小，其模型描述如下：
(1)
式中：aij为设施i和设施j之间的物流量；bij为设施i和设施j之间的路径长度。路径长度一般用欧氏距离来表示，设设施i的坐标为(xi,yi)，设施j的坐标为(xj,yj)，则
2.3 计算要点及结果分析
本实例目标函数的解是一个物流成本方案，假设群体是由5个个体组成的一组解，计算要点如下。
1)产生初始群体：对各设施坐标进行变换，每变换一次得到一个解，作为群体中的一个个体，每5个个体组成一个群，重复以上运算共产生125个群体，即为初始群体。
2)求解过程：在每个群体中进行适应度函数的计算、交叉变异、评价迭代。
3)选择个体适度值:使用每个个体的物流成本的倒数作为个体的适度值，物流成本越高个体的适度值越低，因此选择物流成本较低的个体适应度。
4)判断函数收敛：对使用以上算法得到的解进行评价，并绘制目标函数解的变化过程曲线，判断是否收敛。
5)计算结果分析：本实例计算使用Java语言实现，设定迭代次数为5，交叉率为0.4，变异率为0.11，设定图2的设施按纵向排列的初始解为[2 3 4 1 5 7 6]，其对应的物流成本优化目标函数结果为219 516，对其进行GA优化计算后，得到最优解为[5 6 4 3 7 1 2]，其对应的物流成本优化解为182 250，对应的设施最优布置方式如图3所示，优化后的各个设施的坐标值分别为设施1(18.0,7.0)、设施2(18.0,3.5)、设施3(13.5,7.0)、设施4(8.0,12.0)、设施5(2.0,13.0)、设施6(8.0,16.0)、设施7(16.0,16.0)，计算结果如图4所示。
图3 优化后车间设施布局图
图4 目标函数值随迭代次数变化的曲线
图2和图3相比，物流量最大的设施1和设施2，位置发生明显变化，与实际物流运转效率较吻合，这说明GA在设施布局优化中具有切实有效的作用。但本文方法所得的结果仍存在一定不足，比如除了设施1和设施2之外，其他设施之间的位置变化较小，分析其原因，主要是由于迭代次数有限，未能求得完全最优解。
本文针对传统的SLP方法设计的车间设施布局方案存在主观性、不唯一性等缺点，结合某型号螺杆的制造车间设施布局信息，使用GA对SLP设计的方案进行了优化，实验结果表明，GA能使SLP设计的方案更科学、合理。但GA仍存在局限性，如迭代次数太少导致只有局部最优解、容易过早收敛、算法效率低下、逆推得到车间布局的方法太过繁琐、缺乏有效定量分析方法等，若进一步将迭代与群体选取结合起来，就可做到在有限次数迭代后逼近最优解，以及优化逆推过程，提高算法效率。
参考文献：
[1] 范建民.机车转向架生产线工艺布局评价与优化研究[D].大连：大连交通大学， 2013.
[2] 李郝林，杨敏.基于生物遗传算法的车间布局优化算法[J].江苏机械制造与自动化,2001(4):35-38.
[3] 柔英娜，李建勇，李志辉.柔性制造系统鲁棒性设备布局研究[J].北方交通大学学报,2001,25(4):101-104.
[4] 周宏明，蒋祖华，付培红.设施规划[M].北京:机械工业出版社,2013.
[5] 朱耀祥，朱立强.设施规划与物流[M].北京:机械工业出版社,2010.
[6] 邱胜海，樊树海，高成冲，等.CIMS环境下车间设施规划方案综合评价方法研究[J].现代制造工程,2014(4):1-6.
[7] 席裕庚，柴天佑，恽为民.遗传算法综述[J].控制理论与应用，1996(6):697-708.
[8] 黄平，孟永钢.最优化理论与方法[M]. 北京：清华大学出版社,2009.
QIU Shenghai, CHEN Shuding, WANG Yunxia, JIA Xiaolin
(Department of Mechanical. Engineering, Nanjing Institute of Technology, Jiangsu Nanjing, 211167, China)
Abstract：It analyzes the productivity function of workshop layout in modern advanced manufacturing. Aiming at the shortage of traditional SLP method to design workshop facilities layout, it describes the general process of GA, establishes the optimized target function. Combining with the screw parts of workshop layout parameters and logistics capacity, it obtains concrete realization of the process of GA. The result shows that GA is efficient in the workshop layout optimization, improves productivity for modern enterprise production workshop and reduces logistics cost.
Key words：genetic algorithm; facility layout; design; logistics capacity; SLP method
DOI：10.3969/j.issn.2095-509X.2017.02.017
收稿日期：2016-05-20
基金项目：南京工程学院创新基金重大项目(CKJA201401, CKJA201509)；教育部人文社科青年基金项目(16YJCZH108)
作者简介：邱胜海(1967—)，男，江苏泰州人，南京工程学院副教授，工学硕士，主要研究方向为工业工程、CMIS工程设计、智能制造系统等。
中图分类号：TP391；TP311
文献标识码：A
文章编号：2095-509X(2017)02-0080-04
联系客服
