基于混合蚁群算法的生产系统设施规划问题研究

李 辉，朱连宇，齐二石

（天津大学管理与经济学部，天津300072）

基于混合蚁群算法的生产系统设施规划问题研究

李 辉，朱连宇，齐二石

（天津大学管理与经济学部，天津300072）

设施规划问题主要研究生产设备的布局规划，从而减小厂区内的物料搬运成本。一个有效的设施规划有利于生产过程中整体运作效率的提高。随着市场竞争的日趋激烈，市场环境处于不断的变化之中，制造企业需不断对设施布局进行重新规划来适应不断变化的市场环境对产品需求量的影响，并达到降低成本的目的。这一问题便需要用多阶段设施规划（MFLP）的方法来解决。本文提出了一种改进的混和蚁群算法（HACO）来解决带有财务预算约束的多阶段设施规划问题，并将此方法与其他一些典型的启发式算法进行了对比分析。结果表明，本文提出的HACO算法是求解带有财务预算约束的MFLP问题的一种有效的方法。

多阶段设施规划；混合蚁群算法；财务预算约束

1 引言

当今世界，全球的竞争越来越体现在经济和科技实力的竞争，而技术创新则日益成为促进经济增长和提高科技竞争力的关键。技术获取模式作为企业技术战略的重要一环，对企业长远发展意义重大。

设施规划问题主要研究生产设备的布局规划，从而减小厂区内的物料搬运成本。据统计资料表明，一个生产车间的物料搬运成本占整个生产运作成本的20%～50%，占产品生产总成本的15%-70%［1］。在一个生产车间中，一个有效的设施规划能够调整设备间的物流量，从而使每个设备在正确的时间得到正确数量的物料，这样既可以减少在制品的库存量，又能够防止厂房中机器设备的过度使用，减少物流成本。一个有效的设施规划有利于生产过程中整体运作效率的提高［2］。

物流成本主要由物料在各设备间的流动量以及各设备间的相对距离来决定。如果各设施间的物流量自始至终都是固定不变的，这样的设施规划问题称为静态设施规划问题（Static Facility Layout Problem，SFLP）［3］。相反，如果各设备间的物流量在不同的阶段内均有所变化，静态设施规划的方法就显得无能为力了，为了维持、甚至提高制造系统的效率，就需要一种新的规划方式，即根据不同时期生产系统中物流量的变化重新规划生产系统或调整生产系统结构，这就是多阶段设施规划问题（Multistage Facility Layout Problem，MFLP）。近几年，有不少学者对多阶段设施规划进行了研究。不同企业的生产制造系统划分阶段有不同的标准，可以以星期、月或年为单位划分。在一个阶段内，各设备间的物流量假定是恒定不变的。但是在不同的阶段，由于生产系统发生了变化，各设备间的物流量会有所改变，这就需要在每个阶段初期对设施布局进行重新设计［1］。导致设施间的物流量发生变化的因素主要有［4］：

（1）改变现有产品的设计；

（2）产品种类的增加或减少；

（3）现有生产设备的更换；

（4）产品生命周期的变化；

（5）产品生产计划和产量的改变。

因此，有必要设计一个柔性生产系统来应对以上因素对设备间物流量变化的影响。据统计，有1/ 3的美国企业平均每两年都会对生产系统做一次大的调整［5］。传统上，设施规划的有效应与各设备间的物流量有关。物料搬运成本的最小化通常被当作评价设施规划有效性的标准。然而对生产系统进行调整或重新规划也需要一定的费用。因此，就需要在物料搬运成本和生产系统的重新规划成本之间取得一个权衡。这就是多阶段设施规划需解决的主要问题。

