文章快速检索  
  高级检索
多约束能耗拆卸线平衡问题的改进果蝇模糊优化
蔡宁, 张则强, 朱立夏, 贾林     
西南交通大学机械工程学院, 四川 成都 610031
摘要: 为了解决实际拆卸线的能耗浪费问题,综合考虑固定工位约束、相斥约束、相容约束等多约束条件,建立了以最小化拆卸能耗、拆卸成本和均衡指数为优化目标的拆卸线优化模型.通过定义目标隶属度函数,采用最大满意度将多目标问题转化为模糊综合优化问题.设计了一种改进离散果蝇算法,采用变异方式产生邻域解,执行嗅觉操作;通过筛选最优邻域解,更新当前解,执行视觉操作.采用全局协作机制,提高全局搜索能力,并采用改进模拟退火机制,避免陷入局部最优.通过算法的对比验证,表明了该算法具有较好求解性能.最后将该算法应用于求解电视机拆卸实例,得到2个综合较优的拆卸方案,验证了模型和方法的可行性.
关键词: 多约束     能耗     模糊优化     改进果蝇算法     拆卸线平衡    
Improved Fruit-fly Fuzzy Optimization Algorithm for Multi-constrained Disassembly-line Balancing Problem Considering Energy Consumption
CAI Ning, ZHANG Zeqiang, ZHU Lixia, JIA Lin     
School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
Abstract: To solve the problem of wasting energy in actual disassembly lines, and considering the constraints of fixed position, repulsion, compatibility, and others, we propose a disassembly-line optimization model to minimize disassembly energy consumption, disassembly cost and the equilibrium index. By defining an objective membership function, we transform this multi-objective problem into a fuzzy comprehensive optimization problem with a maximum degree of satisfaction. We also design an improved discrete fruit-fly algorithm to generate a neighborhood solution. To perform the olfactory operation, we use a mutation method, and to perform the visual operation, we update the current solution by filtering the optimal neighborhood solution. We adopt the global cooperative search mechanism to improve the global search ability and adopt the improved simulated annealing mechanism to avoid getting into the local optimum. A comparison of the algorithms shows that the proposed algorithm has better performance. Finally, we apply the algorithm to solve TV disassembly examples, and obtain two kinds of disassembly schemes. The results further confirm the feasibility of the proposed method and model.
Keywords: multi-constraint     energy consumption     fuzzy optimization     improved fruit-fly algorithm     disassembly line balance    

0 引言

拆卸是产品回收再利用的关键环节,并且以流水线形式的生产组织方式可以实现大规模、自动化高效的产品拆卸.随着个性化需求的增加,机电产品淘汰的速度越来越快.据统计分析,我国每年淘汰的电子产品超过千万台,而且以大于20%的增长率逐年递增[1].另外,产品回收又是绿色制造的基本内容之一.我国制造业及其产品的能耗约占全国能耗的2/3,高能耗将成为制约我国制造业发展的重要因素[2].因此,对考虑能耗的拆卸线平衡问题(disassembly line balancing problem,DLBP)进行研究,在企业节能减排、降低成本及提高拆卸效率等方面具有重要的意义.

近些年,DLBP引起了国内外研究学者们的广泛关注,并取得了大量研究进展.在DLBP的模型建立方面,文[3]首次提出拆卸线平衡问题,建立了有缺陷零件对拆卸线平衡影响的数学模型.文[4]建立以拆卸利润为导向的不完全拆卸的混合整数规划模型;文[5]提出以最小工位数、均衡空闲时间、最小危害指数和需求指数的数学模型且证明DLBP是一类复杂的组合优化问题;文[6]提出以最小化工位数为目标的并行拆卸线平衡问题.但大多数DLBP研究都以最小工位数、最小需求指数和危害指数等为优化目标,只考虑节拍约束、任务分配约束及优先关系约束等常规约束条件,并没有考虑实际拆卸过程中能耗问题及其它约束条件.在DLBP求解方法方面,传统方法有精确求解方法[4, 7]、启发式方法[8-9],这些方法在求解小规模问题时可以求得较好解,但是随着拆卸任务的增加,会产生组合爆炸问题;另外,基于上述方法处理多目标的方式都是先决策再优化,通过线性加权转化为单一目标,但权重难以确定,受主观性影响较大.为了解决大规模复杂多目标DLBP,研究学者开始将智能算法如遗传算法[10]、粒子群算法[11]、模拟退火算法[12]、人工蜂群算法[13]用到DLBP中并取得较好效果.随后,产生了智能优化方法和Pareto的思想结合,如Pareto人工鱼群算法[14]、Pareto蚁群算法[15].这种处理多目标优化方式是先优化再决策,先筛选得到互不占优的Pareto解集,然后从多个Pareto解集中选择较优解.但面对pareto解集中非劣解过多的情况,筛选过于复杂.

果蝇优化算法(fruit-fly optimization algorithm,FOA)是基于果蝇觅食行为提出的仿生群集智能优化算法[16].果蝇通过嗅觉搜索和视觉搜索不断更新自身位置,找出味道浓度最大的个体,最终通过迭代演化找到食物的具体位置.将果蝇觅食行为模拟为算法迭代寻优过程,依据果蝇嗅觉和视觉行为来设计搜索操作.该算法参数少,复杂度低且原理简单,具有求解复杂优化问题的潜力[16].自2011年提出以来,已有许多学者将其运用到实际优化问题,如多模态函数优化[17]、车间布局与调度[18]、装配序列规划[19]、项目调度[20]等.在求解上述问题中,均表现出一定优势.但果蝇优化算法具有局部搜索能力较弱,易早熟的缺点. Metropolis准则可以避免陷入局部最优,如与遗传算法[21]、Memetic算法[22]等结合,均取得较好效果.因此,本文考虑将Metropolis准则融入到果蝇优化算法中.

