基于模块间约束的机床布局优化方法*

李爱平 何 琪 刘雪梅

（同济大学机械与能源工程学院，上海 201804）

机床布局是生产线布局设计中急需解决的问题。性能最优与空间最小是机械系统布局的两个主要目标。在以满足性能要求为目的的机械系统布局方面，国外 Moon［1］和 Kota［2］等人提出了分解运动变换矩阵以实现机械结构自动重组。国内的张广鹏［3］以同样的思路研究机床布局，根据刀具位姿矩阵导出了运动级联矩阵，进而生成运动功能方案，最终实现机床的结构形态方案。韩泽光［4］研究了机械产品的运动方案设计与结构方案设计，对这两个设计进行了精确的数学描述与表达，为机床的结构与布局方案设计提供了一种理论设计方法。王德伦［5］提出运动构型、尺度与结构方案相融合的机械产品创新设计状态空间方法体系，并将其应用到机床的方案设计中。在以空间最小为目的进行的机械系统布局方面，冯恩民等［6－7］对布局中的图元作了精确的数学表示，并构建了数学模型，给出了一些理论上的算法，并将改进的遗传算法应用到卫星舱的布局问题中。徐义春［8］在研究了矩形布局优化问题时设计了一种构造式算法——定位法，即将一个矩形围绕另一个已经确定位置的矩形作为参照进行部署，结合遗传算法寻优，得到了较好的计算结果。Jacquenot［9］等在2009年的 ASME设计工程国际会议上提出了多目标自由布局问题的方法，对机械产品的二维和三维布局都有一定的借鉴意义。

国内外研究学者在考虑性能或空间两者之一单个因素的机床布局研究都已经较为成熟，但是对于如何在机床空间优化布局的同时保证机床的性能这一问题还有待研究。本文在对机床的布局优化中充分考虑了性能与空间两方面的因素。在保证机床加工性能与操作性能的基础上，对机床的空间布局进行优化。具体研究的机床为其与地面接触的各个模块（床身、电气柜、排屑机构、刀库）的底面形状为矩形或可简化为矩形的这一类机床，总体思路是将三维的机床划分成多个二维矩形块作为矩形布局图元，以机床所占矩形包络面积最小为优化目标，用数学方法精确描述机床二维矩形块之间的约束。应用改进的遗传算法针对图元进行布局优化计算，得到机床布局的优化结果。

1 机床布局优化模型

1．1 问题描述

机床作为生产线上的主要加工设备，它的占地面积影响着整个生产线的布局。机床所占的矩形包络面积越小，生产线可以布局得越灵活、紧凑、高效。如何使机床在满足功能要求的同时，合理布局各个功能模块，使机床的占地面积达到最小便是本文研究的问题。

1．2 机床模块数学模型构建

机床各个模块的相对位置的确定就是机床的布局。在机床的布局过程中，首先要将机床划分为若干个相对独立的模块。由于本文研究的机床与地面接触的各个模块底面形状为矩形，可将三维机床的各个模块简化为二维矩形布局图元（床身、立柱、电气柜等）。操作工人在操作机床的时候会占据一定的操作空间，机床各个模块在布局过程中为了不与这些操作空间相干涉，本文将这些操作空间分隔出来，定义为二维矩形功能图元（控制观察区，工件装夹区等）。经过以上步骤，可得到n个二维矩形布局图元和m个二维矩形功能图元，然后对矩形图元进行精确的数学表达。具体如下所述。

以机床所占地的矩形区域T为布局的对象，首先以待布局区域的矩形T的型心为坐标原点，建立直角坐标系l1－o－l2（l1轴与矩形的长平行，l2轴与矩形的宽平行）。在矩形T上布n个二维矩形布局图元Ri，i∈In={1，2，…，n}，记Ri的型心为 xi=（xi，yi）∈R2;Ri的4个顶点按逆时针方向分别记为Pik∈R2，k∈I4={1，2，3，4}，其中 Pi1Pi2与x轴的正方向所成角度记为 θi∈（－π/2，π/2）;记平行 Pi1Pi2的单位矢量为 ui=（cosθi，sinθi），根据右手定则确定与 ui正交的单位向量 vi，vi=（－ sinθi，cosθi）;记Ri的长宽分别为 2ai1、2ai2（ai2≤ai1）;记 ai=（ai1，ai2），如图1 所示。

