基于粒子群算法的多目标可重构设施布局方法

丁祥海 姚文鹏

杭州电子科技大学工业工程与管理研究所，杭州，310018

基于粒子群算法的多目标可重构设施布局方法

丁祥海 姚文鹏

杭州电子科技大学工业工程与管理研究所，杭州，310018

提出了一种多目标可重构设施布局方法。该方法引入了空间填充曲线来表征设施位置，可以实现任意两个设施之间的互换；考虑了柔性面积需求和设施形状约束系数等因素，保证布局方案的可行性；建立了以成本(物料运输成本和设施重构成本)和在制品库存为目标的多目标可重构设施布局模型；设计了该模型的改进粒子群算法，该算法在全局极值和个体极值的选取、Pareto解集的更新策略方面相对于标准的粒子群算法有改进。最后用算例说明了该方法的有效性。

多目标可重构设施布局;改进粒子群算法;设施形状约束系数;Pareto解集

0 引言

可重构设施布局(reconfigurable facilities layout problem，RFLP)是指已知下一周期的产品品种和数量的前提下，基于现有布局，寻求一种绩效最佳的布局方案[1-2]。在城市生产环境中产品生产数据(包括产品品种和生产数量)不确定性程度高[3]，对制造提前期、在制品(works in process，WIP)、产出率等与运作相关的绩效指标提出了明确的要求，而这些指标与布局方案相关[4]。现有研究文献中，RFLP的绩效主要集中在物料运输费用和设施重构费用方面，很少综合考虑运作方面的指标，满足不了实际需要[5-9]。这些运作指标受到生产过程中许多动态因素的影响，很难精确建模。

多目标可重构布局模型比一般的布局模型更加复杂，难以精确求解，进化算法是求解这类问题的有效选择[10-15]。粒子群优化(particle swarm optimization，PSO)算法在单目标优化算法中表现出高效性和良好的鲁棒性；而且PSO算法是基于群体操作的寻优，可以并行地得到大量非劣解，适用于求解多目标问题[16-17]。本文采用基于排队论的近似计算方法[4]，综合考虑物流运输费用、设施重构费用和WIP等绩效指标，建立了多目标可重构设施布局模型;选用PSO算法来求解多目标可重构设施布局模型，同时，针对Pareto解分布不均、局部堆积以及数量过大或过小的问题，对传统多目标PSO算法进行了改进。案例研究表明，该算法能够获得稳定和均匀的Pareto解集，能使布局决策者对可能的布局方案有更全面的认识，以便更好地权衡、折中和决策。

1 问题描述和模型构建

1.1 问题描述

(2)车间有M个设施需要进行布局。所有物料从一个进料口进入车间，从一个出料口离开车间。把车间所有设施从i=0到i=M+1进行编号，i=0为进料口，i=M+1为出料口。在布局规划时，进料口和出料口的坐标位置不变。

(6)车间划分为面积相等的网格，引入空间填充曲线来保证车间每个网格的连续性和遍历性[18-19]，可很好地防止各设施之间的重叠以及设施摆放位置超出车间边界等现象。网格分配从空间填充曲线的入口端开始，设施之间不留任何网格，没有用完的网格余留在空间填充曲线的出口端。

(8)设施形状不严格限定为矩形。为了避免产生一些不合适的形状，引入设施形状约束系数[20]。

(9)设施不能被分割。分配给一个设施的所有网格必须在同一条空间填充曲线上，且所有的网格编号是连续的。

1.2 模型构建

RFLP是为应对多品种小批量的市场环境提出来的，其绩效指标不仅包括物流成本和重构成本，还包括WIP、周期时间、生产提前期等。在一定的产出率前提下，根据Little法则，在制品库存与周期时间成比例关系，而提前期与周期时间存在内在联系。为不失一般性，本文选择费用和在制品库存为可重构设施布局的绩效评价目标。

1.2.1 成本目标

RFLP中，主要考虑设施的重构成本和物流运输成本。由于本文假定当没有任何请求时，载具将停留在最后送料的地方，故当载具接收到一个从设施i运料到设施j的指令时，从所在设施r到i有可能是空载。对一个特定的布局方案，空载将产生成本，需要加以考虑，而在现有的文献中往往忽略了空载对成本的影响。基于以上考虑，可以给出RFLP的成本目标函数：

