彭运芳, 孙鲁蒙, 彭雪芬, 夏蓓鑫

(上海大学 管理学院,上海 200444)

0 引言

近年来,越来越多的制造企业开始使用线边物料超市来代替传统的中央仓库以保证装配线上零件的准时化供应。装配线平衡和物料超市规划是装配系统设计的两个重要决策,企业通常在装配线平衡阶段获得最优工作站的数量,再进行物料超市的布置,这种寻优过程可能会造成超市数量或搬运成本的增加。装配线平衡和物料超市规划协同优化是站在整体的角度更系统地进行生产线规划,有效地提高装配线系统的速度和柔性,减少投资风险,增强企业竞争力。

装配线平衡问题(Assembly Line Balancing Problem,ALBP)需要在满足有限资源约束的情况下将装配工序有效地分配到各个工作站,多采用启发式算法求解,如遗传算法[1]、蚁群算法[2]、粒子群算法[3]、以及集数搜索算法[4]等。BATTINI等[5]运用分步程序来确定何时何处建设物料超市。EMDE[6]提出了一个数学模型来确定超市最佳数量和布局。ALNAHHAL和NOCHE[7]使用整数规划模型和实数遗传算法来求解超市的数量和位置,以减少运输和库存系统的固定成本。ZHOU和TAN[8]以运营成本和运输成本最小为目标建立数学模型,提出了一种具有差分进化策略的分布自适应估计算法研究超市选址问题。针对两者结合的问题,BATTINI[9]提出作为零件供应中的长期决策问题的超市规划问题应与ALBP一起考虑。针对两者结合的问题,NOURMOHAMMADI和ESKANDARI[10]提出了分阶段的数学模型,NOURMOHAMMADI等[11]提出了综合模型,但综合模型并未考虑超市的分配问题以及运输成本。2019年他们增加了对工序时间和需求的不确定的考虑,但仍然通过分阶段法进行求解[12]。2020年FATHI等[13]利用模拟退火算法对装配线平衡和超市选址问题进行求解。

综合以上研究可以发现,目前对于装配线平衡和超市规划的问题仍以分阶段方法为主,协同优化依然是一个新鲜领域。本文从装配线规划的整体角度出发,建立以最小化工作站及物料超市的建设成本和加权运输成本为目标的混合整数规划模型,设计了一种新的编码方式对遗传算法进行改进,以求解大规模问题。

1 问题描述

装配线平衡问题(ALBP)就是将具有优先次序的一系列装配工序合理地分配到各个工作站上,是生产线设计阶段的核心决策[14]。各个工序之间的优先关系,一般用优先关系图来表示,图1为经典的Bowman平衡问题,圆圈代表工序,圆圈内的数字是工序序号,箭头表示工序间的优先关系,圆圈上方的数字表示工序j的加工时间tj,圆圈下方的数字表示工序j的零件料箱需求量dj。

图1 优先关系图示例

图2显示了一个带有2个物料超市,10个工作站的直线型装配线布局图。物料超市位于其底部,装配线上所需要的零部件都按照标准尺寸装箱,贮存在物料超市里。每个工作站只能由一个超市供应物料,每个超市只能供应一段连续的工作站。每个超市s都有容量限制Caps,每个超市所负责的一段工作站(从工作站k至工作站l)的物料需求量demkl不能超过其容量限制。牵引小车从超市出发,将料箱送至对应的工作站,再返回至超市结束一次行程。牵引小车一次运送的路程distskl计算式如下:

图2 装配线布局图

distskl=|xs-xk|+|xs-xl|+|xk-xl|+

|ys-yk|+|ys-yl|+|yk-yl|

(1)

其中,xs,ys,xk,yk,xl,yl分别为超市s、超市负责的第一个工作站k和最后一个工作站l的横纵坐标,超市s到任意工作站k的路程bsk为:

bsk=|xs-xk|+|ys-yk|

(2)

图3和图4针对上述简单例子给出了分阶段法和协同优化法下的结果。其中生产节拍设定为20,每个超市容量为20,超市和工作站的建设成本均为300,单位距离成本为1,各工作站和超市横坐标分别为0,3,6,9,12,和0,9,纵坐标分别为5和0。分阶段法中先在生产节拍的约束下最小化工作站数量。小车从物料超市满载出发,每到达一个工作站而后卸下一部分物料,权重也随之改变,最后完成全部运送任务后空载返回。因此上述过程中总成本分为超市建设成本、工作站建设成本和运输成本。分阶段法的总成本计算过程如下:2×300+5×300+5×16+3×8+3×4+11+16×5+3×9+8=2342。而协同优化中,得出总成本为2330,比分阶段成本低,说明协同优化能够有效降低总成本。

