设备布局问题(facility layout problem，FLP)一直以来都是国内外学者研究的热点，主要集中在单行设备布局问题和多行设备布局问题两个方面。文献[1]提出混合分布式评价算法解决单行设备布局问题；文献[2]研究了双行设备布局问题；文献[3]提出了改进型自适应遗传算法求解多行设备布局问题；文献[4]运用非支配排序的多目标遗传算法和选举方法解决不等面积设施布局问题；文献[5]研究了遗传算法解决机器人作业单元布局问题；文献[6]提出了类交互式遗传算法解决设备布局问题。而关于设备混合布局问题(facility mixed layout problem，FMLP)却研究很少。文献[7-8]以矩形和圆形为各种仪器的表征图元，研究了三维空间混合布局优化问题；文献[9]阐述了FMLP的形式，至于数学建模和求解算法该文都没有作进一步研究；文献[10]研究了面向FMLP的设备多单元系统布局，利用“田”分形理论进行多单元布局，缺点是不能保证得到较优解。因为FMLP对布局形式没有限制，系统过于复杂，存在布局形式表达、建模与求解困难等难题，所以有必要对FMLP进行研究。

由于FMLP没有统一的布局表达形式，而多单元系统(multicell system)是由许多独立的设备单元组合而成，单元数量没有限制，可以是两个或更多。因此，本文通过构建设备单元，将FMLP转化为设备单元布局问题(facility unit layout problem，FULP)进行求解。构建多单元布局和物流路径集成优化的多目标数学模型，设计了遗传免疫蚁群混合启发式算法进行模型求解。该算法在遗传操作算子中融入了免疫算法和蚁群算法，提出带“保险柜”的自适应免疫蚁群算法选择操作，并加入了防止迂回搜索的“禁忌表”和防止非劣点流失的“保险柜”，有效提高了问题的求解质量。

1 FMLP数学建模 1.1 变量定义

首先作如下变量定义(参数关系见图1)：i(j)=1, 2,…,n，i为设备编号；u为单元编号，u=1, 2,…,U；U为单元个数，2≤U≤n–1；r为设备布置位置编号，r=1, 2,…,R，R≥n；x_i (y_i )为设备i的中点到Y(X)轴的距离；l_i 和w_i 分别为设备i的长和宽；Q_ij 为设备i到设备j的当量物流量；f_ij 为设备i到设备j的物流频率；C_ijx (C_ijy )为设备i到设备j的X(Y)轴方向的单位物流费用；c₁(c₂) 为顺(逆)向物流单位物流费用，正(负)的常数，满足|c₂|＞|c₁|；Δl_ij (Δw_ij )为设备i与设备j在X(Y)轴方向上间距；Δ_ijx (Δ_ijy )为设备i和设备j的X(Y)轴方向上净间距；(x_a, y_a), (x_b,y_b)为包络所有设备的最小矩形的左下角和右上角的坐标；s_i 为设备i的面积；S为包络车间所有设备单元的最小矩形面积；μ₁、μ₂为子目标权重，满足μ₁+μ₂=0；η₁、η₂为归一化因子；G_t为总优化目标；L、W为车间的长和宽；M_i 为第i台设备；M_j 为第j台设备；d_ijx 为设备i与设备j之间在Y轴方向必须保持的最小间距；d_ijy 为设备i与设备j在X轴方向必须保持的最小间距。设备混合布局参量、决策变量和参考线如图1所示。

1.2 基于设备单元布局集成求解的多目标数学模型

本文给出一种可同时处理单元构建和单元系统布局问题的集成解决方案，引入了设备i和设备j的X(Y)轴方向净间距Δ_ijx (Δ_ijy )变量，通过Δ_ijx (Δ_ijy )的调整来降低设备单元内和单元系统的整体物流成本和所占用面积。

考虑到物流费用和面积利用率对车间生产成本的影响，以及物流方向对物流费用的影响，构建可同时处理单元构建和单元系统布局问题的混合布局多目标优化数学模型。

$\begin{split}& \quad\quad {G_{\rm{t}}} \!=\! \min [{\mu _1}{\eta _1}\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{Q_{ij}}{f_{ij}}(\text{Δ} {l_{ij}}{C_{ijx}} \!+\! \text{Δ} {w_{ij}}{C_{ijy}})} } \!+ \\& {\mu _2}{\eta _2}(1 - \frac{{\sum\limits_i^n {{s_i}} }}{S}) \times 100\% ]{ \text{。}}\end{split}$