因此,针对现有DLBP优化模型缺乏实际拆卸能耗的研究及多目标问题中筛选非劣解过于复杂的不足,本文建立多约束能耗DLBP数学模型,提出果蝇模糊优化的求解方法.首先,本文将拆卸能耗引入到DLBP中,同时考虑最小化拆卸成本、均衡指数两个目标,并引入固定工位约束、相斥约束和相容约束,与常规约束一起构成多约束条件,建立多约束多目标能耗DLBP优化模型.然后,运用模糊优化处理多目标的方法,将多个目标集成转化为最大满意度指标,并将FOA的嗅觉和视觉搜索进行离散化操作.为了克服FOA易早熟的缺点,在基本FOA中加入全局协作机制和Metropolis准则,提出了改进的离散果蝇优化算法(improved fruit fly optimization algorithm,IFOA).最后,验证了所提方法求解多目标DLBP的可行性,并将IFOA应用于求解电视机拆卸实例,得到综合较优的拆卸方案.

1 考虑能耗的BLBP数学模型 1.1 问题描述

拆卸生产线,是一种大规模高效生产的组织形式,由若干个工位及连接这些工位的传动装置组成.废旧机电产品按照一定优先顺序,依次经过各个工位,并按照预先设定的生产节拍完成各工位的拆卸作业任务,最后将有用零件的拆卸并回收.如图 1所示.

图 1 拆卸线示意图 Figure 1 The schematic diagram of disassembly line

DLBP可定义为:有一个拆卸作业任务集合,每个作业任务之间存在优先约束关系,在满足节拍约束、工位约束、任务分配等多约束关系的前提下,合理分配各作业任务,使得工位数、各工位空闲作业时间尽可能少,拆卸效率尽可能高,达到多个目标综合协同优化.

在当今低碳经济的大环境下,废旧产品在拆卸回收过程中必须重视能耗问题,本文主要考虑拆卸线上2类能耗:主要能耗和辅助能耗.探求一种最优的作业任务分配方案,使得拆卸过程能耗、拆卸成本和均衡指数综合优化.为方便模型的的建立,本文假设:

1) 每次换向操作都需要机器完成且每次主要能耗相等,为已知量.

2) 每个拆卸任务不可分开执行.

3) 每个工位的单位时间通风、照明辅助能耗均相同且为已知量.

4) 拆卸时处于理想状态,不存在突发中断情况.

5) 拆卸作业时间为确定已知量.

1.2 符号说明

n:总的拆卸作业数目.

M:总的拆卸工位数目.

il:拆卸作业的编号,il∈{1,2,…,n}.

k:拆卸工位编号,k∈{1,2,…,M}.

xik:决策变量,任务i是否分配给工位k,若是则为1,否则为0.

Sk:0-1变量,第k个工位是否开启,若是则为1,否则为0.

ER:变向一次的主要能耗,单位J/次,为已知量.

E1:单位时间每个工位通风能耗,单位J/s,为已知量.

E2:单位时间每个工位照明能耗,单位J/s,为已知量.

ui:第i个拆卸任务作业的单位拆卸成本,为已知量.

CT:给定的拆卸节拍,是固定值.

Ri:0-1变量,指拆卸序列上第i个位置上操作方向的变动性.

ri:第i个拆卸任务的操作方向,共分为6种:±x,±y,±z,取值分别为±1,±2,±3.

W:固定工位约束集合,特殊拆卸作业i必须分配到工位k的(ik)集合.

C:相容约束集合,必须分配到一个工位的(il)集合.

IC:相斥约束集合,不能分配到同一个工位的(il)集合.

P:任务优先关系矩阵P=[ali]n×n,若任务li的紧前任务,则ali=1;否则为ali=0.

1.3 目标函数

为了实现DLBP的优化,决策者希望最终的拆卸方案既能满足拆卸线的平衡性,又能综合考虑实际生产的能耗问题、工人因素和经济成本,多目标优化是解决上述问题的有效方法.针对拆卸线平衡问题的特点,当前考虑如下的3个目标:最小化拆卸能耗、最小化均衡指数、最小化拆卸成本.

1.3.1 最小化拆卸能耗

从能耗角度,废旧产品在实际拆卸回收过程中存在2大类能耗:

1) 主要能耗是指直接作用于废旧产品的能源消耗,例如翻转、传送等操作所需的能耗.依据调研结果,转向操作引起的能耗占主要地位,因此本文只考虑拆卸方向改变引起的能耗,用表示.