许多学者都对设施规划进行过研究［6］。王盈、吴正佳［7］介绍了车间设备布局的一般原则，并依据设施规划的原则对锯片车间的重新布局方式作了系统的阐述。董海［8］基于系统布置设计SLP原理，通过计算机仿真技术，并采用Visual Basic语言编写程序，提出了对新建工厂设施布置的合理方案。王凤仙、王英利［9］应用SLP原理分析了网卡的生产过程和物流系统，提出：根据各部门之间的物流和非物流关系进行规划，使用计算机技术可以得到更合理、有弹性的车间布置。韩庆兰［10］综合考虑物流系统总成本与顾客满意度之间的平衡，提取出对物流设施规划有重要影响的因素，将其中顾客满意度这一定性因素用量化的服务水平代替，由此建立一个多目标规划模型。马彤兵、马可［11］把精益生产的思想引入了设施规划改进程序模型中，通过该模型对一个具体的实例（某变压器厂的箱体车间）进行的深入而系统的分析，对该车间的设备进行了重新布置，同时对操作人员也进行了相应的调整。

从以上文献资料可以看出，国内大多数文献都是针对静态设施规划问题进行的研究。人们开始关注多阶段设施规划问题是近些年的事。Rosenbaltt［12］第一个对多阶段设施规划问题进行了建模和求解。他是用多阶段规划的模型对MFLP问题进行了最优化求解。在求解过程中，多阶段规划模型中的每一个阶段与设施规划中的不同阶段相对应。相比于SFLP问题，MFLP问题的求解会更加复杂。对于一个有N个设备T个阶段的生产系统来说，将会有（N！）T种布局方案。因此，只有在问题规模不很大的时候才有可能在合理的运算时间内求出最优解。对于规模较大的MFLP问题，常用启发式算法进行求解。Lacksonen和Enscore［13］将一系列的静态设施规划算法进行了修正，建立了一个改进的二次规划模型。Urban［14］提出了一种基于定量布置技术（Computerized Relationship Facilities Technique，CRAFT）的启发式算法。Balakrishnan［15］提出了两种启发式算法改进了Urban的最速下降成对交换法。Conway和Venkataramanan［16］应用改进的遗传算法解决MFLP问题。Balakrishinan［17］提出了一种混合遗传算法。Kaku和Mazzola［18］提出了一种基于禁忌搜索法的启发式算法解决MFLP问题。模拟退火法也同样被用于解决MFLP问题［19］。Erel等［20］人使用多阶段规划和模拟退火法相结合的方法对MFLP问题提出了一系列启发式算法。Kochhar和Heragu［21］研究了多层多阶段设施规划问题。Balakrishman和Cheng［22］对现有的MFLP问题的各种算法进行了比较，并详细分析了各种算法的优劣性。

之前的文献很少考虑财务预算方面的约束。然而，我们应注意到，如果考虑到了财务预算方面的限制，某些阶段中的重新规划方案就变得不可行了。因此，财务预算的约束对多阶段设施规划方案的选择会产生显著的影响［23］。

2 MFLP问题描述和数学建模

SFLP问题假设各设备间的物流量是恒定不变的，因此它的规划方案是要使各设备间总的物料搬运费用最小化。而MFLP问题不仅要在每一个阶段确定一个静态布局方案，而且还要决定在下一个阶段是否进行重新规划来改变生产系统的现有布局以提高生产系统的运作效率。如果对生产系统进行重新布局规划，就会产生重新布局规划的成本。这部分成本是由于设施的移动、产量的变化或对相关人员或器材的特殊需求等原因导致的［24］。如果重新规划的成本比较低，我们就倾向于在每个阶段重新规划生产系统以维持它的高效率。相反的，如果重新规划的费用过高，我们就有可能维持现有规划方案不变。本文考虑了财务预算对MFLP的影响，在某些阶段，由于财务预算的限制，即使重新规划生产系统是有利的，也无法真正实施。

本文对MFLP问题的假设如下：

（1）各设备间的物流量随每个阶段的变化而变化，而在每个阶段内物流量恒定不变；

（2）每个设备具有相同的形状和面积；

（3）生产系统中设施能摆放的位置是确定的，并且和设施的数量相同；

（4）各位置间的相对距离是预先确定的。