根据以上的定义，可以通过 xi、θi、ai唯一确定矩形图元和其在布局空间上的位置。即

n个二维矩形布局图元表示为Ri（i∈In）。m个二维矩形功能图元不参与布局，它们的位置参数由二维矩形布局图元所确定。表示为Rn+i（i∈Im），其中Im={1，2，…，m}。

1．3 布局方案

对于布局参数ai（i∈In）确定的布局图元，其布局位置 ci可由xi1、xi2、θi确定，记 ci=（xi1，xi2，θi）∈R3，称C=（c1，c2，…，cn）∈R3n为一个布局方案。

记Pxik和Pyik为矩形布局图元Ri中的顶点坐标Pik（k∈I4）的横坐标和纵坐标;称μ（C）=（Pxma－Pxmi）（Pyma－Pymi）为C的矩形包络，其中Pxma=max{Pxik}，Pxmi=min{Pxik}，Pyma=max{Pyik}，Pymi=min{Pyik}，i∈In，k∈I4。

1．4 约束描述

（1）不干涉约束

机床在布局的过程中，各个模块之间不能干涉，操作工人占据的操作空间与机床的模块不能干涉。用数学方法如下所述。

图元Ri除去边界后的那部分称为Ri的内部，记为intRi，有 intRi=Ri（xi，θi，ai）={xi+ λ1ui+ λ2vi|λk∈（－aik，aik），k=1，2}⊂R2，机床模块间、机床功能区的不干涉约束可表示为 intRi∩intRj=Ø（i≠j，i，j∈In+m），In+m={1，2，…，n+m}。

（2）相邻约束

为保证机床的性能，要求机床特定模块之间具有相邻的关系。如机床床身与立柱具有相邻关系，刀库与主轴运动区中特定换刀的位置相邻，电气柜与控制观察区相邻等。这种相邻关系的数学表达如下所述。

图元Ri的边界记为 bouRi，bouRi=Ri－ intRi。任意点P与矩形Ri相邻约束表为P∈Ri;任意两矩形相邻表为bouRi∩bouRj≠Ø，且满足不干涉约束。根据具体机床模块的约束，记点与矩形图元之间所有图元约束为dot（PRi），i∈In+m;记二维矩形图元之间所有相邻约束为 st（RiRj），其中i，j∈In+m，i≠j。

1．5 机床二维布局数学模型

在满足不干涉约束和相邻约束的条件下，使矩形包络值最小的机床布局问题的二维数学模型如下:

不干涉约束:intRi∩intRj=Ø（i≠j，i，j∈In+m）

其中In+m={1，2，…，n+m}

相邻约束:dot（PRi），i∈In+m，st（RiRj）

其中i，j∈In+m，i≠j

2 约束表达算法与优化算法

2．1 不干涉算法

根据王秀梅等［6］研究布局优化模型关于不干涉算法的证明得到，机床布局问题的不干涉约束intRi∩intRj=Ø（i≠j，i，j∈In+m）成立的充要条件为∃k'∈I4或l'∈I4，使得 max{min{（Pil－ Pik'）Tnik'|l∈I4}，min{Pik－Pjl'}Tnil'|k∈I4}}≥0，其中 Pik（k∈I4）为Ri的 4个顶点，nik为PikPi（k+1）的单位外法向量，规定Pi（4+1）=Pi1。

记 Ω=Ri∩Rj，计算 Ω 的面积S（Ω）来表示Ri与Rj两者之间的干涉程度，具体计算方法参见冯恩民等［7］关于卫星舱布局研究的论文。

