基于改进和声搜索算法的车间布局优化

2023-11-14刘冠权沈汝清潘丹丹

武汉理工大学学报(信息与管理工程版) 2023年5期

刘冠权,沈汝清,潘丹丹

(青岛理工大学管理工程学院,山东青岛 266525)

车间作为制造企业的基本生产单位,车间设施布局的合理性决定了生产的可行性和车间的经济效益。国内外研究将其视为降低生产成本和提高生产效率的关键因素。因此,在现有设施和场地的情况下,要降低生产成本,增加空间利用率,提高生产制造企业的生产效率,最好的措施是优化和改善现有厂房的布局。

目前,车间设施布局的方法主要有传统方法和启发式算法,具有代表性的传统方法是SLP法[1]。而启发式算法主要有遗传算法、粒子群算法、模拟退火算法等。邓兵等[2]针对多品种类产品,将改进的SLP和遗传算法相结合进行车间设备布局的优化。王亚良等[3]以物料搬运费用最小、单元移动费用最小、作业单元包络矩形面积最小及非物流关系最大为目标,利用引入动态变异策略的动态差分元胞多目标遗传算法进行布局模型的求解。张青雷等[4]以降低车间物料搬运成本为目标,通过动态改变惯性因子大小的动态多目标粒子群优化算法求解布局模型。葛晓梅等[5]以最小作业单元间物料搬运费用和最短搬运时间为优化目标,运用引入进化逆转操作的改进遗传算法进行布局模型的求解。靳国伟等[6]提出和声搜索算法和Dijkstra算法相结合的混合算法求解铁路物流中心分层选址分配模型。于红丽[7]以物料搬运费用最小和非物流关系密切度最大为目标函数,提出了基于SLP+和声搜索算法的工厂布局优化办法。谷培义等[8]提出一种改进的多目标和声搜索算法,引入自适应操作,并选取4个测试函数验证该算法的有效性。徐文星等[9]针对FJSP,以最大完工时间为优化目标,提出一种采用两段组合编码的改进和声搜索算法。QIAO等[10]提出一种同时考虑物料搬运成本和车间面积利用率的目标函数,并采用遗传算法进行布局模型的求解。TALAPATRA[11]将物料搬运成本最小设为目标函数,利用遗传算法求解布局模型。HONG等[12]提出一种对交叉率和变异率进行非线性处理的自适应交叉和变异策略得到的自适应遗传算法,并将其应用到求解车间布局模型问题。LI等[13]利用SLP和遗传算法求解船舶舱室设备布局模型。ZHANG等[14]构建配送中心布局优化模型,并采用SLP结合遗传算法进行求解。LENIN等[15]利用和声搜索算法来求解同时满足产品流动距离和布局面积最小化的双目标车间布局模型。

综上所述,大多数车间设施布局优化只将物流搬运费用作为单一优化目标,忽略了实际生产中非物流密切因素的影响,故笔者建立以最小物流搬运成本和最大非物流关系密切度为双目标函数的车间设施布局数学模型,针对和声搜索算法解决离散性问题时易陷入局部最优的问题,在标准和声搜索算法的基础上,引入遗传算法的交叉、变异算子代替微调带宽,以增强和声搜索算法的全局寻优能力,并通过6个规模不同的生产案例验证了算法的有效性。

1 车间布局问题描述

1.1 模型假设

笔者着重于多行设备布局问题,在实际生产中,作业单位的大小、形状各有不同,因此在构建简化后的布局模型时做出以下假设:①坐标原点设定在生产车间的左下角,X轴为车间长度方向,Y轴为车间宽度方向,车间长度为L,宽度为W;②假设车间各个作业单位均为面积固定的矩形,且长宽已知,令车间第i个作业单位为mi,i=1,2,…,n,其长度为li,宽度为wi;③作业单位进出点为其中心点,作业单位间的距离是指中心间的曼哈顿距离,且各作业单位间的物料运输路线平行于车间的长度方向或宽度方向。