(1)

$\quad\quad {C_{ijx}} = \left\{ {\begin{array}{*{20}{c}}\!\!\!\!\!\!\!\!\! {{c_1},}{{x_j} - {x_i} {\text{≥}} 0;}\\\!\!\!\!{{c_2},}{{x_j} - {x_i} {\text{＜}} 0{ \text{。}}}\end{array}} \right.$

(2)

$\quad\quad{C_{ijy}} = \left\{ {\begin{array}{*{20}{c}}\!\!\!\!\!\!\!\!\!\! {{c_1},}{{y_j} - {y_i} {\text{≥}} 0;}\\\!\!\!\! {{c_2},}{{y_j} - {y_i} {\text{＜}} 0{ \text{。}}}\end{array}} \right.$

(3)

$\quad\quad \text{Δ} {l_{ij}} = {d_{ijx}} + {\textit{Δ} _{ijx}}{ \text{。}}$

(4)

$\quad\quad \text{Δ} {w_{ij}} = {d_{ijy}} + {\textit{Δ} _{ijy}}{ \text{。}}$

(5)

$\quad\quad {x_j} = {x_i} + \text{Δ} {l_{ij}} + \frac{1}{2}({l_i} + {l_j}){ \text{。}}$

(6)

$\quad\quad {y_j} = {y_i} + \text{Δ} {w_{ij}} + \frac{1}{2}({w_i} + {w_j}){ \text{。}}$

(7)

$\quad\quad S = ({x_{\rm{b}}} - {x_{\rm{a}}}) ({y_{\rm{b}}} - {y_{\rm{a}}}){ \text{。}}$

(8)

$\quad\quad {x_{\rm a}} = {\rm {min}}\{ {x_i} - \frac{1}{2}{l_i}\} { \text{，}}{x_{\rm b}} = {\rm {max}}\{ {x_i} + \frac{1}{2}{l_i}\} { \text{。}}$

(9)

$\quad\quad {y_{\rm{a}}} = \min \{ {y_i} - \frac{1}{2}{w_i}\} { \text{，}}{y_{\rm{b}}} = \max \{ {y_i} + \frac{1}{2}{w_i}\} { \text{。}}$

(10)

s.t.

$\quad\quad \sum\limits_{u = 1}^U {{x_{iu}} = 1} ,\forall i = 1,2, \cdots \!,n{ \text{。}}$

(11)

$\quad\quad \sum\limits_{i = 1}^n {{x_{iu}} {\text{≥}} 1} ,\forall u = 1,2, \cdots \!,U{ \text{。}}$

(12)

$\quad\quad \sum\limits_{r = 1}^R {{{\textit{z}}_{ir}} = 1} ,\forall i = 1,2, \cdots \!,n{ \text{。}}$

(13)

$\quad\quad \sum\limits_{i = 1}^n {{{\textit{z}}_{ir}} = 1} ,\forall r = 1,2, \cdots \!,R{ \text{。}}$

(14)

$\quad\quad {x_{\rm{a}}} {\text{≥}} 0,{y_{\rm{a}}} {\text{≥}} 0,{x_{\rm{b}}} {\text{≤}} L,{y_{\rm{b}}} {\text{≤}} W{ \text{。}}$

(15)

$\quad\quad {x_{iu}} = \left\{ {\begin{array}{*{20}{c}}\!\!\! 1\!\!\!\!\!\!\!\!\! \\\!\!\!\!\!\! 0 \!\!\!\!\!\!\!\!\!\!\!\!\!\end{array}} \right.\begin{array}{*{20}{c}}, \text{若设备}i{{\text{属于单元}}}u;\ \text{其他{ \text{。}}} \quad\quad\quad\quad\quad\quad\end{array}$

(16)

$\begin{aligned}& \quad\quad {{\text{z}}_{ir}} = \left\{ {\begin{aligned}& 1 \\& 0 \end{aligned}} \right.\begin{aligned}, & \text{若设备}i{{\text{布置在位置}}r;}\ & \text{其他。}\end{aligned} \end{aligned}$

(17)

上述公式中, 式(1)表示物流费用和面积利用率的总目标函数；式(2)和式(3)分别表示X轴和Y轴方向的单位物流费用函数；式(4)和式(5)分别表示设备i和设备j在X轴和Y轴上的距离函数；式(6)和式(7)分别表示设备j的横纵坐标函数；式(8)表示包络车间所有设备的最小矩形面积的函数；式(9)和式(10)分别表示包络所有设备的最小矩形的左下角和右上角的坐标的函数；式(11)表示一台设备只能属于一个设备单元；式(12)表示任何设备单元必须包含至少一台设备；式(13)表示任何一台设备只能布置于一个位置；式(14)表示任何一个位置只能放置一台设备；式(15)表示所有设备放在车间平面内，没有超出车间；式(16)和式(17)表示决策变量。

2 基于GIAHHA单元布局模型求解

单元构建与设备布局问题均为典型的组合优化问题，具有NP-hard属性^[11]。由算法复杂性理论可知，这类问题目前还没有最优解求解算法。在这种情况下，可以快速求得问题满意解的各类启发式算法显得更加重要。遗传算法(genetic algorithms，GA)是一种基于生物进化规律的群体优化算法，通过选择、交叉、变异等手段，不断地向最优解逼近。其优点是简单、通用、鲁棒性强，但GA具有“早熟”和“收敛速度慢”的缺点；免疫算法(immune algorithms, IA)是模仿免疫系统抗原识别、抗原与抗体结合及抗体产生过程，并利用免疫系统多样性和记忆机理抽象得到的一种算法，优点是具有学习、记忆和自适应调节的能力，但缺点是该算法的稳定性受抗体浓度的影响较大，并且可能出现“早熟收敛”现象；蚁群算法(ant colony algorithms, ACA)是一种模拟蚂蚁觅食行为的模拟优化算法，优点是具有正负反馈的特点，有间接通讯和自组织的特点，但蚁群算法“容易陷入停滞状态”和“盲目随机搜索”的不足。考虑到各启发式算法的优缺点，本文提出遗传免疫蚁群混合启发式算法(genetic-immune-ant-colony hybrid heuristic algorithms，GIAHHA)，该算法在遗传选择操作过程中，先利用免疫算法选择优秀个体，再利用自适应蚁群算法对个体进行重组，并融入非劣点“保险柜”和禁忌表，有效提高算法求解性能。该GIAHHA求解设备混合布局问题的流程图如图2所示。

2.1 染色体表达

染色体的表达方式对算法求解非常重要，既要保证染色体的合理性，又要保持问题描述的详尽。

FMLP染色体表达的主要设计工作在于如何确定设备分组，及设备单元和设备单元系统如何布置。为此，本文设计了由3部分编码构成的染色体编码方案，表达方式为v=[{m₁,m₂,…,m_n }, {a₁,a₂,…,a_n–1}，{Δ₁^x ,Δ₂^x ,…,Δ_n^x ,Δ₁^y ,Δ₂^y ,…,Δ_n^y , }]。其中，m_i 为设备i的编号；a_i 为设备单元的划分符，取值为0–1二进制编码；Δ_i^x (Δ_i^y )为设备i与相邻设备i–1在X(Y)轴方向的净间距(i=1, 2,…,n)。

2.2 进化种群产生

Step1 　随机产生n个1–n之间的编码作为设备i位置编码部分染色体基因的值，生成一条长度为n的设备位置编码；同理，随机生成长度为n–1的设备单元划分编码和长度为2n的设备净间距编码，3部分共同组成一条长度为4n–1的染色体。

Step2 　重复Step1，直到生成的染色体数目满足群体规模。

2.3 适应度和罚函数构建

适应度和罚函数决定了群体的进化方向.

根据代价极小化与利益极大化的对偶原则，适应度函数取目标函数值的倒数，因此，个体v代表的设备布局的适应度函数为

$\quad\quad E({T_v}) = 1/{G_{{\rm{t}}v}}{ \text{，}}v = 1,2, \cdots ,{\rm{pop}}\_{\rm{size}}{ \text{。}}$

(18)

式中，T_v 为第T代中个体v；G_tv为个体v的目标函数值。

罚函数包括设备重叠及超出车间尺寸。

由于设备在X轴和Y轴方向均有净间距，因此任何2个设备都不会重叠，只需构建布局超出车间尺寸的罚函数。

$\quad\quad {\lambda _{1v}} = \left\{ {\begin{aligned}& {0,} \qquad{{l_{v\max }} {\text{≤}} L;}\\& {{\theta ^{T - 1}}{\alpha _0}({l_{v\max }} - L),} \quad{{l_{v\max }} {\text{＞}} L{ \text{。}}}\end{aligned}} \right.$

(19)

$ \quad\quad {l_{v\max }} = {x_{v{\rm{b}}}} - {x_{v{\rm{a}}}}{ \text{。}} $

(20)

$\quad\quad {\lambda _{2v}} = \left\{ {\begin{aligned}& {0,} \qquad{{w_{v\max }} {\text{≤}} W;}\\& {{\theta ^{T - 1}}{\beta _0}({w_{v\max }} - W),} \quad {{w_{v\max }} {\text{＞}} W{ \text{。}}}\end{aligned}} \right.$

(21)

$\quad\quad {w_{v\max }} = {y_{v{\rm{b}}}} - {y_{v{\rm{a}}}}{ \text{。}}$

(22)

式中，λ_1v为个体v在X轴方向上超过车间尺寸的罚函数；λ_2v为个体v在Y轴方向上超过车间尺寸的罚函数；l_{v max}、w_{v max}分别为个体v在X和Y轴方向最大长度；(x_{v a},y_{v a})、 (x_{v b},y_{v b})分别为包络个体v所有设备的最小矩形的左下角和右上角的坐标；α₀、β₀为惩罚因子的初值，θ为惩罚因子的系数，θ＞1。

于是，加入惩罚项的适应度函数为

$\quad\quad E({T_v}) = \frac{1}{{{G_{{\rm{t}}v}} + {\lambda _{1v}} + {\lambda _{2v}}}}{ \text{。}} $

(23)

2.4 带“保险柜”的自适应免疫蚁群选择操作

在稳定指数排序选择的基础上，将体现抗体(个体)浓度的生物免疫算法应用于选择操作，即兼顾了个体的适应度值，又兼顾了个体浓度。再利用自适应蚁群算法的超强寻优能力，重新组合遗传基因，提高解的质量。基于自适应免疫蚁群算法的选择操作过程如下。

1)计算群体中抗体(个体)的浓度。

$\quad\quad {\phi _\upsilon } = {\left[ {\frac{1}{{{\rm{pop}}\_{\rm{size}}}}{{\sum\limits_{\upsilon =1}^{{\rm{pop}}\_{\rm{size}}} {\left( {1 + \sqrt {\sum\limits_{k = 1}^{4n{\rm{ - }}1} {{{({\upsilon _k} - {\tau _k})}^2}} } } \right)} }^{ - 1}}} \right]^{(1 - \frac{T}{{{T_{\max }}}})\gamma }}\!\!{\text{。}}$

(24)

其中，υ、τ为抗体；φ_υ 为抗体υ的浓度；k为抗体的基因位；γ为系统参数；T为进化代数；T_max为最大进化代数；υ=1, 2,…, pop_size。

φ_υ 随进化代数T的增加而最终趋于1，避免算法后期的振荡不收敛。

2)考虑到个体浓度对选择的影响，对适应度计算公式进行修改。

$\quad\quad E{({T_\upsilon })_{{\rm{after}}}} = E\left( {{T_\upsilon }} \right)/{\varphi _\upsilon }{ \text{。}} $

(25)

其中，E(T_υ )_after为调整后的适应度。

3)基于稳定指数排序选择从群体中选择ε个个体。

4)对ε个个体进行蚂蚁重组，用最优个体替换原群体中最差个体，自适应蚂蚁重组算法过程如图3所示。

自适应蚂蚁重组的思想体现在组合概率随个体的基因相似程度的增加而减小。从遗传学上来说，个体基因差异越大越有可能组合出更优秀的新个体，相反当个体趋于相同时这种可能性会越小。改进后的基于个体浓度的蚂蚁自适应选择概率

$ \quad \quad P = {\left[ {1 - {{\left( {\frac{1}{\varepsilon }\sum\limits_{\upsilon = 1}^\varepsilon {{\varphi _\upsilon }} } \right)}^2}} \right]^{\frac{3}{2}}}{ \text{ 。}}$

(26)

式中，P为蚂蚁选择概率。

5)“保险柜”储存选择过程中的非劣点。

选择过程不能保证每一父代的最优特性都能遗传到子代。由于有限的群体规模，有些非劣点在进化过程中仅出现过一二次，然后就永远消失了。为了防止这种浪费，增强算法的寻优能力，引入了非劣点“保险柜”。它将每一代中的非劣点保存起来，避免遭受遗传操作的破坏，并且“保险柜”中的个体参与每次进化过程。

2.5 交叉操作

交叉操作是新个体产生的主要方法，它决定了遗传算法的全局搜索能力。对设备位置编码和设备单元划分编码采用单点交叉方式。然而，简单的单点交叉操作使得群体的染色体具有相似性，而且对重复产生的染色体不能进行有效禁忌，容易出现迂回搜索。为此，引入禁忌表，对于交叉产生的子代个体，如果存在于禁忌表中，则直接抛弃，重新进行交叉操作；反之，则将该子代个体放入禁忌表中。对设备净间距编码部分采用算术交叉方式。

假设2个父代个体的净间距序列分别为A和B，则子代个体的净间距为

$\quad\quad A' = \sigma A + (1 - \sigma )B,B' = \sigma B + (1 - \sigma )A{\text{。}}$

其中，σ=1–0.9^T 。

交叉过程产生的一些优秀个体可能会遭到变异操作的破坏，为此，同样设置交叉过程非劣点“保险柜”，适应度值高的优秀个体被放入“保险柜”，不参与变异操作，最后与变异个体一起参与选择操作。

2.6 变异操作

变异操作是新个体产生的辅助方法，它决定了遗传算法的局部搜索能力。

设备位置编码采用互换式变异操作方式；由于设备单元划分编码部分是一个0–1二进制编码串，随机选择某基因位，将它变为相反的值以得到不同编码；对设备净间距部分，采用邻域搜索技术对设备位置进行细微的调整。

2.7 终止准则

终止条件取以下2个终止准则之一成立时终止算法操作：

1)连续5代最优个体适应度值无变化；