2) 辅助能耗是指协助拆卸过程的高效完成,包括每个工位通风和照明设备的能耗,用(E1+E2M·CT表示.因此,总的拆卸能耗为二者能耗之和,其目标函数为

(1)
1.3.2 最小化均衡指数

从工人角度,同一个工位由一个工人负责完成拆卸作业,每个工位时间可能小于节拍,因此会产生空闲时间,然而空闲时间的产生就造成时间浪费;同时每个工位的空闲时间不同,这样就造成工位负荷不均衡.为实现工人间的公平性,用最小化均衡指数函数来表示,其可同时兼顾工位数最少和空闲时间最小两个目标[23],其表达式为

(2)
1.3.3 最小化拆卸成本

从经济方面,产品拆卸要尽可能为企业创造最大利润,因此拆卸成本要尽可能最小化.同时,每个工位拆卸任务不一样,每个拆卸任务对工人的技术水平需求也不一样,用分配在某工位所有拆卸任务的单位拆卸成本最大值作为该工位的单位拆卸成本[15].其对应的目标表达式为

(3)
1.4 约束条件

对拆卸线进行设计时,受生产环境、工艺要求及人因等多因素影响,需要考虑多种约束条件,除了节拍约束、优先关系约束、工位约束和任务分配约束之外[13-14, 23],还需要考虑相斥约束、相容约束和固定工位约束[24-25].

1) 节拍约束.任何一个开启的工位k的所有拆卸作业任务i的作业时间之和不能超过节拍,否则无法完成规定的拆卸产量:

(4)

2) 相斥约束.对于某些拆卸作业任务,必须分开独立进行拆卸作业,不能同时分配给相同工位,如涉及燃油的拆卸任务和需要切割产生电火花的拆卸作业任务:

(5)

3) 相容约束.需要特殊技能要求的拆卸任务必须分配在同一个工位,由同一个工人完成拆卸任务且同时提高设备利用率:

(6)

4) 固定工位约束.基于区域限制或者需要特殊设备及特殊技能工人的要求,必须分配给某一个特定工位,如冷媒的回收,需要特定设备,否则造成污染或者对工人造成伤害:

(7)

5) 优先关系约束.基于零件之间的物理属性,零件拆卸必须满足优先约束关系,即保证拆卸序列的可行性:

(8)

6) 工位约束.拆卸线开启的工位理论上最少为,最多为n个,即每个拆卸任务刚好单独分配给一个工位,从而确定工位的上下界限,见式(9).同时保证开启的工位内分配有拆卸作业,并且开启的工位编号尽量靠前,见式(10).

(9)
(10)

7) 任务分配约束.所有的拆卸任务必须分配且只能分配给一个工位,每个开启的工位必须有任务分配:

(11)
1.5 目标函数的模糊化

对于多目标的DLBP问题,可以建立目标函数的隶属度函数来进行模糊化处理.期望在满足所有约束条件下,选择合适的隶属度函数,寻找一个折中解,尽可能减少拆卸能耗、拆卸成本和均衡指数.针对求最小化问题,本文选择降半直线表示各目标的隶属函数,如图 2所示.

图 2 降半直线隶属函数 Figure 2 Descending half line membership function

三者目标值越小,与之对应的隶属度越大,决策者的满意度就越高[26-27]. 3个目标的隶属函数的形式见式(12)~式(14).式中,X为拆卸序列向量,c1c2c3为最小拆卸能耗、最小均衡指数、最小拆卸成本单目标的最优值,δ1δ2δ3为3个相应目标的伸缩值.

(12)
(13)
(14)
1.6 多目标模糊优化的DLBP模型

λ为所有目标函数中隶属度的最小值,用来表示决策者的满意程度,λ值越大则满意度越高,表示优化结果越好.因此用λ表示目标优化的满意度指标,表示为

(15)

通过模糊数学理论中的极小极大原则,将所有多目标转化为满足所有条件求λ值最大的问题[27],即数学描述为

(16)
2 模糊多目标果蝇求解方法

本文针对DLBP问题的特性,基于模糊理论中最大满意度的思想,提出一种多目标离散果蝇优化算法.求解DLBP的IFOA主要思想为:

1) 采用实数编码,每个个体为一个可行拆卸序列;

2) 依据启发式规则先产生满足优先关系的种群,并对种群进行相斥相容约束、固定工位约束判断,产生可行初始化种群;

3) 用变异操作产生扰动,把满足约束的序列作为邻域解来执行嗅觉搜索;

4) 依据目标函数的隶属度,用最大满意度来评价邻域解的优劣,来执行视觉操作,更新自身位置;

5) 为了避免陷入局部最优,采用Metropolis接受准则,并嵌入全局协作机制,提高全局搜索能力.

围绕DLBP离散问题解集空间广、约束多等特征,设计基于FOA的改进FOA算法,针对多目标进行模糊综合优化求解,图 3为IFOA的流程图,其中,λc为当代中的最大满意度;X(λc)为表示每迭代一次,当代中的最优解,即最优拆卸序列.

图 3 算法流程图 Figure 3 Flow chart of the algorithm
2.1 生成可行解

采用节拍约束下的启发式规则进行工序实数编码,通过优先关系矩阵产生满足符合优先约束的拆卸序列,然后对序列进行固定工位约束、相斥约束、相容约束判断:若满足,则得到可行拆卸序列;否则,循环直至满足约束.其步骤为:

Step 1   输入优先关系矩阵P=[ali]n×n、节拍时间CT、任务数n、工位分配时间T=CT.

Step 2   搜索无紧前任务的可选任务集合,从Y中随机挑选作业时间满足tjT的任务l,令T=T-tl.若无法得到任务l,则开启新的工位,令T=CT;否则,转至Step 3.