(1)

式中，cij为从设施i到设施j移动单位距离单位物料的费用；ci为设施i的重构费用；cempty为载具空载单位距离的费用；xi为表征设施i是否重构的变量，其值取1和0；dij为从设施i到设施j的距离。

式(1)中第一项为重构成本；第二项为物流成本，考虑了载具空载的情况。xi和dij是目标函数中的决策变量。dij可用两个设施几何中心之间的距离表示，可由网格编号与网格坐标方便求得，xi描述了新旧方案中设施i的位置异同[20]。

空间填充曲线对模型的约束体现如下，设第i个设施占有Ai个网格，其沿空间填充曲线所占网格编号依次为Ai(a),…,Ai(m),Ai(n),…,Ai(b),则应满足:

(2)

Ai(n)=Ai(m)+1

(3)

(4)

(5)

f(Ai(a),…,Ai(m),Ai(n),…Ai(b))≤Klim

(6)

式(2)中，1与W分别为空间曲线的最小网格编号与最大网格编号，式(2)表示车间内足以放置M个设施且各设施均不超出车间边界；式(3)表示各个设施所占网格的连续性，保证设施不能被分割；式(4)表示不同设施之间依次相邻，很好地防止了各设施之间的重叠；式(5)表示各设施需满足柔性面积约束；式(6)表示形状约束系数对各设施形状的约束，Klim为本文规定的形状约束系数，f(·)为形状约束系数计算函数，其计算方式已在算法中体现，此处不做详细说明。

1.2.2 在制品库存目标

考虑生产过程中的不确定性，以及载具的空载等情况，布局方案会对制造系统的WIP产生直接的影响[4]。对于给定的布局方案，要求在各设施处等待加工和等待运输的期望WIP最少，目标函数如下：

(7)

式(7)中等号右边第一项表示载具的WIP期望，第二项表示在各个设施处的WIP期望。

各个设施处的期望在制品库存函数为[4]

(8)

ui=λitei

(9)

相似地，运输工具的期望WIP由下式给出[4]:

(10)

设ti是载具运输物料i所需的时间，据文献[4]，可以给出以下参数的计算公式：

(11)

(12)

(13)

(14)

(15)

i=1,2,…,M+1

(16)

trij(x)=(dri+dij)/v

πi=λi/λti=1,2,…,M+1

式中，trij(x)为载具由r设施处到i设施处，然后由i运料到j设施处所需的时间；v为载具的平均运行速度。

2 粒子群算法求解

很难找到一个布局方案，可使得费用和WIP同时最低，本文的目标是尽可能找出RFLP的Pareto解集。PSO算法中每个粒子是解空间中的一个解，它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程中所经历的最好位置，就是粒子本身找到的最优解，称为粒子i的个体极值Pb(i)；整个群体所经历过的最好位置，就是整个群体目前找到的最优解，称之为全局极值Gb。每个粒子都通过上述两个极值不断更新自己，更新公式如下：

(17)

式中，vi(t+1)、vi(t)、xi(t+1)、xi(t)分别为粒子i在时刻t+1和t的速度向量和位置向量；w为惯性权重；c1、c2为学习因子；r1、r2为随机函数。

现有多目标粒子群寻优的文献中，主要研究如何选择确定Pb(i)和Gb来更新粒子的位置和速度[16-17]，使得粒子最终收敛于Pareto解附近，但还存在着Pareto解分布不均、局部堆积以及数量过大或过小的问题。另外，多目标粒子群算法中，变量是连续的，而在多目标可重构布局问题中，布局方案是一个由整数组成的离散向量，需要对粒子群算法进行一定的改进才能适用。根据前面建立模型的特点，本文在粒子的编码和解码、初始粒子群的产生、个体极值和全局极值的选择、Pareto解的更新策略等方面进行了改进，目的是获得一个分布比较均匀的稳定的Pareto解集。

2.1 粒子的编码和解码

根据前面空间曲线网格的分配规则，只要知道每个设施在空间曲线上的起始网格编码，就能确定整个布局方案；因此每个粒子可以表示为由每个设施在空间曲线上的起始网格编码组成的M维向量(M为设施数)，如表1所示。