图3 分阶段法优化的最优装配线平衡与物料超市规划方案

图4 协同优化的最优装配线平衡与物料超市规划方案

2 混合整数规划模型

本文用到的符号定义如下:

(1)集合与索引

N:工序集合;K:工作站集合;S:超市集合;i,j:工序,i,j∈N={1,2,…,N};k,l,m:工作站,k,l,m∈K={1,2,…,K};s:超市,s∈S={1,2,…,S}。

(2)参数

CT:生产节拍;Pij:如果工序i是工序j的紧前工序则为1,否则为0;tj:工序j的时间;dj:工序j的需求量;IC:超市的单位建设成本;SC:单位移动距离成本;xk:工作站k的横坐标;yk:工作站k的纵坐标;xs:超市s的横坐标;ys:超市s的纵坐标;distskl:从超市s到工作站k再到工作站l最后返回的距离;Caps:超市s的容量;KC:工作站的单位建设成本;a:工作站之间的距离;bsk:超市s到工作站k的距离;cls:工作站l到工作站s的距离。

(3)决策变量

M:最优工作站数量;Xjk:工序j分配给工作站k为1,否则为0;Zskl:工作站k到l由超市s负责为1,否则为0;NS:最优超市数量;Yk:工作站k建立为1,否则为0;Tdemkl:从工作站k到l的需求量;Wdisskl:从超市s到工作站k再到工作站l再返回的总加权距离。

(4)模型

建立的整体规划模型如下:

(3)

(17)

模型的目标函数(3)是最小化工作站和超市的建设成本以及总加权运输成本,其中单位建设成本和运输成本都转化为单节拍下的成本;约束(4)(5)计算开启的工作站数量和最优超市数量;约束(6)确保只有当工作站启用了才能分配工序;约束(7)(8)保证每个工序只能分配给一个工作站,每个物料超市只能负责一段工作站的物料供应;约束(9)保证工作站是连续开启的,避免出现工作站1、3开启,工作站2却未开启;约束(10)限制每个工作站的时间不能超过节拍;约束(11)(12)分别计算每个工作站的物料需求量和一段(从k到l)工作站的物料需求量;约束(13)限制了工序之间的优先关系;约束(14)限制了超市提供的物料供应不能超过超市的容量;约束(15)确保了开启的工作站都被超市供应;约束(16)计算了物料需求的加权距离;约束(17)限定了开启的超市数量的取值范围。

3 改进遗传算法设计

本文研究的问题属于分配问题,若采用传统遗传算法的两段式编码方式存在算子不可行、工序排列顺序不直观和算子修正难度增加的缺点。针对上述缺点,本文提出了改进遗传算法,采用了新的编码方式和种群初始化方法,其操作过程包括编码、种群初始化方法、选择算子、交叉算子、变异算子、解的修正,如图5所示。

图5 遗传算法流程图

3.1 编码

本文采用三部分组成的实数编码:根据工序优先关系形成工序序列POA,再以此得出工序的分配方案形成第二段染色体POB,其基因位与POA 的工序编号相对应,基因值为该工序被分配至的工作站的编号;第三段染色体POC 的基因位为工作站编号,基因值为该工作站被分配至的物料超市编号,0为该工作站没有开启。以图1中Bowman平衡问题为例,给出了两个染色体的编码,如图6所示。

图6 编码示例

3.2 种群初始化

本文初始种群的20%的工序分配染色体按照传统遗传算法生成[15],根据优先关系依次计算工序累计时间Ti,当第i工序时,Ti大于生产节拍,则将前i-1个工序分配给第1工位,依次计算直到分配完毕;另外80%染色体采用新方式生成,即根据工序的排列顺序,在不超过生产节拍和最大备选工作站的前提下将工序随机分配给工作站,并保证工作站的连续。工作站的分配是根据各工作站的工序需求量,依次计算累积作业需求量,并与物料超市容量Cap进行比较,当计算到第j个工作站的累积作业需求量大于物料超市容量时,则将前j-1个工作站分配至第1个物料超市,依次进行计算,直到分配完毕。

3.3 适应度函数构造及选择

适应度函数的值是衡量个体优劣的指标,本文中的目标函数为最小化问题,将其转化为最大化问题,个体p的适应度函数如式(18)所示。

(18)

本文采用的选择方法是最优保存方法与轮盘赌相结合,为了使进化过程中的最优解不被交叉或变异操作所破坏,种群中适应度最高的n个染色体直接复制到下一代中,然后对剩余染色体进行轮盘赌选择,适应度大的被选择概率越高。选择概率Sp如式(19)所示。