2)迭代次数达到预设的最大代数。

3 算例验证

为了验证本文提出的GIAHHA算法优越性，以文献[12]的案例作为验证算例(源数据参见文献[12])，设μ₁=0.7，μ₂=0.3，α₀=β₀=100，θ=1.05，交叉概率P_c=0.65，变异概率P_m=0.08，种群规模pop_size=50，进化代数T_max=1 000。分别采用本文GIAHHA算法和文献[12]的粒子群优化(particle swarm optimization，PSO)算法进行运算。

在Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz 2.30 GHz、RAM 4.00GB、Windows 10环境下，各运行30次得到的平均最优适应度和平均运行时间分别如图4和图5所示。

由图4和图5算法对比可见，本文GIAHHA算法能够在较短的时间内得到问题的更优解。基于GIAHHA最优解的车间设备混合布局见图6。

为了进一步验证本文提出的GIAHHA算法能够有效求解FMLP，仍以文献[12]的案例作为验证算例，车间有12个设备组和1个原料堆放处，因此染色体长度为51，其他参数设置同上。运行算法50次(10次/组×5组)，取运算结果中最好的一组(10次)，将其解值和文献[12]算法求解结果列于表1。其中，C_i 为第i次计算的物流费用。

因此，本文提出的GIAHHA算法在求解FMLP时是有效的和优越的。

5 结束语

本文研究了设备混合布局问题。构建了单元构建与单元布局集成求解的设备混合布局多目标数学模型，设计了GIAHHA算法进行模型求解。在GIAHHA中，根据设备单元布局的特点，设计了由设备编号、单元划分和设备净间距3部分构成的染色体编码，根据每部分编码的特点分别设计了不同的遗传操作，其中在选择操作中，提出了带“保险柜”的自适应免疫蚁群算法选择操作，有力地维护群体的多样性，防止算法的早熟收敛。最后，通过算例分析，验证了模型及算法的有效性和优越性，可为FMLP求解提供理论指导。