表1中编码表示的网格分配为:F2(1～8)，F3(9～27)，F4(28～34) ，F1(35～52) ，F5(52～60)。其中60是车间最大的网格编号。

表1 布局方案编码

由于粒子群算法为连续空间，而布局问题是整数规划问题，所以需要作相应的调整。

设xij(t)表示粒子i中设施j在第t次迭代后的起始网格编号。如果xij(t)<1,则xij(t)=1(1是最小的网格编号)；如果xij(t)>W,则xij(t)=W(W是最大的网格编号)；如果xij(t)为小数，按四舍五入方法取整；对每一个粒子i按照xij(t)的值由小到大排序，如果xij(t)相等则随机排序。

对每一个排好序的粒子，需要针对每个设施检验面积大小和形状约束系数是否满足要求，具体算法如下。

设排序后的队列为xi1(t)

(1)xi1(t)=1；

(2)forj=2 toM+1

计算并判断设施j-1的形状系数约束，如果满足则停止

Next

如果设施j-1的形状系数得不到满足，则终止

如果xi，M+1(t)>W，则终止(最后设施结束编号大于空间填充曲线最大编号)

Next

2.2 初始粒子群的产生

用设施两两互换的方法来获取初始粒子群[21-23]。在设施两两互换时，既要考虑面积相等设施之间的互换和相邻设施之间的互换，还要考虑面积不相等的不相邻的设施之间的互换[21-23]。面积不相等的不相邻的设施互换时可能产生设施重构的传导效应。当发生设施重构传导效应有多个重构方案时，选择重构费用最小的方案。该种情形下的设施两两互换的算法属于同层设施互换算法[20]。

2.3 全局极值和个体极值的选择与确定

本文为获取较均匀分布的Pareto解，对Gb和Pb(i)的选取依据为：根据各个目标函数之间的制约关系，尽可能使得每个粒子都移向解区域中不同的解，则可找到更多不同的Pareto解，以免收敛于非最优解的局部区域。

(1)Gb的确定。Gb引导Pareto粒子在目标空间中分布均匀,因此，在目标空间中选择最孤立的Pareto粒子作为Gb。本文用以下方法来选定最孤立的粒子。定义目标空间Pareto粒子i和粒子j之间的距离为

Dij=‖Fi-Fj‖

(18)

其中，Fi和Fj分别是粒子i和粒子j对应的目标向量。令：

Si=min(Dij)i≠j

(19)

Si越大，说明与Pareto粒子i相似的粒子越少,因此，取Si最大的粒子为全局极值。

(2)Pb(i)的确定。对于整个粒子群，存在两个全局极值，即GbC和GbWIP；对于粒子i，存在两个个体极值，即PbC,i和PbWIP,i(i=1,2,…,N；N是粒子的个数)(图1)。本文采用判断个体极值粒子相对全局极值粒子的离散程度来选择个体极值粒子Pb,i。令：

DGb=‖FGbC-FGbWIP‖

(20)

DPb,i=‖FPbC,i-FPbWIP,i‖

(21)

式中，DGb为两个全局极值之间的距离；DPb,i为粒子i的两个局部极值之间的距离。

图1 粒子的目标空间Fig.1 The target space of the particle

用以下算法实现Pb(i)的选择：

fori=1 toN