MFLP问题的总成本是由各设备间的总物料搬运成本与各时期生产系统重新规划成本组成。因此，MFLP的目标函数通常被定义成各设备间的总物料搬运成本与各时期生产系统重新规划成本在各个阶段总和的最小化［7-8，20］。本文的MFLP数学模型如下所示：

其中，i，k表示生产系统中的设备，j，l表示生产系统中设备能够摆放的位置，ctjk表示在阶段t中i，k两设备间的单位物料搬运成本（两设备间一单位物料搬运一单位距离所花费的成本），ftik在阶段t中i，k两设备间的物流量，dtjl表示在阶段t中j，l两位置的距离，Atijl表示在阶段t中将设备i从位置j移动到位置l所需要的固定成本，LB表示上一阶段剩余财务预算，B表示当前阶段财务预算。

在以上模型中，公式（1）即目标函数，是要求取各阶段的物料搬运成本以及生产系统重新规划成本之和的最小值；公式（2）说明在各个阶段，每一个设备只能放在一个位置；公式（3）说明在各个阶段，每一个位置只能容纳一个设备；公式（4）说明只有当设备改变位置时，才会产生重新规划成本；公式（5）说明Xtij属于0，1变量，当在阶段t中设备i处于位置j上时，Xtij=1，否则Xtij=0；公式（6）说明Ytijl也属于0，1变量，当在阶段t的开始设备i从位置j移动到了位置l时，Ytijl=1，否则Ytijl=0。公式（5）说明生产系统重新规划成本要满足预算要求。

对于MFLP问题，我们假设在每个阶段内各设设备的物流量是恒定不变的。因此，在每个阶段内的设施规划问题均可看作是一个SFLP问题。我们用πt表示在阶段t中生产系统中N个设备、N个位置的布局方案，即πt=（π1t，π2t，…，πNt）。其中πit表示在阶段t中位置i上的设备（i=1，2，…，N）。因此，MFLP问题的一个求解方案便可表示成：

π=｛π1，π2，…，πT｝=｛（π11，π21，…，πN1），（π12，π22，…，πN2），…，（π1T，π2T，…，πNT）｝

以图1为例，图1描述了一个有6个设备3阶段的MFLP问题示例。在阶段1，设施6，4，2，1，5，3被分别安置在1，2，3，4，5，6号位置。阶段1的布局可表示成π1=（6，4，2，1，5，3）。阶段2和阶段3以此类推。因此此示例的3个阶段总的规划方案可表示成：

π=｛（6，4，2，1，5，3），（5，4，2，1，6，3），（5，4，3，1，6，3）｝

在阶段2中，设备5和设备6调换了位置，因此阶段2的重新规划成本就是将设备6从位置1移到位置5的费用加上将设备5

从位置5移到位置1的费用。由于2，3两阶段的布局没有改变，所以在阶段3并不产生重新规划成本。而且每个阶段的物料搬运成本也没有变化。这样便可计算出MFLP整体规划的总成本。

图1 一个6设施3阶段的MFLP问题示例

2 混和蚁群算法对MFLP问题的求解

2.1 蚁群算法描述

蚁群算法（Ant Colony Optimization Algorithm，ACO）是近年来新发展起来的一种启发式算法，由Dorigo等［25］在20世纪90年代首先提出，而后又进行了一系列改进。由于蚁群算法采用分布式并行计算机制，具有较强的鲁棒性，容易与其他算法结合等优点，一经提出，立即受到各领域学者的重视。近几年，蚁群算法被应用于加工车间调度问题、图形着色问题、二次分配问题、车辆路径问题等一系列NP难问题［26］。