Step 3  松弛与任务l有关的优先约束关系,令ali=0且ail=0.

Step 4  循环Step 2、Step 3直到产生一个任务数为n的拆卸序列X1.

Step 5  判断序列X1是否满足固定工位约束.若是,则转至Step 6;否则转至Step 1.

Step 6  判断序列X1是否满足相斥约束.若是,则转至Step 7;否则转至Step 1.

Step 7  判断序列X1是否满足相容约束.若是,则输出满足要求的可行解X1;否则转至Step 1.

2.2 适应度函数

果蝇味道浓度函数可以评价解的质量好坏,作为适应度函数.对于解Xi,其适应度函数可以表示为λi=min{μ(f1(Xi)),μ(f2(Xi)),μ(f3(Xi))},对于所有个体Xi,其适应度值是λi,其值越大,表明解的质量越好.保存每一代中适应度值最大的解和相应的满意度,随着迭代次数增加,不断更新较优解Xbestfly和最大满意度λ0.

2.3 嗅觉和视觉搜索

基于DLBP工序实数编码,设计了一种变异操作执行嗅觉搜索,利用随机数产生随机变异点,在满足优先关系的条件下,通过嗅觉操作产生S个邻域解,最后再进行约束判断.从邻域解中筛选最优解更新自身的位置来执行视觉搜索,具体步骤为:

Step 1  产生随机整数k,得到在拆卸序列X中位置k对应的任务q且邻域解计数I=0.

Step 2  利用优先关系矩阵得到q的紧前任务m和紧后任务n,保持m之前和n之后的序列不变.

Step 3  mn之间的序列为可插入位置,在可插入位置将任务q随机插入.

Step 4  判断是否同时满足固定工位约束、相斥约束、相容约束.若是,则产生一个邻域解且I=I+1;否则,转至Step 1.

Step 5   判断I=S是否成立.若成立,转至Step 6执行视觉搜索;否则,循环Step 1~Step 4.

Step 6   计算λ值,利用最大满意度筛选最优的邻域解替换当前解.

2.4 全局协作机制

果蝇种群在觅食过程中,每个果蝇个体会通过种群之间的交互和协作学习,并不断调整自身的位置逐渐逼近食物源.因此,为了提高算法的全局搜索能力,本文模拟果蝇种群之间的协作学习行为,并针对DLBP问题设计了一种特殊的两点交叉操作,实现果蝇种群内个体间的协作机制.交叉操作情况为:将视觉搜索产生的解作为父代Xfather,从种群中随机挑选一个解作为参考解Xreference,然后在Xfather上随机挑选两个交叉点ab(a < b),保持相对位置在a之前和b之后的序列不变,并在Xreference上搜索Xfather父代中介于[ab]之间的相同任务,按照相对位置由小到大排序,可保证优先关系约束,最后映射到Xfather,即生成子代Xoffspring,完成交叉操作,具体协作机制见图 4.

图 4 协作机制 Figure 4 Collaborative mechanisms
2.5 模拟退火机制

针对DLBP多目标多约束问题的复杂性,求解过程中易陷入局部最优,因此对执行完协作机制后的个体进行模拟退火操作.传统的单目标优化问题中,对可行解S0扰动产生一个新解S1,分别计算f(S0)、f(S1),并计算目标差Δf,按照Metropolis准则,即min(1,exp(-Δf/T))>rand(0,1)接受新解[21].但本文针对多目标问题需要将Metropolis准则进行改进,接受新解的概率为

(17)

式中,i∈{1,2,3};finew为新解Xnew的第i个目标值,ficurrent为新解Xcurrent的第i个目标值,T为每次更新的温度.退火机制设置为:设置初温为T0,确定迭代次数k,按照指数降温策略Tk=a×Tk-1,确定终止温度Tend=ak×T0.若Xnew严格优于Xcurrent,则用新解替换掉当前解;若Xcurrent严格优于Xnew,则判断接受概率是否成立:若是,则替换当前解,否则不变;若XcurrentXnew互不占优,则解保持不变.

2.6 问题求解步骤

1) 输入原始数据相关信息矩阵K、优先关系矩阵P、节拍CT、任务数目n等.

2) 以拆卸能耗最小进行单目标优化,运用FOA优化求解得到c1,并得到相应均衡指数f2和拆卸成本f3.

3) 以均衡指数最小进行单目标优化,运用FOA优化求解得到c2,并得到相应拆卸能耗f1和拆卸成本f3.

4) 以拆卸成本最小进行单目标优化,运用FOA优化求解得到c3,并得到相应拆卸能耗f1和均衡指数f2.

5) 在步骤(2)~步骤(4)求解基础上,将各单目标值进行一定的伸缩,即确定δ1δ2δ3的值,其取值范围为:0≤δ1≤max(f1-c1f1-c1),0≤δ2≤max(f2-c2f2-c2),0≤δ3≤max(f3-c3f3-c3).决策者可以根据意愿和偏好,进行不同程度的伸缩.

6) 将确定的δ1δ2δ3c1c2c3代入式(12)~式(14),得到各目标隶属度函数表达式.

7) 采用最大满意度的方法将多目标转化为式(16)单目标模型,以最大满意度为适应度函数,运用FOA进行模糊综合优化.

3 算例验证和应用