基于以上模型假设,建立车间设施布局模型示意图,如图1所示。以作业单位mi为例,作业单位mi中心点的横坐标、纵坐标为xi、yi;dxij为作业单位i与j在X轴方向的距离,dyik为作业单位i与k在Y轴方向的距离。

图1 车间设施布局模型

1.2 目标函数

建立以车间物料搬运总费用P1最小和车间面积利用率P2最大为优化目标的函数:

(1)

(2)

式中:P1为生产车间作业单位间物料搬运成本;P2为生产车作业单位间的非物流关系;Qij为作业单位i与j之间的单次物料搬运成本;Fij为作业单位与之间的物料搬运频率;Dij为作业单位i与j之间的距离,这里采用的是曼哈顿距离,计算公式为Dij=|xi-xj|+|yi-yj|;Tij为作业单位i与j之间的非物流关系值,其值根据作业单位之间的密切程度等级进行定量化,具体数值如表1所示;bij为作业单位i与j之间的接近程度,称为关联度,其值由Dij决定,具体对应值如表2所示。

表1 密切程度量化表

表2 关联度值

由于两个目标的量化标准有所差异,故采用加权因子α和β来调整两个目标函数所占比重,其中α+β=1;采用归一化因子λ1和λ2来统一式(1)和式(2)的量纲,转化后的目标函数为:

(3)

(4)

(5)

式中:P为加权后的目标函数;α为物料搬运费用所占比重;β为面积利用率所占比重。

1.3 约束条件

在对车间设施进行布局优化时,需要考虑车间的实际生产情况进行约束,主要包括固定约束、边界约束和间距约束。

(1)固定约束。在生产加工过程中各作业单位需与墙壁之间保持一定的间距。

(6)

(7)

(2)边界约束。同一行作业单位在X轴方向的长度之和不超过车间的长度,同一列作业单位在Y轴方向的的长度之和不超过车间的宽度。

(8)

(9)

(3)间距约束。各个作业单位之间需保持一定的间距,且作业单位不能重叠:

(10)

(11)

(12)

2 改进和声搜索搜索算法

2.1 标准和声搜索算法

和声搜索算法(harmony search,HS)是由韩国学者GEEM等[16]提出的一种基于音乐演奏和声原理的仿人智能优化算法,算法模拟了音乐创作过程中乐师们凭借自己的记忆,通过反复调整乐队中各乐器的音调,最终达到一个美妙的和声状态的过程。和声搜索算法包含了现有的启发式算法结构,保留了类似禁忌搜索算法的初始向量元素,对应着和声搜索算法中的和声记忆库,从计算的开始到结束能够以类似模拟退火算法的方式改变适应率,即对应着和声记忆库保留概率,且以类似遗传算法的方式同步处理多个向量元素。

2.2 改进和声搜索算法设计

车间设施布局优化问题经证实是具有离散优化和非线性特性的NP-Hard问题,标准的和声搜索算法是针对离散问题设计的,但由于其对和声库、取值概率及微调概率的依赖性较强,笔者在基础和声搜索算法的基础上,引入遗传算法的交叉变异操作,将遗传算法的逆序变异代替和声搜索算法的微调带宽,即在编码长度内生成两个位置,对两个位置间的基因进行逆序变换。

(2)确定适应度函数。在遗传算法中,种群个体的适应度越大,表示种群个体的优越性越好,由于优化目标是求最小值,因此设定适应度函数为:

(13)

(3)设定编码方式。采用实数编码的方式,具体编码样式设计为[m1,m2,…,mn],表示从车间生产区域左下角开始,依次沿X轴正方向布置作业单位,如果在同一行内的作业单位长度和相互之间的距离之和超过生产车间总长度,则采取自动换行策略,由Y轴正方向另起一行,依次布置即可得到最终的车间布局图。

(14)

(15)

图2 交叉操作

(16)