蚁群算法模仿了自然界中蚂蚁觅食的行为，主要通过蚂蚁群体之间的信息传递而达到寻优的目的。蚂蚁在移动过程中会释放出一种称作“信息素”的化学物质。信息素浓度越高，对蚂蚁的吸引力就越强，因此蚂蚁更倾向于选择信息素浓度高的路径。一开始每个蚂蚁并不知道食物在何处，只是在本身所能见到的局部范围内搜索，并以一定的概率向其他蚂蚁留下的信息素浓度高的方向移动，同时自己也释放信息素。如果许多蚂蚁都经过了同一条路径，则此路径上的信息素浓度便会升高，后来的蚂蚁就更倾向于选择这条路径。同时所有蚂蚁释放的信息素将以一定速率挥发，因此经过一段时间后，最短路径上的信息素浓度会越来越高，从而形成一种正反馈，因此到最后所有的蚂蚁都会选择最短的路径去寻找食物。这一过程如图2所示。

图2 蚂蚁寻找最短路径过程示意图：（a）初态；（b）阶段一；（c）阶段二；（d）终态：蚂蚁集中于最短路径

为了能够有效的应用蚁群算法解决MFLP问题，我们可将蚁群算法解空间看作一种网状结构。图2描述了一个2阶段3设备的网状结构可行解示意图。在这一结构中假设只有一只蚂蚁（即一个可行解）。在第一阶段，蚂蚁所经过的位置1-2-3中的设施为2-1-3，。而在第二阶段，蚂蚁所经过的位置1-2-3中的设施为3-2-1。因此，这两个阶段的可行解便可表示成一个字符串的形式：2-1 -3-3-2-1。这一可行解也可表示成结构书的形式如图3所示。

图3 MFLP问题蚁群算法解空间的网络表示

2.2 蚁群算法求解MFLP问题的步骤

蚁群算法的核心内容包括以下三部分：（1）选择机制：某条路径上留下的信息素越多，此路径被选择的概率越大；（2）更新机制：某条路径上的信息素浓度会随着蚂蚁经过数量的增加而变大，同时信息素也会逐渐的挥发；（3）协调机制：蚂蚁之间通过信息素交换信息并相互影响。

求解过程中所用字母的含义如下：

M：蚁群规模（蚂蚁的数量）

m：蚂蚁序数（m=1，…，M）

N：设施（位置）的数量

i，z：生产系统中的设备（i，z=1，…，N）

j：生产系统中的位置（j=1，…，N）

S：阶段总数

t：阶段

F：目标函数

BLt：阶段t的最优布局方案

r：失败迭代计数器，记录连续迭代连续失败的次数

R：失败迭代的上限

Pijt：信息素浓度（在阶段t中将设施i放置在位置j中的倾向性）

Q：信息素更新参数

W：交换次数。

α：信息素挥发率

u：ACO流程迭代次数

U：ACO流程迭代上限

用蚁群算法求解MFLP问题的步骤如下：

Ⅰ.确定初始解

令Fbest=一个很大的数。从第一只蚂蚁开始（m=1）对每一只蚂蚁重复进行如下操作（重复M次）：

步骤1：随机确定第一阶段的设备布局方式，即将所有的设备随机排列。令之后的每一阶段的设备布局方式不变，因此其重新规划成本为0（π1=π2=…=πS）。

步骤2：改进过程。令r=0。计算初始布局方案的目标函数（Fm）。随机选择一个阶段，在此阶段中随机选择2个设备进行交换。检验是否满足预算约束条件。若满足条件，计算交换设备后的目标函数（Fm'）。若Fm＞Fm'，则接受改变后的布局方式，并令r=0。如果Fm＜Fm'或不满足预算约束条件，就要重新选择两个设备进行交换，并令r=r+1。

步骤3：更新最优解。如果第m只蚂蚁的目标函数（Fm）优于现阶段最优解，即Fm＜Fbest，则要更新最优解（Fbest=Fm，BLt=πt，t=1，…，S），否则，最优解不更新。

步骤4：更新蚂蚁数量（m=m+1），返回步骤1。

根据以上步骤，可确定问题的一个初始解。此时各路径上的信息素浓度为Pijt=Pijt+Q/Fbest（i= 1，…，N，t=1，…，S，Q表示所规定的目标函数的上限）。