If (DPb,i

Pb,i=Rselect(Pb,WIP,i,PbC,i) //随机选择

Else

Pb,i=Aver(PbC,i,PbWIP,i) //可以平均，也可以按照某种比例计算

end if

Next

(3)Pareto解集的更新策略。Pareto解集更新策略的实质是在迭代过程中，采用什么机制来保存Pareto粒子，避免因粒子规模膨胀而使收敛速度慢，同时也避免Pareto解堆积在某一局部区域。本文在传统粒子群算法之外，引入三个粒子池，分别是Pareto粒子池、个体极值粒子池和新粒子池，三个粒子池和粒子群算法之间的关系如图2所示。Pareto粒子池保存每次迭代更新后的Pareto粒子，个体极值粒子池保存每次迭代后产生的每个粒子的个体极值粒子，新粒子池保存最新迭代后的粒子。为了避免因Pareto粒子数量过多，增加计算量，需要将Pareto粒子维持在一定的规模。当Pareto粒子达到限定的规模时，可以根据式(19)中的值来找出并删除发生堆积的粒子(越小，堆积越严重)。另外，为了获取更加广泛的Pareto边界(GbC和GbWIP的目标值尽可能小)，在当前目标值的基础上，可以采用模拟退火方法，继续进行局部搜索[24]，也可以选择值大的粒子进行局部搜索。具体方法，本文不作赘述。

图2 粒子的更新策略Fig.2 The update strategy of the particle

2.4 算法流程

(1)读取数据。读取的数据既包括物流数据、车间网格坐标和编号数据、初始布局方案数据、价格数据(设施重构费率、物流运输费率、载具空载费)、时间数据(每个设施加工时间的数学期望、方差和变异数)、载具平均运行速度等基础数据，还包括一些程序运行所需的数据，如迭代次数、粒子群规模、Pareto粒子规模等。

(2)计算原始方案的E[C]和E[IWIP]。

(3)产生初始粒子群。用设施两两互换的方法，产生初始粒子群规模N，确定每个粒子的位置，计算粒子i的适应度值，并令速度等于零。为了提高初始粒子群的质量，要求产生的方案在费用和在制品库存方面相对原方案不同时增加。用产生的布局方案的费用和在制品库存分别除以初始方案的费用和制造品库存。产生的布局方案应该满足ρcos t<1或ρWIP<1。

(4)更新各个粒子池中的粒子。

(5)计算粒子i的体极值PbC,i、PbWIP,i；找出两个全局极值GbC、GbWIP。

(6)计算Pareto粒子之间的Dij和Si，确定全局极值Gb。

(7)计算DGb值，对粒子i求DPb，i，并确定Pb(i)。

(8)用步骤(6)和步骤(7)求得的Gb和Pb(i)更新粒子i的速度和位置。

(9)对每个粒子进行解码，每个粒子需满足E[Ci]和E[IWIP,i]不同时增大，如果不能满足，则粒子位置不变。

(10)如满足条件中止退出，否则返回步骤(4)。

3 算例及分析

本文算例的车间网格和空间填充数据如表2所示，物流数据如表3所示，物流费用数据如表4所示，设施数据如表5所示，初始布局方案如图3所示。生产10种产品，产品需求如表6所示。入料口的坐标为(0,0)，出料口坐标为(21,31)，入口处理单位物料的平均时间为9 min，出口为9.3 min，变异系数设为1。载具运行的平均速度为1.67 m/s，单位距离空载的费用为0.01元，粒子的种群规模取20，最大迭代次数为150，Pareto解集规模取50，学习因子c1=c2=2，惯性权重w=0.5，所有设施形状系数设为1.5，设施的加工时间变异系数设为1，产品需求变异系数设为1。以上算法用MATLAB R2010b编程实现。

本算法对粒子群算法的改进主要体现在以下三个方面：

(1)针对多目标的方案选择问题，引入Pareto解集的概念，使得决策者可从多个Pareto解集方案中选出一个适合自身情况的优化方案。

(2)改善后的算法增加了算法的局部搜索能力。如图4所示，在每一次迭代运算过后，针对现有的Pareto解集中的每一个Pareto解逐个采用退火算法进行局部搜索(分别在A框、B框、C框、D框内产生适宜的新Pareto解)，使得Pareto解更加广泛。

表2 空间填充曲线的网格编号

表3 物流数据Tab.3 Logistics data

表4 物流费用数据Tab.4 Logistics cost data

表5 设施数据Tab.5 Facility data

图3 初始布局方案Fig.3 The initial layout scheme

表6 产品需求数据Tab.6 Product demand data

图4 粒子的局部搜索更新Fig.4 The updating of local search for particle

(3)选用Gb和Pb(i)，使得Pareto解更加均匀。在图4的Pareto解中，根据Gb的确定方法，A框点(与其他点的相似程度最低)所对应的方案编码将会被设定为Gb进行迭代运算，因此迭代运算后的新方案编码将会较大概率出现在A框附近，则会使得Pareto解更加均匀。

(4)算法采用最优解保存策略，限定Pareto解集的规模，加快算法收敛速度。Pareto解集的规模被限定之后，进行退火算法的局部搜索次数将会减少，此外Gb的确定过程也变得便捷，这将加快算法的收敛速度，节约算法运算时间。

改进粒子群算法结果见图5和表7。

图5 粒子群算法迭代后的情形Fig.5 The situation after the iteration by the particle swarm optimization algorithm

4 算例比较

4.1 遗传算法

遗传算法是解决搜索问题的一种通用算法，该算法的计算优化过程就如同生物学上遗传进化的过程，主要包括选择、交叉、变异三个基本操作。本算例种群规模取20,最大进化代数取150，杂交概率取0.9，变异概率取0.05，二进制编码位串的长度取20。

表7 改进粒子群算法得到的结果Tab.7 Improved particle swarm optimization algorithm results

在进行上述三个操作之前，首先需要将问题的解表示成“染色体”，即编码过程。本文采用二进制编码，码长根据设备类别数确定为20。由编码与设备的初始布局方案而得到新的布局方案，如图6所示。图中，从左到右,0表示不移动，1表示移到最末端，则上述编码(0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0)产生的新布局方案为(A B H S G T W D C V F U K E P M R L N J)。

(1)选择策略。在每次迭代之后，从种群中选取E[Ci]/E[C]与E[IWIP,i]/E[IWIP]之和最小的编码作为父代编码，母代编码则从迭代后的种群中随机选择。

(2)交叉方法。在满足交叉概率的前提下，对选取的父代编码和母代编码采用随机选取切点位置的单点交叉方式。

(3)变异根据。交叉操作之后，在满足变异概率的前提下反转子代某个基因位置的值，其中变异基因的位置随机确定。

由于此算例是多目标的，最终的结果并不是仅仅希望得到E[Ci]/E[C]与E[IWIP,i]/E[IWIP]之和的最小值，而是收集与E[C]和E[IWIP]相比,E[Ci]和E[IWIP,i]不同时增大的方案，所以在每次迭代之后会收集此方案的编码并存储，结果见图7。

图7 遗传算法迭代后的情形Fig.7 The situation after the iteration by the genetic algorithm

4.2 退火算法

本算例初始温度设为20，终止温度设为1，且采用等比例下降法降温，此比例设为0.9，此外最大迭代次数设为20，最稳定状态的步数设为20。

此算法的编码与解码原理和粒子群算法相同，编码中数据的大小顺序决定相应设备的先后排列顺序。由初始温度、终止温度以及温度下降比例三个变量控制外循环的次数，由最大迭代次数和最稳定状态的步数控制内循环的次数，并以E[Ci]/E[C]与E[IWIP,i]/E[IWIP]之和的值为比较指标(使之趋于较小值)。与遗传算法类似，在每次迭代之后会收集此方案的编码并存储，结果如图8所示。

图8 退火算法迭代后的情形Fig.8 The situation after the iteration by the annealing algorithm

4.3 三种算法的比较

综合比较三种算法在搜索Pareto解、寻优能力以及寻优速度等方面的表现，给出表8的比较结果。

表8 三种算法的综合比较

5 结论

(1)引入了空间填充曲线，并按空间填充曲线确定的顺序给设施分配面积，利用空间填充曲线的连续性，将二维的平面布局问题转化为设施网格编号的一维排列问题，降低了算法的复杂性；考虑了不同面积的设施交换时可能产生的设施重构传导效应，通过引入设施的柔性面积需求，减少了这种效应的影响；引入设施形状约束系数，使获得的布局方案更加符合实际情况。

(2)将车间近似描述为GI/G/1的网络排队模型，既考虑了设施的加工时间，又考虑了载具的处理时间；既考虑了载具送料到各个设施的到达时间间隔，又考虑了载具空载情况。

(3)采用粒子群进行求解。在计算粒子个体最佳值和全局最佳值的过程中，综合考虑了费用和在制品库存两个目标函数的影响，保证了算法收敛于非劣最优解和全局性；Pareto解集的更新策略，保证了算法的效率和解集的均匀性。

(4)本文没有考虑在制品库存和设施面积之间的关系。在实际生产中，在制品库存需要有缓冲的空间，本文虽引入了设施的柔性面积需求，但在建立的模型中没有仔细探讨它们之间的关系。在城市生产方式中，面积使用费日益提高，成为影响制造企业生产成本的重要影响因素。另外，本文没有对粒子群算法中惯性权重、学习因子等参数的设定进行讨论。

[1] MENG G ,HERAGU S S, ZIJM H. Reconfigurable Layout Problem[J]. International Journal Production Research,2004,42(22):4709-472.

[2] BENJAAFAR S，HERAGU S S，IRANI S A. Next Generation Factory Layouts: Research Challenges and Recent Progress[J]. Interfaces，2002，32(6):58-76.

[3] 王磊，付建荣. 美国都市工业的空间分布及其对中国城市发展的启示[J]. 经济地理，2014,34(8)：81-88. WANG Lei, FU Jianrong. The Spatial Distribution of Urban Manufacturing Industries in the United States and Its Implications for Urban Development in China[J].Economic Geography,2014,34(8)：81-88.

[4] WHITT W. Approximations for the GI/G/mQueue[J]. Production and Operations Management，1993，2(2):114-161.

[5] GUAN X，DAI X, QIU B， et al. A Revised Electromagnetism-like Mechanism for Layout Design of Reconfigurable Manufacturing System[J].Computer & Industrial Engineering, 2012,63(1):98-108.

[6] ABDI M R. Layout Configuration Selection for Reconfigurable Manufacturing Systems Using the Fuzzy AHP[J].International Journal Technology and Management,2009,17(1/2):149-165.

[7] 金哲，宋执环，杨将新. 可重构制造系统工艺路线与系统布局设计研究[J].计算机集成制造系统，2007,13(1)：7-12. JIN Zhe, SONG Zhihuan, YANG Jiangxin. Process Route and Layout Design Method for Reconfigurable Manufacturing Systems[J].Computer Integrated Manufacturing Systems,2007,13(1)：7-12.

[8] 武志军，宁汝新，王爱民. 可重构制造系统布局规划方案的灰色模糊综合评价方法[J]. 中国机械工程，2007,18(19):2313-2318. WU Zhijun, NING Ruxin, WANG Aimin. GreyFuzzy Synthetically Evaluation Method for RMS Layout Planning[J].China Mechanical Engineering, 2007,18(19):2313-2318.

[9] SHAFIGH F， DEFERSHA F M. A Mathematical Model for the Design of Distributed Layout by Considering Production Planning and System Reconfiguration over Multiple Time Periiods[J]. Journal of Industrial Engineering International,2015,11(3):283-295.

[10] 张屹，卢超，张虎，等. 基于差分多元目标遗传算法的车间布局优化[J]. 计算机集成制造系统，2013，19(4)：727-734. ZHANG Yi，LU Chao，ZHANG Hu，et al. Workshop Layout Optimization Based on Differential Cellular Multi-objective Genetic Algorithm[J]. Computer Integrated Manufacturing Systems，2013，19(4)：727-734.

[11] 左兴权, 王春露, 赵新超. 一种结合多目标免疫算法和线性规划的双行设备布局方法[J]. 自动化学报, 2015,41(3):528-540. ZUO Xingquan，WANG Chunlu，ZHAO Xinchao. Combining Multi-objective Immune Algorithm and Linear Programming for Double Row Layout Problem[J]. Acta Automatica Sinica，2015，41(3)：528-540.

[12] SINGH S P, SINGH V K. An Improved Heuristic Approach for Multi-objective Facility Layout Problem[J]. International Journal of Production Research,2010,48(4):1171-1194.

[13] MATAI R. Solving Multi-objective Facility Layout Problem by Modified Simulated Annealing[J]. Applied Mathemtics and Computation,2015,261(7):302-311.

[14] CHEN G Y， LO J C. Dynamic Facility Layout with Multi-objectives[J].Asia-Pacific Journal of Operational Research，2014,31(4):1450027.1-1450027.26.

[15] AIELLO G, SCALIA G L, ENEA M.A Non-dominated Ranking Multi-objective Genetic Algorithm and Electre Method for Unequal Area Facility Layout Problems[J]. Expert Systems with Applications,2013,40(12):4812-4819.

[16] 王允良，李为吉.基于混合多目标粒子群算法的飞行器气动布局设计[J]. 航空学报，2008，29(5)：1202-1206. WANG Yunliang，LI Weijie. Aerodynamic Configuration Design of Aircraft with Hybrid Multi-objective Particle Swarm Optimization[J]. Acta Aeronautica et Astronautica Sinica,2008,29(5):1202-1206.

[17] 张利彪，周春光，马铭，等. 基于粒子群算法求解多目标优化问题[J]. 计算机研究与发展，2004，41(7)：1286-1291. ZHANG Libiao， ZHOU Chunguang，MA Ming, et al. Solutions of Multi-objective Optimization Problems Based on Particle Swarm Optimization[J]. Journal of Computer Research and Development, 2004,41(7):1286-1291.

[18] BOZER Y A， MELLER R D，ERLEBACHER S J. An Improvement-type Layout Algorithm for Single and Multiple-floor Facilities[J]. Management Sci.,1994,40(7):918-932.

[19] JOHNSON R V. Spacecraft for Multi-floor Layout Planning[J]. Management Science,1982,28(2):407-417.

[20] 丁祥海.基于改进模拟植物生长算法的多层可重构设施布局方法[J].中国机械工程，2016,27(15)：2027-2034. DING Xianghai. Multi-floor Reconfigurable Facility Layout Method Based on Improved Plant Growth Simulation Algorithm[J].China Mechanical Engineering,2016,27(15):2027-2034.

[21] POURVAZIRI H，NADERI B. A Hybrid Multi-population Genetic Algorithm for the Dynamic Facility Layout Problem[J]. Applied Soft Computing，2014，24(11)：457-469.

[22] SAMARGHANDI H, TAABAYAN P, JAHANTIGH F F. A Particle Swarm Optimization for the Single Row Facility Layout Problem[J]. Cpmputer&Industrial Engineering,2010,58(4):529-534.[23] GARCA-HERNNDEZ L, PALOMO-ROMERO J M, SALAS-MORERA L, et al. A Novel Hybrid Evolutionary Approach for Capturing Decision Maker Knowledge into the Unequal Area Facility Layout Problem [J]. Expert System with Applications,2015(42):4697-4708.

(编辑 袁兴玲)

Multi-objective Reconfigurable Facility Layout Method Based on Particle Swarm Optimization

DING Xianghai YAO Wenpeng

Institute of Industrial Engineering and Management，Hangzhou Dianzi University, Hangzhou,310018

A method of multi-objective reconfigurable facilities layout was presented. The space filling curve was used to describe the facilities locations and it was possible to exchange between any two facilities. The flexibility area requirements of facility and the facility’s shape constraint coefficient were used to keep the layout solution’s feasibility. A multi-objective reconfigurable facilities layout model with costs (material transportation costs and facility reconstruction costs) and works in processes (WIP) as targets was established. An improved particle swarm optimization algorithm was designed for this model. Compared with standard particle swarm optimization the algorithm was improved in the selection of global extremum and individual extremum, and the updating strategy of Pareto solution set. Finally, an example was given to illustrate the effectiveness of this method.

multi-objective reconfigurable facility layout；improved particle swarm optimization algorithm；facility shape constraint coefficient；Pareto set

2016-09-05

国家社会科学基金资助项目(15BGL100)；NSFC-浙江两化融合联合基金资助项目(U1509220)；浙江省自然科学基金资助项目(LY13G010007)；浙江省人文社科基地资助重点项目(ZD05-2016ZB)；浙江省哲学社会科学重点研究基地浙江省信息化与经济社会发展研究中心资助项目(15XXHJD11)

TP18

10.3969/j.issn.1004-132X.2017.07.016

丁祥海，男，1971年生。杭州电子科技大学管理学院副教授。主要研究方向为工业工程、柔性装配系统等。发表论文20余篇。E-mail：dxh@hdu.edu.cn。姚文鹏，男，1992年生。杭州电子科技大学管理学院硕士研究生。