2．2 相邻算法

（1）点与矩形的相邻度计算

记点P0与矩形Ri的相邻度为s（P0），则s（P0）=min{|P0Pt|}，Pt∈botRi。计算点与矩形相邻度的步骤如下:

步骤一，初始化，分别输入点 P0、Ri的型心xi、xj，旋转角θi，相邻度s（P0）=0;

步骤二，判断点P0与矩形Ri是否干涉，判断方法与判断两个矩形是否干涉的方法相同（将点P0看作矩形，即 P0=Pik，k∈I4），若干涉，则s（P0）=0，并终止，若不干涉，跳步骤三;

步骤三，计算Ri的各个顶点坐标Pik和外法向量nik;

步骤四，计算点P0到Ri各个顶点之间的向量P0Pik，确定k'，使得|P0Pik'|=min{|P0Pik|};

步骤五，判断 P0Pik·ni（k'－1）≥0是否成立，若成立，则计算P0到Pk'Pk'（k'+1）所在直线的距离smin1（点到直线的计算公式），s（P0）=smin1，终止，若不成立，转步骤六;

步骤六，判断 P0Pik·ni（k'+1）≥0是否成立，若成立，则计算P0到P（k'+1）k'Pk'所在直线的距离smin2（点到直线的计算公式），s（P0）=smin2，终止，若不成立，则s（P0）=|P0Pik'|，终止。

（2）两个矩形之间的相邻度计算

矩形Ri对矩形Rj的相邻度记为g（i→j），Ri的4个顶点与矩形Rj的相邻度分别为s（Pk），k∈I4，在4个相邻度中选取最小的两个相邻度s（Pk'），s（Pl'），则g（i→j）=s（Pk'）s（Pl'）。同理，可以计算得到矩形Rj对矩形Ri的相邻度记为g（j→i）。两个矩形Ri、Rj之间的相邻度记为gij=min{g（i→j），g（j→i）}。

将以上算法进行运算，得到的结果与用Matlab画图进行比较，验证了不干涉算法和相邻算法的正确性。

2．3 改进的遗传算法

本文针对机床带约束的布局优化问题，采用遗传算法来搜寻全局最优解。遗传算法中对布局变量进行十进制浮点数（实数）编码，采用单点杂交和正态变异，终止准则为达到最大的进化代数或者迭代20代，种群的质量都没有改进为止。在该遗传算法中，为了使重新布局的机床满足性能要求，设计了罚函数，与原目标函数结合作为整体的适应值函数，用来淘汰不满足约束的布局方案。建立适应值函数，应用遗传算法的主要步骤如下所述。

（1）适应值函数

在建立适应值函数过程中，考虑了机床占地面积、图元之间的干涉量、点与矩形之间的相邻度和两个矩形图元之间的相邻度四方面。适应值函数包括一个目标项和3个约束项（罚函数），它们之间统一了量纲，分配了相应的权重（罚因子），即

式中:S（Ω）为干涉度，s（Pu）为第u对点与矩形之间的相邻度，gv为第v对矩形之间的相邻度，p为需求相邻度的点与矩形对的总数，q为需求相邻度的矩形对的总数。ω1、ω2u、ω3v为各项的权重，它们的值可采用层次分析法根据实际机床的情况通过经验确定。

（2）染色体编码、单点杂交与正态变异

染色体编码:［x，y，θ］，其中x，y，θ分别表示矩形图元型心的x坐标、y坐标和图元相对于l1轴转过的角度;

单点杂交:对个体 c1，c2，产生一个［0，1］的随机ran，若ran＜Pc，则按均匀分布选取一个基因位，将 c1、c2的前后两部分位串进行交换。

正态变异:对于个体 c'i=ci+ ξ，ξ =（ξ1，ξ2，…，ξn），ξi～N（0，σi），i∈In，且 ξi，i∈In相互独立。

（3）改进的遗传算法的主要步骤