Ⅱ.ACO流程

设置参数m=1，r=0。重复操作以下步骤，直到迭代次数达到迭代上限为止：

步骤1：更新初始解（令πt=BLt，t=1，…，S）。

步骤2：对每一只蚂蚁重复以下操作：

步骤2.1：交换过程。重复以下交换过程W次：

首先，随机选择一个阶段，并在所选阶段中随机选择一个设备u。然后，再选择一个设备v。选择设备v的概率与设备u和设备v的相关信息素浓度（Pu，lc（v），t+Pv，lc（u），t）成正比（lc（u）表示设备u的位置）。最后，交换所选两设备的位置。需要强调一点：设备v与设施u可以相同。当所选两设备相同时，说明设备的位置没有改变。

根据信息素的浓度选择设备v的具体操作如下：令

任意取q∈（0，1），选择满足以下不等式的第i个设备作为设施v：

步骤2.2：改进过程。与“Ⅰ.确定初始解”中的“改进过程”步骤完全相同。

步骤2.3：更新信息素。首先将信息素进行挥发（Pijt=Pijt*α，i=1，…，N，j=1，…，N，t= 1，…，S），再聚集信息素（Pijt=Pijt+Q/Fbest*α，i =1，…，N，j=1，…，N，t=1，…，S）。

步骤2.4：更新最优解。如果第m只蚂蚁的目标函数优于当前最优解（Fm＜Fbest），则要将最优解进行更新（Fbest=Fm，BLt=πt，t=1，…，S）。这样，下一只蚂蚁就可以使用改进后的最优解作为其初始解了。再次挥发信息素（Pijt=Pijt*α，i=1，…，N，j=1，…，N，t=1，…，S）和聚集信息素（Pijt=Pijt+Q/Fbest，i=1，…，N，j=1，…，N，t =1，…，S）。由于消除了参数α对信息素增加的影响，此时信息素浓度增加的更多。这样一来最优解被选中的概率会增加。最后令r=0。

步骤2.5：若蚂蚁数量m=M则继续执行以下步骤，否则令m=m+1，返回步骤2.1。

步骤3：如果最优解没有更新，则令r=r+1。如果r=R，则清空所有信息素（Pijt=0，i=1，…，N，j=1，…，N，t=1，…，T）并重新聚集信息素（Pijt=Pijt+Q/Fbest，i=1，…，N，j=1，…，N，t =1，…，S）。

步骤4：返回步骤1，进行下一轮迭代。

以上ACO算法的流程图如图4所示。

根据以往实验结论，以上步骤所需参数的取值如下：R=（N*S）/2，W=（N*S）/2，α=0.5，β =1。

2.3 改进的混和蚁群算法(HACO)求解MFLP问题的步骤

本文在简单蚁群算法的基础上加入了模拟退火法（SA），形成了混和蚁群算法（Hybrid Ant Colony Optimization Algorithm，HACO），从而改进了原始蚁群算法的性能。

模拟退火法是一种解决混合优化问题的随机方法，它模拟了金属煅烧退火的过程。在这一过程中，一个金属固体被加热到其融化，而后它的温度不断降低直到达到一种最低能量的状态（或称基态）。如果初始温度不够高或温度下降的过快，固体达到基态时就会产生多种缺陷。Kirkpatrick等［27］第一次运用SA解决混合优化问题。Wilhelm和Ward［28］运用SA解决SFLP问题。Baykasoglu和Gindy［29］第一次运用SA解决MFLP问题。

本文的混合蚁群算法就是用模拟退火法来替换上述蚁群算法中的两次“改进过程”。本文中的模拟退火法的步骤如下：

步骤1：定义SA参数：令T0=初始温度；T=当前温度；γ=冷却率；AM=2（N）（T2）=每一个温度下的最大设备交换次数；Tmin=0.01=最低温度。

步骤2：初始化温度变化计数器k=1。

步骤3：对于初始布局方案π=｛π1，π2，…，πS｝，计算其目标函数f（π），令BS=π，Fbest=f（π）。