变异算子可以维持染色体的多样性,避免进化中早期成熟,改善算法的局部搜索能力。在实数编码下,采用互换变异的方式进行变异操作,其基本思想为:随机选择编码长度内的两个位置,并将这两个位置上的基因进行互换。笔者采用遗传算法的逆序变异代替和声搜索算法的微调带宽,即在编码长度内随机生成两个位置a和b。对两个位置间的基因进行逆序变换,从而提高和声搜索算法的整体寻优能力,互换变异及逆序变异如图3所示。

图3 变异操作

2.3 算法步骤

改进和声搜索算法流程如图4所示,具体算法步骤为:①随机初始和声记忆库和参数,随机初始多个布局编码,解码得到对应的目标函数值,将其作为和声库HMS;②随机产生(0,1)之间的随机数rand1,如果随机数rand1小于HMCR,随机挑选HMS中的一个个体,继续进行步骤③,反之则另外随机生成一个新编码,转入步骤④;③随机产生(0,1)之间的随机数rand2,如果rand2小于PAR,则对挑选的个体进行遗传算法的逆序变异,得到新编码,反之则不调整;④解码得到新编码的目标函数值,如果该目标函数值小于和声库的最劣解(最大目标函数值对应的解),取代最劣解,反之则不取代;⑤判断是否达到创作次数Tmax,达到输出结果,否则转到步骤①。

图4 改进和声搜索算法流程图

3 算例分析

按照设施数目将其分成3种规模不同的算例,其中小规模算例为Z12[17]、T12[18],中规模算例为C16[19]、M18[20],大规模算例为Cy23[21]、A23[22]。文献中给出了每个算例具体的物流量、车间的尺寸、非物流关系密切度等。3种不同规模算例的设施数目和车间尺寸如表3所示。

表3 算例的设施数目和车间尺寸

对于上述算例,采用改进和声搜索算法(HS-GA)和遗传算法(GA)与原始布局进行对比。设施布置优化中的主要目的是最大限度地减少物料搬运,因此根据专家打分法得出α=0.6,β=0.4。通过大量实验数据验证、广泛的模拟以及参考已有文献[23],将和声记忆库的大小HMS设置为50,和声记忆库的取值概率HMCR设置为0.95,音调微调概率PAR设置为0.1,迭代次数Tmax设置为1 000,遗传算法中交叉概率Pc设置为0.9,变异概率Pm设置为0.1。在Intel(R) Core(TM) i5-6200U CPU @2.40 GHz、4.00 GB、Win10系统运行环境下,利用Matlab 2016b分别运行30次,算法终止条件为算法迭代次数达到Tmax,具体结果对比如表4所示。

表4 算例结果对比

根据表4的计算结果可以得出,改进和声搜索算法在解决小规模、中规模、大规模布局优化问题上,大都能够寻找到更优解,具有高效性,仅在中规模算例C16中出现遗传算法布局非物流关系密切度更优的情况。为了证明求解得到的优化方案的合理性,以Cy23为具体案例,根据文献中数据,计算得出目标函数中归一化因子λ1=1.844×10-8、λ2=6.250×10-3。随着迭代次数的增加,目标函数最优解会逐渐趋于稳定,利用标准遗传算法与改进和声搜索算法分别求解车间布局模型,其适应度值及迭代曲线如图5所示,标准遗传算法在迭代到736次时完成收敛,其最优目标函数值为0.039 1;改进和声搜索算法在迭代到233次时目标函数达到最优值0.007 5;原始布局的物料搬运费用为17 660 698.25元,遗传算法求解的费用为16 504 655.00元,利用改进和声搜索算法优化后的费用为14 963 323.00元,优化后布局在遗传算法布局的基础上物料搬运费用降低了9.34%;原始布局的非物流关系密切度为60.8%,遗传算法求解的密切度为57.4%,利用改进和声搜索算法优化后的密切度为63.2%,优化后布局在遗传算法布局的基础上非物流关系密切度提升了10.1%。优化后得到的车间布局作业单位布局如图6所示。