步骤一，初始化，设定最大的进化代数K，种群规模N，矩形布局图元的个数n，矩形功能图元m，长宽ai，需求相邻度的点与矩形对的总数p，需求相邻度的矩形对的总数q，权重系数 ω1、ω2u、ω3v，令进化代数k为0，根据直角坐标，从D⊂R3×n中选取N个个体点，作为初始种群，描述为 Pk=（c1k，c2k，…，cNk）;

步骤二，对Pk中的每个个体，依据不干涉算法，点与矩形的相邻度算法，矩形之间的相邻度算法分别得到干涉量S（Ω），相邻度s（Pu）、gv，依据式（2）计算得到适应值f（ci）;

步骤三，按均匀设计选取N个个体，对这N个个体按照概率Pc进行杂交;

步骤四，将杂交得到的N个个体按变异概率Pm进行正态变异，变异后记为Pk';

步骤五，对Pk'中的每个个体，依据不干涉算法，点与矩形的相邻度算法，矩形之间的相邻度算法分别得到干涉量S（Ω），相邻度S（Pu）、gv，依据式子（2）计算得到f（ci）;

步骤六，按适应值大小对Pk和Pk'中共2N个个体进行排序，选取适应值最小的N个个体组成Pk+1，令k=k+1;

步骤七，判断是否满足终止准则，若满足，则终止，若不满足，跳转步骤三。

3 案例分析

HMC63h型号的加工中心作为某柴油发动机缸体柔性生产线上的主要加工设备，它的占地面积直接影响到整条柔性生产线的布局和效率。同时生产线布局的场地限制也对加工中心的紧凑性提出了要求。以下以HMC63h型号的加工中心为例，应用上述优化方法对其进行布局优化。

3．1 建立机床二维矩形布局与功能图元

取HMC63h型号的机床为优化对象，将机床分为M1（床身和工作台）、M2（立柱和主轴）、M3（刀库）、M4（排屑和冷却机构）、M5（电气柜）5大模块（图2）。

将5个模块再进行垂直投影，得到与机床三维模块一一对应的二维矩形布局图元R1、R2、R3、R4、R5，即n=5，如图3、图4所示。

考虑机床的功能区域，得到两个矩形功能图元，工件装夹区（R6）和操作观察区（R7），m=2。如图 5。

应用机床模块数学模型构建方法，建立机床各个模块的数学表达，如表1所示。

表1 机床各模块的初始位置、形状参数

由表1 得到机床原布局方案 C0=（x11，x12，θ1，x21，x22，θ2，…，x71，x72，θ7）。将 C0代入式（1），得到机床原布局方案的矩形包络值μ（C0）=2．64×107mm2。

3．2 添加约束

根据机床换刀的快速性，R3（刀库）须与主轴运动区上的换刀点Pd相邻。应用点与矩形的相邻度算法得到s（Pd）。

为保证机床的加工性能，R1（床身和工作台）中的加工区与R2（立柱、主轴和床身）中的主轴运动区相邻。采用矩形之间的相邻度算法得到g12。

为便于对机床的操作观察，R5（控制柜）与R7（操作观察区）相邻。采用矩形之间的相邻度算法得到g57。

由机床以上约束知:p=1，q=2，结合式（2），建立的适应值函数为

3．3 确定权重

式（3）中 ω1、ω21、ω31、ω32为各个约束的罚因子，也可以看作是各个目标的权重。应用层次分析法，对该机床的各个性能约束进行两两比较建立成对的比较矩阵，如表2所示，经过归一化处理，令项μ（ci）前的系数确定为1，可得到各个约束的权重分别为:ω1=15．137，ω21=3．277，ω31=5．907，ω32=5．907。

表2 布局约束的比较矩阵

3．4 优化计算