步骤4：如果当前温度T≤Tmin，即停止迭代，并返回BS=π，Fbest=f（π）。否则，初始化设施交换次数计数器a=0，并设置当前温度T=T0γk-1。

图4 ACO算法流程图

步骤5：任选一阶段t，在阶段t中任意交换两个设施的位置，得到一新的规划方案π′。

步骤6：令a=a+1，计算目标函数的变化量Δf =f（π′）-f（π），如果Δf＜0，或Δf＞0且x= random（0，1）＜P（Δf）=exp（-Δf/S），则接受这一新方案，令π=π′。若Fbest＞f（π），则令Fbest=f（π），否则，拒绝这一新方案。

步骤7：如果a≥AM，更新k=k+1，返回步骤3；否则，返回步骤4。

以上步骤的流程图如图5所示。

以上模拟退火法中的各个参数值的确定方法如下：初始温度T0由公式P（Δf）=ex p（-Δf/T0）来确定，根据以往的实证研究［3］，一般设Δf=0.10 f（π），P（Δf）=0.25， 因此，T0=-0.10 f（π）/ln（0.25）。我们分别设γ=0.99，AM= 2（N）（S2）。

3 数据分析

在这一节中，我们利用Balakrishnan和Cheng［30］的文献资料中的48组检测数据来对本文所提出的简单蚁群算法（ACO）和改进的蚁群算法（HACO）的运算效率进行检验。这48组数据分三种类型，分别是每组6台设备、每组15台设备和每组30台设备，每种类型各占16组。在每种类型的数据中，阶段数为5和阶段数为10的数据各占一半，均为8组。

图5 SA算法流程图

表1至表3描述了本文提出的简单蚁群算法和改进的混和蚁群算法与其他一些用于解决MFLP问题的典型的启发式算法进行了对比，其他启发式算法包括Baykosaglu和Gindy［19］提出的模拟退火法（SA），Balakrishnan［17］提出的混合遗传算法（GA），Erel［20］提出的多阶段规划方法（DP）。为了提高算法的精确度，本文将每一个参与检验的算法对每一组检验数据均计算3次，并取其最优解。表1至表3显示了每一种算法对每一个数据经过3次计算后的最优解。简单蚁群算法和混合蚁群算法的数据分别填入“ACO”和“HACO”两列中，而模拟退火法、混合遗传算法以及多阶段规划方法所得到的最优解数据分别填入“SA”，“GA”和“DP”列中。三个表格中的粗体数字均表示每一组数据达到最优解的计算结果。

由表1可知，在6台设备的数据中，对于阶段数为5的8个数据（数据1～8），本文提出的ACO和HACO两种蚁群算法均得到了最优解。其次是GA和DP算法，分别得到了7次和6次最优解，SA算法最少，仅得到2次最优解；对于阶段数为10的8数据（数据9～16），ACO和HACO两种蚁群算法全部得到最优解，其次是DP算法，得到6次最优解，而SA算法没有出现最优解。因此，对于表1中的数据，ACO和HACO是两个最优算法。

由表2可知，在15台设备的数据中，对于阶段数为5的8个数据（数据17～24），HACO算法得到了4次最优解，而ACO算法仅得到2次最优解，其他算法（SA、GA和DP）均没有得到最优解）；对于阶段数为10的8个数据（数据25～32），HACO算法得到了5次最优解，而ACO算法仅得到1次最优解，其他三种算法没有得到最优解。由此可见，在15台设备的数据中，HACO算法明显优于其他算法。

由表3可以看出，在30台设备的数据中，对于阶段数为5的8个数据（数据33～40），HACO算法得到了6次最优解，其次是ACO和GA两种算法，均得到了1次最优解，而其他算法没有得到最优解；对于阶段数为10的8个数据（数据41～48），HACO算法得到了4次最优解，ACO和GA算法各得到2次最优解，而其他算法均无最优解。由此可见，在30台设备的数据中，HACO算法仍然是最优算法，其次是ACO和GA两种算法。