程序运行环境为Intel® Corel i7-6700 CPU@3.40 GHZ,RAM 8.00 G内存,在Win10系统下使用MATLAB R2010b开发IFOA和基本FOA分别求解单目标、模糊多目标的算法优化程序.

3.1 算例验证

鉴于本文模型是新建立的,为了验证所提算法的有效性,以文[28]中25个拆卸任务的手机作为测试算例(简称P25),并引入文[28]中目标函数:最小工位数(F1)、最小空闲时间(F2)、最小危害指数(F3)、最小需求指数(F4).具体函数表达式和相关拆卸信息,详见文[28],考虑篇幅关系,在此不给出.通过将多目标转化为单目标求解该问题的现有方法有:遗传算法(genetic algorithm,GA)[28]、强化学习算法(reinforcement learning,RL)[29].

经过多次测试,综合求解P25的性能和求解时间,IFOA的参数均设置为:N=100,T0=200,S=5,Tend=0.36,a=0.9.基本的FOA参数设置为:N=100,M=60,S=5.分别运行10次,得到单目标优化结果. 4个目标隶属度函数均采用降半直线,然后依据单目标优化结果确立隶属函数参数:δ1=2,c1=9;δ2=150,c2=9;δ3=15,c3=73;δ4=50,c4=850.最后将FOA和IFOA综合优化所求结果与上述2种算法求解结果对比,见表 1.

表 1 4种算法对P25求解结果对比 Table 1 Comparison among the four algorithms for P25 results
算法 F1 F2 F3 F4
GA 9 9 82 868
RL 9 9 97 862
FOA 10 99 85 876
IFOA 9 13 83 857

分析表 1可知,基本FOA所求结果劣于IFOA和GA所求结果,与RL相比,在F3目标上优于RL,其它3个目标均比RL所求结果差. IFOA所求结果与GA所求结果相比,在F2F3目标上,比GA差,但在F4目标上优于GA;IFOA所求结果与RL所求结果相比,在F2目标上比RL差,但在F3F4目标上优于RL;三者在F1目标上均相同,所以三者互不占优.这表明IFOA可以求得较优解,有效克服了FOA易早熟的缺点.

3.2 算例应用

本文结合废旧电视机的实际拆卸过程,运用所提出的IFOA对该拆卸实例进行优化求解.调查已知该拆卸线实际生产节拍为CT=60 s.企业希望在满足多个约束条件下,寻找合理的拆卸作业分配方案,使得拆卸能耗最少,企业拆卸成本尽可能低,均衡各工位的空余时间.表 2给出了各项拆卸作业的相关信息,如拆卸时间t(s)、拆卸方向r、单位时间拆卸成本u(元/秒)等.图 5给出了拆卸作业优先关系图,其中拆卸作业15为特殊作业任务,只能在特定工位2完成,要满足固定工位约束,否则造成环境污染;拆卸作业22和23必须满足相容约束,共用同一设备,否则会增加额外准备时间;拆卸作业23和6由于拆卸特殊,必须满足相斥约束.

表 2 电视机拆卸任务相关信息 Table 2 TV disassembly tasks related information
序号 零件 t r u
1 12个螺钉 50 1 0.012 3
2 后盖 9 -1 0.004 2
3 天线 3 -1 0.002 8
4 喇叭 7 3 0.003 6
5 电线 24 3 0.007 1
6 主电路板 2 -1 0.002 7
7 电源线 10 -1 0.004 2
8 偏转线圈 18 3 0.005 8
9 偏光调节圈 4 3 0.003 1
10 高压帽 4 3 0.003 1
11 消磁线圈 4 3 0.003 1
12 接地线 4 3 0.003 1
13 变压器 4 3 0.003 1
14 高频头 4 3 0.003 1
15 电子枪端电路板 4 3 0.003 1
16 玻璃管 4 3 0.003 1
17 电子枪 4 3 0.003 1
18 防爆带 4 3 0.003 1
19 4个螺钉 17 3 0.005 7
20 前壳 16 1 0.005 6
21 CRT 7 1 0.003 8
22 锥玻璃 3 -1 0.002 9
23 荧光粉 3 3 0.002 9
24 销钉 4 2 0.003 1
25 阳极帽 2 2 0.002 7
26 阴极罩 2 2 0.002 7
27 屏玻璃 2 1 0.002 7
图 5 任务优先关系图 Figure 5 Precedence relations diagram of the tasks
3.3 算例结果分析

综合考虑算法求解性能与时间,IFOA的参数均设置为:N=50,T0=200,S=5,Tend=0.36,a=0.9.基本的FOA参数设置为:N=50,M=60,S=5.依据该企业能耗统计数据的均值,则ER=200,E1=E2=100.首先,IFOA和基本FOA分别进行拆卸能耗、拆卸成本、均衡指数单目标优化,然后确定隶属度参数,比较IFOA和基本FOA求解多约束DLBP的性能,最后,求解出考虑能耗的电视机最优的拆卸方案.

各单目标优化均运行10次,保存运行结果和平均运行时间,二者均可得到表 3相同的单目标优化结果. FOA和改进的FOA单目标平均运行时间分别为0.37 s、0.44 s,改进FOA时间略长于基本FOA,但是改进FOA求得单目标较优解的次数大于FOA.按照表 3所求单目标优化结果,然后确定各目标隶属度函数参数见表 4,进而确定各目标隶属函数及算法适应度函数.