将机床的原布局方案C0作为一个初始个体，应用不干涉算法得到初始干涉量S（Ω）=0，采用相邻度算法得到初始s（Pd）=0，g12=0，g57=0，将干涉量和相邻度值代入式（3）得初始适应值f（Ci）=2．64×107mm2。根据经验改变HMC63h机床各模块的布局位置，取可行的9种布局方案 C1，C2，…，C9，将它们作为9个初始个体，加上原布局方案C0，建立初始种群C0，C1，…，C9，其规模N=10。数学表达第k代种群，即

其中xikj，yikj，θikj为一条染色体上的 3 个布局参数，分别表示第k代群体中第i个个体点的第j个图元的型心的x坐标、y坐标和图元相对于l1轴转过的角度;当k=0 时，Pk表示初始种群，这时 Cik=Ci－1，i=1，2，3，…，10。

输入得到的初始值N、n、m、ai、p、q、ω1、ω21、ω31、ω32，令K=20，应用Matlab按遗传算法步骤编程实现杂交、变异和筛选的过程，计算收敛得到优化结果。由于遗传算法变异与交叉的随机性，每次得到布局图元的位置参数都会不同，为克服这一困难，将结果中R1的布局位置变换到原布局位置上，其他图元作相同的变换，变换后可得到统一的布局结果。从对称性上对布局结果略加调整，得到的机床布局结果如表3所示。

表3 各图元布局优化后的位置、形状参数

图6为最终的二维布局图，由计算得到最终的矩形包络的值为1.63×107mm2，二维占地面积减少了38.26%。对照图3和图6可以发现，位置变动的模块有R4（排屑机构）、R3（刀库）、R5（电气柜），减少的大部分占地面积是由于R4（排屑机构）的位置变动。

根据得到的机床二维布局图，布置相应的机床三维模块，得到图7机床三维俯视图和图8机床三维立体图。

HMC63h机床经过二维矩形布局图元转换，模块间约束添加，优化计算3大步骤，得到优化的布局方案。通过优化前后布局的对比，发现机床占地面积优化很大程度来自机床辅助模块的位置调整。

4 结语

本文提出了相邻算法，引用了不干涉算法，给出了改进的遗传算法。以机床所占的矩形包络面积最小为优化目标，在不干涉约束和相邻约束条件下，给出了对机床与地接触的底面模块可简化为矩形的这一类机床布局优化的一般数学建模的方法。最后引用实例，对HMC63h型号的机床进行了优化布局，得到了布局优化后的机床，其占地面积减少38.26%，验证了该方法对机床二维布局优化的有效性。

［1］Moon Y M，Kota S．Automated synthesis of mechanism using dualvector algebra［J］．Mechanism and Machine Theory，2002，37（2）:146－166．

［2］Moon YM，Kota S．Design of reconfigurable machine tools［J］．Journal of Manufacturing Science and Engineering－Transactions of the ASME，2002，124（2）:480－483．

［3］张广鹏，史文浩，黄玉美，等．数控车床结构布局形态方案创成研究［J］．中国机械工程，2003，14（21）:1805－1808．

［4］韩泽光．机械系统运动与结构方案集成设计理论与方法［D］．大连:大连理工大学，2008．

［5］王德伦，汪伟，刘彪，等．机构创新与应用［C］．中国机构与机器科学应用国际会议（2011 CCMMS）暨中国轻工机械协会科技研讨会论文集，2011:10－12．

［6］王秀梅，冯恩民，藤弘飞．旋转舱布局优化模型的主要性质及不干涉算法［J］．大连理工大学学报，1995，35（2）:125－131．

［7］冯恩民，宫召华，刘重阳，等．带性能约束的卫星舱布局问题改进遗传算法［J］．大连理工大学学报，2005，45（3）:459－463．

［8］徐义春，董方敏，刘勇，等．带平衡约束矩形布局优化问题的遗传算法［J］．模式识别与人工智能，2010，23（6）:794－801．

［9］Jacquenot G，Bennis F，Maisonneuve JJ，et al．2D－ multi－ objective placement algorithm for free－from components［EB/OL］．［2010－01－29］．