通过以上分析可以看出，在这48个设施规划数据中，SA、GA、DP和ACO方法分别得到了2次、13次、12次和22次最优解，而HACO方法则得到了36次最优解，其最优解的数量远远多于其他方法。从表1至表3中的数据我们可以看出，本文所提出的HACO方法无论是解决小规模设施规划问题还是大规模问题，均能表现出良好的性能。而其他方法在解决大规模设施规划问题时较HACO方法则有较大差距。可证明本文所提出的HACO方法是解决带有财务预算约束的多阶段设施规划问题的一种有效方法。

4 结语

本文构建了带有财务预算约束的多阶段设施规划模型，并提出了两种蚁群算法来对此模型进行求解。先用简单蚁群算法对此模型进行求解。而后再在简单蚁群算法的基础上加以改进，融入了模拟退火法，形成了混和蚁群算法，从而提高了蚁群算法的计算性能。利用Balakrishnan和Cheng［26］的48组监测数据，将本文提出的混合蚁群算法与其他一些用于解决MFLP问题的启发式算法进行比较，实践证明，本文所提出的混合蚁群算法能够有效的解决带有财务预算约束的MFLP问题。

表1 6台设备的设施规划问题的计算结果

表2 15台设备的设施规划问题的计算结果

表3 30台设备的设施规划问题的计算结果

本文认为，在本文研究的基础上，还有一些后续问题值得进一步的研究和探讨。这些问题包括：

（1）本文在模型构建中，仅以成本最小化作为模型目标函数。今后的研究可考虑建立并求解多目标模型；

（2）本文仅研究了生产车间的单层多阶段设施规划问题，今后可进一步研究多层生产车间的设施规划问题；

（3）在本文提出的算法的基础上，研究是否还有其他更加有效的算法解决此类问题。

［1］Tompkins JA，White JA，Bozer YA，et al.Facilities planning［M］.New York：Wiley，1996.

［2］Ulutas B H，Islier A A.A clonal selection algorithm for dynamic facility layout problems［J］.Journal of Manufacturing Systems，2009，28（4）：123-131.

［3］Mc Kendall Jr A R.，Shang Jin.Hybrid ant systems for the dynamic facility layout problem［J］.2006，33（3）：790-803.

［4］Shore R H，Tompkins J A.Flexible facilities design［J］.AIIE Transactions，1980，12（2）：200-205.

［5］Gupta T，Seifoddini H.Production data based similarity coefficient for machine-component grouping decisions in the design of cellular manufacturing system［J］.International Journal of Production Research，1990，28（7）：1247-1269.

［6］Liggett R S.Automated facilities layout：Past，present and future［J］.Automation in Construction，2000，9（2）：197-215.

［7］王盈，吴正佳，王魁.锯片制造车间设施规划设计［J］.机械设计与制造，2008，1：229-230.

［8］董海，计算机仿真技术在设施规划与设计中的应用［J］.沈阳大学学报.2004，16（4）：35-37.

［9］王凤仙，王英利.基于SLP法对网卡车间的物流研究与设施规划［J］.内蒙古科技与经济，2009，9：129-131.

［10］韩庆兰.物流设施规划的多目标优化模型［J］.控制与决策，2006，8：957-960.

［11］马彤兵，马可.基于精益生产的车间设施规划改善设计［J］.组合机床与自动化加工技术，2005，6：110-112.

［12］Rosenbaltt M J.The dynamics of plant layout［J］. Management Science，1986，32（1）：76-85.

［13］Lacksonen T A，Enscore E E.Quadratic assignment algorithms for the dynamic layout problem［J］.International Journal of Production Research，1993，31（3）：503-517.

［14］Urban T L.A heuristic for the dynamic facility layout problem［J］.IIE Transactions 1993，25（4）：57-63.