表 3 单目标优化结果 Table 3 Optimization results of the single target
序号 任务分配方案 f1 f2 f3
拆卸能耗单目标最优 [1-2]-[7-5-4-15-3-6-10-13]-[9-8-14-17-18-12-11-16]-[19-21-20-22-25-24-26-23-27] 49 800 217 1.854
拆卸成本单目标最优 [1-2]-[5-15-8-9-4]-[16-19-20-7-10-6-21]-[18-22-26-25-14-13-12-11-17-24-3-23-27] 51 000 299 1.692
均衡指数单目标最优 [1-2]-[7-5-4-15-9-10]-[8-12-16-13-19-6-18]-[20-14-21-17-11-22-23-26-27-25-3-24] 51 000 135 1.848
表 4 隶属函数参数确定 Table 4 Determination of the membership function parameters
目标 各自伸缩值范围 确定伸缩值 单目标优化值
f1 0≤δ1≤1 800 δ1=1 200 c1=49 800
f2 0≤δ2≤164 δ2=100 c2=135
f3 0≤δ3≤0.162 δ3=0.1 c3=1.692

为比较IFOA和基本FOA求解模糊多目标综合优化的性能,程序运行10次,保存运行结果和运行时间.具体结果如表 5,黑体表示的为优化的最好结果.分析表 5可知IFOA优化的最大满意度最好结果为0.58,而FOA最好结果为0.52,且前者最大满意度的均值为0.532,后者最大满意度均值为0.42,均证明IFOA所求解的质量优于FOA;IFOA平均运行时间为2.51 s,略大于FOA平均运行时间2.10 s,但求解质量明显得到提高,所以针对本问题增加少量求解时间,探索更好的优化结果是值得的.

表 5 IFOA和FOA的性能对比分析 Table 5 Performance comparison and analysis of IFOA and FOA
序号 IFOA FOA
f1 f2 f3 最大满意度 f1 f2 f3 最大满意度
1 50 400 143 1.740 0.52 50 200 155 1.74 0.52
2 50 400 159 1.734 0.58 50 600 179 1.74 0.40
3 50 400 177 1.722 0.58 50 400 183 1.74 0.52
4 50 400 183 1.740 0.52 50 800 195 1.74 0.20
5 50 200 183 1.740 0.52 50 400 207 1.74 0.28
6 50 200 183 1.740 0.52 50 400 155 1.74 0.52
7 50 200 153 1.734 0.58 50 200 195 1.74 0.40
8 50 400 177 1.722 0.58 50 400 183 1.74 0.52
9 50 600 179 1.740 0.40 50 200 183 1.74 0.52
10 50 400 167 1.740 0.52 50 600 183 1.74 0.40

IFOA有4次优化结果最大满意度为0.58,分析可知编号3和编号8的方案相同,编号7的方案优于编号2的方案.因此,实际上得到2个较优的拆卸方案见表 6.为了直观对比,将单目标优化的3个方案和模糊综合优化的2个方案在图 6中展示.图 7为5个优化方案的空间分布,图 8为模糊综合优化所得方案的具体拆卸方案.

表 6 IFOA模糊综合优化最好结果 Table 6 Best results of IFOA fuzzy synthesis optimization
序号 任务分配方案 μ(f1) μ(f2) μ(f3) λ
1 [1-2]-[7-5-15-8]-[19-10-11-6-3-20-12-14]-[4-13-9-17-16-18-21-22-25-23-27-24-26] 0.8 0.82 0.58 0.58
2 [1-2]-[5-7-15-8]-[4-6-3-10-14-9-16-18-13-11-12-17]-[19-21-22-24-25-23-20-27-26] 0.58 0.6 0.7 0.58
图 6 单目标f1f2f3优化结果 Figure 6 Optimization results of the single target f1f2f3
图 7 优化方案空间分布 Figure 7 Spatial distribution of the optimization scheme
图 8 模糊综合优化的拆卸方案 Figure 8 Fuzzy integrated optimization of the disassembly program

图 6图 7可以看出,各个目标之间是矛盾的,一个目标变好会导致其它目标变差,但是模糊综合优化可以同时协同优化多个目标,找到一个令人满意的折中解.图 6(a)表示只考虑拆卸能耗(f1)时,以拆卸能耗为单目标优化方法得到的拆卸能耗最小,其次是模糊综合优化方法得到的两个方案,最差是均衡指数(f2)单目标优化和拆卸成本(f3)单目标优化方法,同理,可分析图 6(b)图 6(c).模糊综合优化得到两个拆卸方案,在图中用正方形表示,其中不带圈的正方形为方案1和带圈正方形为方案2.方案1和方案2与拆卸能耗单目标优化结果相比,拆卸能耗分别提高了0.8%和1.2%,但是拆卸成本分别降低了29.5%和18.4%,均衡指数分别降低了6.5%和7.1%.方案1和方案2与均衡指数单目标优化结果相比,均衡指数分别提高了1.3%和3.1%,但是拆卸成本分别降低了6.2%和6.8%,拆卸能耗分别降低了1.2%和1.6%.方案1和方案2与拆卸成本单目标优化结果相比,拆卸成本分别提高了2.5%和1.8%,但是均衡指数分别降低了48.8%和40.8%,拆卸能耗分别降低了1.2%和1.6%.因此,综合模糊优化得到的2个折中解:第1个方案,拆卸能耗为50 200 J,均衡指数为153,拆卸成本为1.734元;第2个方案,拆卸能耗为50 400 J,均衡指数为177,拆卸成本为1.722元.二者都比单目标优化结果好,在一定程度上,是可以接受的.