(19)

3.4 交叉

本文对POA采用单点交叉,对POB和POC采用双点交叉,具体交叉过程如图7、图8所示。通过交叉操作之后获得了新的染色体,但新染色体可能违反了容量或分配关系约束条件。此时需要对染色体进行整体修正以保证染色体的可行性。具体修正思路如下:以节拍限制为例,在子代1中,原先工序6、7均置于第6个工作站,工序时间总和为22,超过生产节拍,所以子代11中需修正为工序7分配到第5个工作站, 6、8分配到第6个工作站。

图7 染色体POA的交叉操作

图8 染色体POB+POC的交叉操作

3.5 变异

本文的变异操作是对三段染色体分别进行变异。染色体POA采用位移变异法,任意选择一个基因进行变异,将进行变异的基因重新插入不违反先后关系的任意一个位置,如图9(a)所示。POB染色体的变异方式是随机挑选一个基因,在不超过节拍的前提下将该基因位对应的基因值随机等于左边基因值或右边基因值,且工作站连续开启。其变异操作如图9(b)所示。为了保证工作站分配的多样性,本文对染色体POC采用双点变异,随机产生两个变异点,将两个变异点之间的基因值在不违反相关约束的前提下随机更换物料超市编号,其变异操作如图9(c)所示。

(a)染色体POA

4 算例验证

为了验证协同优化模型及其遗传算法的有效性和可行性,采用了SCHOLL[16]中的SALBP1测试问题进行验证。工作站间距为定值3,备选工作站及超市的数量为标准算例的1.2～1.5倍之间随机生成。各工序的物料需求在1～20内随机产生,超市至工作站距离参数需根据不同的问题规模进行设置,当超市负责一个工作站时总行程为10,之后每增加一个工作站等值递增4,依此类推。所有测试在配置为Intel○R CoreTMi7-8250U CPU处理器进行求解。

本文的数学模型用CPLEX 12.6.1进行精确求解,最长运算时间为3600秒。遗传算法在MATLAB R2017a中进行编程实现,种群规模为500代,最大迭代次数为100次。本文将结果与Amir[10]所提出的分阶段模型求解结果进行比较,验证本文所提出的协同优化的必要性。

协同优化的CPLEX、遗传算法、传统遗传算法以及分阶段方法的CPLEX运算结果如表1所示,其中M为最优工作站数量、NS为最优物料超市数量、TC为总成本。第一栏和第二栏是算例的问题和工序数量,第三栏是节拍时间CT,第四栏是超市的容量,不同的超市容量建设成本不相同[10],如表2所示。

表1 运算结果分析表

表2 工作站与物料超市建设成本

由表1可知对于小规模算例,CPLEX 和遗传算法均可在最大运行时间内找到最优解,但随着工序数量及优先关系复杂度上升,协同优化下CPLEX无法在规定时间内找到最优解,遗传算法可以很好的求解,证明遗传算法有更好的适用性;通过表中的运算结果显示,协同优化下总成本优于分阶段方式下的总成本,且在工作站数量和物料超市数量方面的决策稍有不同。综上所述,本文的协同优化方法在降低总成本方面更具有优势;改进遗传算法和传统遗传算法虽然都能找到问题的最优解和近似解,但是随着问题规模的扩大,改进遗传算法具有更好的性能,能在较短时间内找到更接近精确解的目标值。

图10为传统遗传算法和改进遗传算法的迭代曲线,横坐标表示进化代数,纵坐标代表目标函数值。可以看出传统遗传算法的适应度值在将近60代进化后才趋于近似最优解,且极易陷入局部最优解。而改进遗传算法随着进化代数的增加迅速收敛,在10代左右趋于稳定,达到近似最优解,说明改进遗传算法能够快速收敛找到近似最优解。

(a)传统遗传算法

5 结论与展望

本文针对装配线平衡和物料超市规划这两个相互关联的决策问题来优化装配线,从整体出发建立协同优化模型,并根据实际生产中的复杂性和连续性设计了适用于大规模问题的遗传算法,可以在较短时间内获得满意解。与分阶段方法的结果进行比较,协同优化方法在降低总成本方面更具有优势。本文考虑的主要是直线型装配线,在实际生产中还有其他种类的装配线,如U型装配线、双边装配线等,未来可以根据不同的装配线类型进行优化。同时,在现实生产中,工人的体力、精神状态、机器设备故障、工序复杂等都会对装配线生产活动产生影响。未来的研究可考虑从这几个方面随机化来进一步完善数学模型。