［15］Balakrishnan J，Cheng C H，Conway G.An improved pair-wise exchange heuristic for the dynamic plant layout problem［J］.International Journal of Production Research，2000，38（13）：3067-3077.

［16］Conway D G，Venkataramanan M A.Genetic search and the dynamic facility layout problem［J］.Computers and Operations Research，1994，21（8）：955-960.

［17］Balakrishnan J，Cheng C H，Conway D G，et al.A hybrid genetic algorithm for the dynamic plant layout problem［J］.International Journal of Production Economics，2003，86（2）：107-120.

［18］Kaku B K，Mazzola J B.A tabu search heuristic for the dynamic plant layout problem［J］.INFORMS：Journal on Computing，1997，9（4）：374-384.

［19］Baykasoglu A，Gindy N N Z.A simulated annealing algorithm for dynamic layout problem［J］.Computers and Operations Research，2001，28（4）：1403-1426.

［20］Erel E，Ghosh J B，Simon J T.New heuristic for the dynamic layout problem［J］.Journal of the Operational Research Society，2003，54（12）：1202-1275.

［21］Kochhar J S，Heragu S S.Facility layout design in a changing environment［J］.International Journal of Production Research，1999，37（11）：2429-2446.

［22］Balakrishnan J，Cheng C H.Dynamic layout algorithms：a state-of-the-art survey［J］.Omega：International Journal of Management Science，1998，26：507 -21.

［23］Balakrishnan J，Jacobs F R，Venkataramanan M A. Solutions for the constrained dynamic facility layout problem［J］.European Journal of Operational Research，1992，57（2）：280-286.

［24］Mc Kendall Jr A R.，Shang Jin，Kuppusamy S.Simulated annealing heuristics for the dynamic facility layout problem［J］.Computers&Operations Research，2006，33（8）：2431-2444.

［25］Dorigo M，Maniezzo V，Colorni A.Positive feedback as a search strategy［R］.Technical Report，1991.

［26］Baykasoglu A，Dereli T，Sabuncu I.An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems［J］.The International Journal of Management Science，2006，34（4）：385-396.

［27］Kirkpatrick S，Gelatt C D，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220（4598）：671-80.

［28］Wilhelm M R，Ward T L.Solving quadratic assignment problems by simulated annealing［J］.IIE Transactions，1987，19（1）：107-19.

［29］Baykasoglu A，Gindy N N Z.Asimulated annealing algorithm for dynamic facility layout problem［J］. Computers&Operations Research，2001，28（14）：1403 -26.

［30］Balakrishnan J，Cheng C H.Genetic search and the dynamic layout problem［J］.Computers&Operations Research，2000，27（6）：587-93.

A Research for Multi-stage Facility Layout Problem of Production System Based on Hybrid Ant Colony Optimization Algorithm

LI Hui，ZHU Lian-yu，QI Er-shi
（The College of Management and Economics，Tianjin University，Tianjin 300072，China）

Facility layout problem mainly studies the layouts of manufacturing facilities，which aims at reducing the material handling costs in the plant.An effective facility layout method can contribute to improve the overall operation efficiencies during the process of manufacturing.With the increasingly fierce competition in the market，the market environment is constantly changing.Manufacturing enterprises must continuously redesign the facility layout so as to adapt the changing production demands and reduce the cost.This problem requires the solution of Dynamic facility layout problem（DFLP）.In this paper，an improved hybrid ant colony optimization（HACO）is proposed to solve the DFLP with budget constraints. The HACO algorithm proposed by this paper can show good performance both for small and for large scale facility layout problems.There exists great gap between HACO and the other algorithms on solving large scale facility layout problems.Therefore，HACO is an effective method to solve dynamic facility layout problem with budget constraints.

dynamic facility layout problem；hybrid ant colony algorithm；budget constraint

F207

：A

1003-207(2014)01-0074-10

2012-02-01；

2012-11-21

国家自然科学基金面上项目（70671072）

朱连宇（1970-），男（满族），辽宁人，天津大学管理与经济学部，博士生，研究方向：精益生产.