5 结论

针对DLBP实际拆卸特点,首次在拆卸线过程中考虑拆卸能耗问题,以最小化拆卸能耗、拆卸成本和均衡指数为优化目标,并提出固定工位约束、相斥约束和相容约束,与已有优先关系约束、节拍约束等构成多约束条件,从而建立了多目标多约束DLBP数学模型.本文采用模糊规划和最大化满意度方法,建立各目标隶属度函数,将多目标优化转化为模糊综合优化.设计一种离散果蝇优化算法,将最大化满意度作为适应度函数,为了提高全局搜索能力,加入模拟退火机制和全局协作机制.通过求解P25问题,将IFOA和基本FOA与已有算法对比,结果表明IFOA在求解DLBP多目标中具有良好求解性能.最后将其运用到具有27个拆卸任务的电视机拆卸实例,求解得到2个较好的拆卸方案,验证了模型和算法的实用性.拆卸过程中还存在资源约束、作业时间不确定、不同布局形式等问题,这值得后续进一步研究.

参考文献
[1] 周杰, 陶晓芳. 生产者责任延伸制下销售-回收型闭环供应链收益共享契约研究[J]. 科学决策, 2016(2): 39–57.
Zhou J, Tao X F. Research on revenue-sharing contract of sales-recycling closed-loop supply chain with EPR[J]. Scientific Decision-Making, 2016(2): 39–57.
[2] 科技部.绿色制造科技发展"十二五"专项规划(2015-2020)[EB/OL]. (2013-09-27)[2017-07-21]. http://ezone.mofcom.gov.cn/article/ad/201309/20130900327233.shtml.
Ministry of Science and Technology. Green manufacturing technology development "second five" special planning (2015-2020)[EB/OL]. (2013-09-27)[2017-07-21]. http://ezone.mofcom.gov.cn/article/ad/201309/20130900327233.shtml.
[3] Gungor A, Gupta S M. A solution approach to the disassembly line balancing problem in the presence of task failures[J]. International Journal of Production Research, 2001, 39(7): 1427–1467. DOI:10.1080/00207540110052157
[4] Altekin F T, Kandiller L, Ozdemirel N E. Profit-oriented disassembly-line balancing[J]. International Journal of Production Research, 2008, 46(10): 2675–2693. DOI:10.1080/00207540601137207
[5] Mcgovern S M, Gupta S M. A balancing method and genetic algorithm for disassembly line balancing[J]. European Journal of Operational Research, 2007, 179(3): 692–708. DOI:10.1016/j.ejor.2005.03.055
[6] Kara Y. A network-based shortest route model for parallel disassembly line balancing problem[J]. International Journal of Production Research, 2015, 53(6): 1849–1865. DOI:10.1080/00207543.2014.965348
[7] Altekin F T. A piecewise linear model for stochastic disassembly line balancing[J]. IFAC PapersOnline, 2016, 49(12): 932–937. DOI:10.1016/j.ifacol.2016.07.895
[8] Avikal S, Mishra P K, Jain R. A fuzzy AHP and PROMETHEE method-based heuristic for disassembly line balancing problems[J]. International Journal of Production Research, 2014, 52(5): 1306–1317. DOI:10.1080/00207543.2013.831999
[9] Mcgovern S M, Gupta S M. Combinatorial optimization analysis of the unary NP-complete disassembly line balancing problem[J]. International Journal of Production Research, 2007, 45(18/19): 4485–4511.
[10] Kalayci C B, Polat O, Gupta S M. A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem[J]. Annals of Operations Research, 2016, 242(2): 321–354. DOI:10.1007/s10479-014-1641-3
[11] Kalayci C B, Gupta S M. A particle swarm optimization algorithm for solving disassembly line balancing problem[C]//Proceedings for the Northeast Region Decision Sciences Institute, 2012: 347-357.
[12] Kalayci C B, Gupta S M. Simulated annealing algorithm for solving sequence-dependent disassembly line balancing problem[J]. IFAC Proceedings, 2013, 46(9): 93–98. DOI:10.3182/20130619-3-RU-3018.00064
[13] Liu J, Wang S. Balancing disassembly line in product recovery to promote the coordinated development of economy and environment[J]. Sustainability, 2017, 9(3): 2–15.
[14] Zhang Z Q, Wang K P, Zhu L X, et al. A pareto improved artificial fish swarm algorithm for solving a multi-objective fuzzy disassembly line balancing problem[J]. Expert Systems with Applications, 2017, 86: 165–176. DOI:10.1016/j.eswa.2017.05.053
[15] 丁力平, 谭建荣, 冯毅雄, 等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15(7): 1406–1413.
Ding L P, Tan J R, Feng Y X, et al. Multi-objective optimization for disassembly line balancing based on Pareto ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15(7): 1406–1413.
[16] 王林, 吕盛祥, 曾宇容. 果蝇优化算法研究综述[J]. 控制与决策, 2017, 32(7): 1153–1162.
Wang L, Lü S X, Zeng Y R. Literature survey of fruit fly optimization algorithm[J]. Control and Decision, 2017, 32(7): 1153–1162.
[17] 张晓茹, 张著洪. 求解多模态函数优化的微果蝇优化算法[J]. 信息与控制, 2016, 45(3): 361–370.
Zhang X R, Zhang Z H. Micro fly optimization algorithm solving multi-modal function optimization[J]. Information and Control, 2016, 45(3): 361–370.
[18] 刘琼, 赵海飞. 基于多目标果蝇算法面向低碳的车间布局与调度集成优化[J]. 机械工程学报, 2017, 53(11): 122–133.
Liu Q, Zhao H F. Integrated optimization of workshop layout and scheduling to reduce carbon emissions based on a multi-objective fruit fly optimization algorithm[J]. Journal of Mechanical Engineering, 2017, 53(11): 122–133.
[19] 袁文兵, 常亮, 徐周波, 等. 基于果蝇优化算法的多工位装配序列规划[J]. 计算机科学, 2017, 44(4): 246–251.
Yuan W B, Chang L, Xu Z B, et al. Multi-plant assembly sequence planning based on fruit fly optimization algorithm[J]. Computer Science, 2017, 44(4): 246–251.
[20] 郑晓龙, 王凌. 随机资源约束项目调度问题基于序的果蝇算法[J]. 控制理论与应用, 2015, 32(4): 540–545.
Zheng X L, Wang L. An order-based fruit fly optimization algorithm for stochastic resource-constrained project scheduling[J]. Control Theory & Applications, 2015, 32(4): 540–545.
[21] 汪开普, 张则强, 朱立夏, 等. 多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J]. 计算机集成制造系统, 2017, 23(6): 1277–1285.
Wang K P, Zhang Z Q, Zhu L X. Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J]. Computer Integrated Manufacturing Systems, 2017, 23(6): 1277–1285.
[22] 郭秀萍, 杨根科, 吴智铭. 一种基于模拟退火的多目标Memetic算法[J]. 信息与控制, 2007, 36(1): 29–33.
Guo X P, Yang G K, Wu Z M. A simulated-annealing-based multi-objective memetic algorithm[J]. Information and Control, 2007, 36(1): 29–33. DOI:10.3969/j.issn.1002-0411.2007.01.006
[23] 汪开普, 张则强, 毛丽丽, 等. 多目标拆卸线平衡问题的Pareto人工鱼群算法[J]. 中国机械工程, 2017, 28(2): 183–190.
Wang K P, Zhang Z Q, Mao L L, et al. Pareto artificial fish swarm algorithm for multi-objective disassembly line balance problems[J]. China Mechanical Engineering, 2017, 28(2): 183–190. DOI:10.3969/j.issn.1004-132X.2017.02.010
[24] 查靓, 徐学军, 余建军, 等. 多类约束下U型装配线平衡建模研究[J]. 工业工程与管理, 2011, 16(1): 59–63.
Zha J, Xu X J, Yu J J, et al. Balancing U-shaped assembly line with multiple constraints[J]. Industrial Engineering and Management, 2011, 16(1): 59–63. DOI:10.3969/j.issn.1007-5429.2011.01.012
[25] 李大双, 张超勇, 邵新宇, 等. 基于殖民竞争算法的多约束双边装配线平衡[J]. 机械工程学报, 2015, 51(2): 183–189.
Li D S, Zhang C Y, Shao X Y, et al. Hybrid colonial competitive algorithm for the two-sided assembly line balancing problem with multiple constraints[J]. Journal of Mechanical Engineering, 2015, 51(2): 183–189.
[26] 张晓花, 赵晋泉, 陈星莺. 节能减排多目标机组组合问题的模糊建模及优化[J]. 中国电机工程学报, 2010, 30(22): 71–76.
Zhang X H, Zhao J Q, Chen X Y. Multi-objective unit commitment fuzzy modeling and optimization for energy-saving and emission reduction[J]. Proceedings of the CSEE, 2010, 30(22): 71–76.
[27] 李修琳, 傅培华, 鲁建厦, 等. 基于人工蜂群优化的串并行混装线关联排序问题[J]. 计算机集成制造系统, 2017, 23(3): 567–574.
Li X L, Fu P H, Lu J S, et al. Integrated sequencing of serial parallel mixed assembly line based artificial bee colony[J]. Computer Integrated Manufacturing Systems, 2017, 23(3): 567–574.
[28] Kalayci C B, Gupta S M. A hybrid genetic algorithm approach for disassembly line balancing[C]//Proceedings of the 42nd Annual Meeting of Decision Science Institute. Boston, MA, USA: DSI, 2011, 1: 2142-2148.
[29] Tuncel E, Zeid A, Kamarthi S. Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25(4): 647–659. DOI:10.1007/s10845-012-0711-0
http://dx.doi.org/10.13976/j.cnki.xk.2018.7390
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

蔡宁, 张则强, 朱立夏, 贾林
CAI Ning, ZHANG Zeqiang, ZHU Lixia, JIA Lin
多约束能耗拆卸线平衡问题的改进果蝇模糊优化
Improved Fruit-fly Fuzzy Optimization Algorithm for Multi-constrained Disassembly-line Balancing Problem Considering Energy Consumption
信息与控制, 2018, 47(6): 702-712.
Information and Control, 2018, 47(6): 702-712.
http://dx.doi.org/10.13976/j.cnki.xk.2018.7390

文章历史

收稿/录用/修回: 2017-07-24/2017-09-26/2017-10-17

工作空间