不确定环境下再制造加工车间多目标调度优化方法

张铭鑫,张　玺,彭建刚,陈鸿海

(合肥工业大学 机械与汽车工程学院 安徽 合肥　230009)



不确定环境下再制造加工车间多目标调度优化方法

张铭鑫,张玺,彭建刚,陈鸿海

(合肥工业大学 机械与汽车工程学院 安徽 合肥230009)

摘要:针对再制造生产过程中工件的加工时间和成本不确定性调度问题,文章提出了一种不确定环境下再制造加工车间多目标调度优化方法。该方法采用模糊变量表示其不确定性参数,以最小化加工时间和成本为目标,在满足模糊交货期等约束条件下,构建了不确定环境下多目标决策的模糊机会约束规划模型,并提出了求解该模型的混合智能算法;应用模糊模拟技术产生样本数据,用于训练神经网络以逼近不确定函数;针对神经网络中存在收敛速度慢、容易陷入局部最优的缺点,应用改进的粒子群算法优化神经网路,将训练好的神经网路嵌入改进的遗传算法中求解调度模型。最后,通过仿真实例,验证该模型和算法的可行性。

关键词:再制造;加工车间调度;模糊机会约束规划;混合智能算法

0引言

再制造是将可利用废旧品经过分类拆解、清洗检查、修复加工、重新装配和调整检测等工序恢复到“新品”状态的过程[1-2]。与传统制造的过程相比,再制造过程存在着大量的不确定性因素[3],其中对再制造调度优化的影响主要表现为再制造时间、成本和工艺路线的不确定。现有研究已证实,这些不确定因素使得传统计划和调度方法难以直接应用[4]。因此,如何在不确定环境下对再制造生产调度进行优化排产,以减少产品生产成本、提高客户满意度,已成为再制造企业提高生产管理水平关键环节之一。

目前,有关再制造生产调度优化研究已有了一些成果。文献[5]研究了基于基本周期政策的制造和再制造多产品经济批量调度问题,提出了一个简单且易于实现的算法,并使用基本周期政策求解该模型,放宽了每个项目在每个周期的通用周期时间和单一的再生产批号的约束;文献[6]提出了一个寻找最优通用时间周期的精确算法,结合混合整数规划方法搜索最佳周期,研究了制造和再制造独立生产线的多产品经济批量调度问题;文献[7]以单计划周期内总生产成本最小为目标,考虑回收件质量差异对生产成本的影响,建立了面向再制造生产计划的非线性整数规划模型,采用3种不同的再制造和废弃策略,比较总生产成本的变化规律。

总体来说,目前再制造生产调度的关注点在于生产计划的优化,而有关再制造车间调度的研究不多。

文献[8]分析了再制造车间的拆卸和重新组装设施共享静态优先级规则的性能;文献[9]研究了预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题,以最小化完工时间为目标,提出了LPT-LSU算法;文献[10]提出了一种基于关键链的再制造系统不确定性生产调度方法,将生产调度问题视作不确定性的资源受限项目调度问题;文献[11]针对再制造加工车间加工时间的不确定性,建立了再制造加工车间的模糊随机调度模型,并提出了求解该模型的一种混合智能算法。

纵观这些研究发现,上述成果主要用于求解单目标再制造车间调度问题,都未考虑在多重不确定性环境下,时间和成本对再制造生产调度的影响。

因此,本文在借鉴现有研究成果的基础上,采用模糊变量来描述再制造加工车间的加工时间、成本和交货期,在满足一定交货期满意度的约束下,以最小化加工时间和成本为目标,构建了基于一定置信水平下模糊机会约束规划的再制造车间多目标决策的不确定性模型;提出了一种求解该模型的混合智能算法,并给出了求解方法及相应流程;最后,通过仿真实例验证该混合智能算法对于解决再制造加工车间调度问题的可行性。

1再制造加工车间调度问题模型

1.1模糊变量及其数学描述

对于再制造车间而言,加工零部件所需类型因受再制造系统中废旧件回收数量、拆卸数量和库存数量等因素的影响,加工过程的零部件不仅包含新品零部件,还有再修复件和再利用件,其质量不确定性导致工位加工时间、加工成本和交货期范围波动很大。例如在特定的加工工序中,新品件只需通过设定机器设备参数(例如扭矩、压力等)来完成操作,再修复件或再利用件还需进行附加的工艺调整(例如增加调整垫片达到所需公差配合)。因此本文采用基于可信性测度的模糊变量来描述再制造加工车间的加工时间、成本和交货期。

定义1设θ是非空集合,P(θ)是θ的幂集。如果Pos是可能性测度,则三元组(θ,P(θ),Pos)称为可能性空间[12]。

定义2设ξ为从可能性空间(θ,P(θ),Pos)到实直线R上的函数,则称ξ是一个模糊变量[12]。

在模糊理论中,文献[13]定义了必要性测度Nec{},文献[14]定义了可能性测度Pos{}。

定义3假设(θ,P(θ),Pos)是可能性空间,A是幂集P(θ)中的一个元素,则称Cr{A}=(Pos{A}+Nec{A})/2为事件A的可信性测度[13]。

定义4设ξ为模糊变量,且α∈(0,1],则称ξinf(α)=inf{r|Cr{ξ≤r}≥α}为模糊变量ξ的α悲观值,本文采用悲观值来度量模糊变量ξ[15]。

1.2问题描述

衡量生产调度优化效果最常用的2个指标是成本和时间。

同时考虑成本和时间因素的再制造加工车间调度问题可描述为:有n个再制造件需要经过k道工序在m台机器上完成加工。每个再制造件由于失效程度的不同,导致在相同的工序中工件所需的设备也不相同,再制造件的加工时间和成本是由机器性能决定。在满足工序顺序约束、机器约束和交货期约束等前提下以预定置信水平下最小化加工时间和成本为调度目标。

该模型满足如下假设:① 每个再制造件在某一时刻只能在一台机器上加工,工序开始后不能中途中断;② 不同再制造件之间具有相同的优先级;③ 所有再制造件在零时刻均可以被加工;④ 再制造件在机器之间的转运时间忽略不计,且生产准备时间包含在加工时间之内。

1.3调度建模

与传统制造不同,受废旧件回收质量状况的影响,再制造生产系统中不仅包含传统的机械加工操作,还包含针对废旧件不同质量状况的特种修复技术,这造成了再制造系统中加工时间、成本和交货期的不确定性，使企业决策者经常面临时间指标和成本指标的目标冲突,因此希望寻求在一定可能性下使各个决策目标相对达到最优。

模糊机会约束规划是文献[16]提出的一类模糊规划,其显著特点是模糊约束条件至少以一定的置信水平成立,允许所做决策在一定程度上不满足约束条件,只要求该决策使约束条件成立的可信性不小于决策者预先给定的置信水平,它为不确定性决策问题提供了解决思路。

如果决策者同时面临多个决策目标时,模糊机会约束目标规划模型通常表示为:

其中,x为决策向量;ξ为模糊向量;fi(x,ξ)为目标函数;gj(x,ξ)为约束函数;Cr{}为事件的可信性测度;αj和βi为决策者预先给定的置信水平。

成本是衡量生产调度的一个重要指标。取一定置信概率β1下加工再制造件总成本之和最小为成本目标，用模糊机会约束描述为:

时间是衡量生产调度的另一个重要指标。取一定置信概率β2下加工再制造件最大完工周期的最小值为时间目标，用模糊机会约束描述为:

在加工时间和交货期均为模糊变量的再制造车间中,交货期满意度约束可以描述为在一定置信水平α下各工件的平均满意度大于车间定义的阀值。用模糊机会约束描述为:

综上所述,考虑时间和成本为模糊变量的模糊机会约束规划模型可表示为:

(1)

(2)

(3)

2模型求解

2.1混合算法介绍

求解模糊机会约束规划主要有2种方法:① 转化为确定性的等价规划,这种方法要求目标函数和约束条件的参数符合某种特征分布;由于再制造车间的不确定性,导致相关参数呈现模糊性特性,无法转化为清晰等价形式;② 逼近法,通过模拟仿真生成大量样本数据集来逼近机会约束函数,结合智能算法来优化求解模型。第2种方法更符合再制造生产实际。

本文在参考文献[12,17]的基础上设计了一种将模糊模拟技术、神经元网络和遗传算法相结合的混合智能算法,用来对模糊机会约束规划进行求解。在仿真平台上,运用模糊模拟技术产生大量的输入输出样本数据;利用样本数据和改进的粒子群算法训练多层前向神经网络以逼近不确定函数;将不确定函数嵌入遗传算法中,检验染色体的可行性和计算染色体的目标值,优化再制造加工车间调度问题。

结合模糊模拟技术、神经元网络和遗传算法的混合智能算法的主要步骤如图1所示。

图1　混合智能算法主要步骤

2.2模糊模拟

模糊模拟是对模糊系统进行抽样试验的一项技术,当模拟次数达到一定程度时,模拟值就可以无限接近精确值。下面给出本文需要的模糊模拟计算方法。

检验模糊模型的交货期约束条件L=Cr{g(x,ξ)≤0}≥α。算法步骤[18]如下:

(1)设L=Cr{g(x,ξ)≤0}。

(2)分别从θ中均匀产生θk,使得Pos{g(x,ξ(θk))}≥ε,并定义vk=Pos{g(x,ξ(θk))}(k=1,2,…,N),其中ε是个充分小的数。

(3)计算L,即

返回L。

(4)若L≥α则作为样本数据。

(2)分别从θ中均匀产生θk,使得Pos{f(x,ξ(θk))}≥ε,并定义vk=Pos{f(x,ξ(θk))}(k=1,2,…,N),其中ε是个充分小的数。

(3)计算L(r),即

找到满足L(r)≥β的最小值r。

2.3模糊函数的神经网络逼近

人工神经网络是由许多神经元连接而成，用来抽象简化和模拟人脑行为的一类适应系统。多层前向神经元网络是目前使用较多的网络结构,已被广泛应用于函数逼近、模式识别和网络优化等领域。目前已证明对于任何在闭区间的一个连续函数都可用一个3层前向神经元网络来逼近。

设调度序列为矢量X,模型中的机会约束可用X的模糊函数来描述,定义p+2个不确定函数如下：

用模糊模拟产生的大量样本数据训练一个3层前向神经网络来逼近此式中的不确定函数。该神经网络中取调度序列X作为输入神经元,输出层为p+2神经元。

然而,神经网络存在收敛速度慢、容易陷入局部最优的局限性,针对这些缺点,很多研究者通过算法训练来优化神经网络。

文献[19]通过比较遗传算法、普通粒子群算法和改进粒子群算法对神经网络的优化得出,改进粒子群算法明显优于其他算法,训练的收敛速度大大提高且神经网络的性能也显著提高。

粒子群优化算法是一种模拟鸟群觅食行为的优化算法,通过群体中个体间的合作与竞争来寻找最优解。

本文采用文献[19]中改进的粒子群优化算法来训练神经网络,算法流程如下:① 初始化参数,包括种群规模、惯性权重和迭代次数等,按均匀设计方法产生初始种群;② 计算粒子的适应度函数值,更新个体极值和种群全局极值;③ 根据个体极值的适应度函数进行排序,选取本粒子外的n个最优粒子作为本粒子的学习对象,记录n个粒子的当前位置;④ 判断最优粒子在最近L代内是否更新,同时更新粒子的速度和位置;⑤ 若满足最大迭代次数,则停止迭代,输出神经网络的最终权重和阀值,否则转到步骤②。

2.4利用遗传算法优化再制造车间调度问题

编码和解码采用基于工序和机器分配相结合的编码方式[20]。基于工序的编码用来表示工序加工的先后顺序。染色体的长度等于所有工件的总序总数,每个基因表示一个工件号,工件号在染色体中出现的顺序表示工件加工的顺序。基于机器分配的编码用来表示每道工序可选择的加工机器。图2所示为一条染色体样例,表示工序顺序为(O21O11O22O31O12O32O22),机器序列为(M1M2M2M4M3M3M4)。

图2　基于工序和机器的编码

为保证能生成主动调度,本文采用插入式贪婪解码算法[21]。解码过程如下:从首道工序开始,将每道工序插入该工序可选机器上的最佳可行加工时刻,直到所有工序都安排完成为止。

(1)初始化。初始化染色体种群,设置种群大小、交叉概率、变异概率和算法迭代次数等,利用训练好的神经网络检测染色体的可行性,判断是否满足交货期机会约束。

(2)适应度的计算和评价。将训练后的神经网络嵌入到遗传算法中,根据输出数据首先判断在一定置信水平下交货期约束(3)式是否满足,如不满足约束,染色体适应度为0,淘汰该染色体，否则由(1)式和(2)式确定最小成本Cmin和最短的最大加工周期Emin。由于时间和成本的量纲不同,本文对其进行归一化处理,给出时间和成本的权重ω1、ω2,定义适应度函数Fi=ω1Cmin+ω2Emin,然后计算适应度值,其值越小表示该染色体适应度越高。

(3)选择算子。选择操作是根据适应度值选择高性能的个体以更大概率遗传到下一代种群中,本文采用锦标赛选择与精英保留策略相结合的原则[22]。将父代种群中1%的最优个体,不经过交叉和变异,直接复制到下一代种群中;剩下的个体通过锦标赛选择较优的个体,放到下一代种群中。

(4)交叉算子。交叉操作是遗传算法的重要操作,决定着遗传算法的全局搜索能力。基于工序的编码采用改进的基于工件优先顺序的交叉IPOX[23],设父代染色体为P1和P2,交叉后产生子代为C1和C2。其操作过程是将工件集随机分成2个集合J1和J2,复制P1和P2中包含在J1和J2中的工件到C1和C2,并保留它们的位置和顺序,复制P1和P2中不包含在J1和J2中的工件到C2和C1,并保留它们的顺序。IPOX交叉操作过程如图3所示。

图3　基于工序编码的IPOX交叉操作

基于机器编码采用均匀交叉UX,设父代染色体为P1和P2,交叉后产生子代为C1和C2。其操作过程是在染色体长度自然整数内,随机产生r个互不相等的自然数用于标识染色体的位置,复制P1和P2中对应位置的基因到C1和C2中,保持它们的位置和顺序;然后复制P1和P2中剩余的基因到C1和C2中,保持它们的位置和顺序。UX交叉操作过程如图4所示。

图4　基于机器编码的UX交叉操作

(5)变异算子。变异操作过程如图5所示。

图5　基于工序编码和机器编码的变异操作

通过对染色体进行较小的基因改变来生成新的染色体,增加种群的多样性。基于工序编码的变异操作采用插入变异操作,随机选取一个基因,在确保工件加工工序顺序限制的前提下,将其插入到另外一个基因前;基于机器编码的变异操作,随机选择r个位置,每个位置的机器选择可选机器集中负荷较低的设备。

(6)算法终止条件。满足预先设定的最大迭代次数或出现可接受解终止。

3算例分析

以某再制造加工车间为例,现准备在5台设备上加工3个工件,该实例为具有加工时间、成本、交货期约束的再制造加工车间调度问题,具体数据见表1所列。

表1　再制造件模糊加工时间及成本约束

注：机器工时、成本的单位为min；符号“-”表示该工序不能在相应的机器上加工。

表1中,时间和成本用三角模糊数表示,即最乐观值、最可能值和最悲观值;交货期用梯形模糊数表示。

本次试验的算法参数为样本容量1 000、模拟次数1 000,在Matlab R2009平台上构建仿真模型,通过模糊模拟获得样本数据。基于这些样本数据,通过改进的粒子群算法训练神经网络来逼近不确定函数(18个输入神经元、18个隐层神经元、5个输出神经元),种群规模为20,权重因子c1=c2=2,惯性权重ω从0.9逐渐调整到0.4,最大迭代次数为100。把训练好的神经元网络嵌入到遗传算法中,种群规模为100,交叉概率为0.8,变异概率为0.1,最大迭代次数为1 000,优化目标为在一定置信水平下满足交货期满意度约束下最小化完工成本和时间。在CPU为CORE-2 T5600、主频为1.83 GHz、内存为2 GB的硬件环境上应用Matlab R2009编写仿真实验程序。取初始时间和成本的目标权重ω1=ω2=0.5,交货期满意度阀值设为0.8,依次改变置信水平,通过运行智能算法,经过迭代后可以得到目标函数的较优解,见表2所列。

表2　不同置信水平下的仿真结果

从表2可以看出,以适应度值最小为优化目标,随着置信水平的增大,生产系统的稳定性增强,完工成本和完工时间也随着增大。

在一定置信水平不变的条件下(置信水平设为0.8),针对企业的不同需求,改变时间和成本的相对目标权重,通过运行混合智能算法得到的较优调度结果见表3所列。

表3　一定置信水平的较优调度序列

从表3可以看出,不同的权重水平下,调度方案也是不同的,表明再制造企业决策者需要根据相应的目标风险决策方案,选择合理的调度方案。由于篇幅所限,只给出置信水平为0.8、时间和成本的目标权重ω1=ω2=0.5时,混合智能算法的调度结果的迭代过程图,如图6所示。

图6　调度结果收敛曲线

由图6可以看出,由于混合智能算法计算量较大,仿真运行时间也较长,在一定置信水平、迭代次数和约束条件下,该解是一种较为理想的妥协解。

4结束语

本文针对时间和成本不确定的再制造加工车间多目标调度问题进行了研究。首先针对再制造车间决策过程中的不确定性,建立了基于一定置信水平下模糊机会约束规划模型,比其他调度模型更能真实反映再制造加工车间实际情况。然后针对该调度模型,提出一种集模糊模拟、神经网络、粒子群算法和遗传算法相结合的混合智能算法,该算法在求解不确定性调度问题时,具有收敛性好和求解质量高的优良特性。最后通过具体算例验证了模型和混合智能算法的有效性,为不确定环境下研究再制造加工车间调度理论提供了新的思路和方法。

[参考文献]

[1]Lund R T.Remanufacturing[J].Technology Review,1984,87(2):18-23.

[2]刘琳，刘光复，宋守许，等.废旧机电产品再制造工艺过程的经济性分析[J].合肥工业大学学报：自然科学版，2011，34(8)：1121-1125.

[3]Guide V D R.Production planning and control for remanufacturing:industry practice and research needs[J].Journal of Operations Management,2000,18(4):467-483.

[4]Reveliotis S A.Uncertainty management in optimal disassembly planning through learning-based strategies[J].IIE Transactions,2007,39(6):645-658.

[5]Zanoni S,Segerstedt A,Tang O,et al.Multi-product economic lot scheduling problem with manufacturing and remanufacturing using a basic period policy[J].Computers and Industrial Engineering,2012,62(4):1025-1033.

[6]Teunter R,Kaparis K,Tang O.Multi-product economic lot scheduling problem with separate production lines for manufacturing and remanufacturing[J].European Journal of Operational Research,2008,191(3):1241-1253.

[7]Chun S U,Zheng A N.Remanufacturing production planning considering quality cost and demand substiution[J].Journal of Southeast University:English Edition,2011,27(2):222-226.

[8]Jr V G,Souza G C,Laan E V D.Performance of static priority rules for shared facilities in a remanufacturing shop with disassembly and reassembly[J].European Journal of Operational Research,2005,164(2):341-353.

[9]Liu B Y,Chen W D.Single-machine scheduling with preventive periodic maintenance and resumable jobs in remanufacturing system[J].Journal of Southeast University:English Edition,2012,28(3):349-353.

[10]李聪波,刘飞,易茜,等.基于关键链的再制造系统不确定性生产调度方法[J].机械工程学报,2011,47(15):121-126.

[11]刘明周,张玺,刘从虎,等.不确定环境下再制造加工车间生产调度优化方法[J].机械工程学报,2014,50(10):206-212.

[12]刘宝碇,赵瑞清,王纲.不确定规划及应用[M].北京:清华大学出版社,2003:83.

[13]Liu B,Liu Y K.Expected value of fuzzy variable and fuzzy expected value models[J].IEEE Transactions on Fuzzy Systems,2002,10(4):445-450.

[14]Liu B.Toward fuzzy optimization without mathematical ambiguity[J].Fuzzy Optimization and Decision Making,2002,1(1):43-63.

[15]Liu B.Theory and practice of uncertain programming[M].Heidelberg:Physica-Verlag,2002:76.

[16]Liu B,Iwamura K.Chance constrained programming with fuzzy parameters[J].Fuzzy Sets and Systems,1998,94(2):227-237.

[17]张国军,李婵娟,朱海平,等.不确定信息条件下Job-Shop调度的混合智能算法[J].中国机械工程,2007,18(16):1939-1942.

[18]孙燕,谭英,曾建潮.求解模糊机会约束规划模型的微粒群算法[J].系统工程与电子技术,2009,31(2):376-379.

[19]王晓霞,王涛,谷根代.基于改进粒子群优化的神经网络及应用[J].华北电力大学学报:自然科学版,2009,36(5):99-102.

[20]彭建刚,刘明周,张铭鑫,等.基于改进非支配排序的云模型进化多目标柔性作业车间调度[J].机械工程学报,2014,50(12):198-205.

[21]Chen X,Kong Q,Wu Q.Hybird algorithm for job-shop scheduling problem[C]//Procceding of the 4th Congress on Intelligent Control and Automation.Shanghai:East China University of Science and Technology Press,2002:1739-1743.

[22]张超勇,高亮,李新宇,等.基于进化禁忌算法的Job-Shop调度问题研究[J].华中科技大学学报:自然科学版,2009,37(8):80-84.

[23]张超勇,董星,王晓娟,等.基于改进非支配排序遗传算法的多目标柔性作业车间调度[J].机械工程学报,2010,46(11):156-164.

(责任编辑胡亚敏)

Multi-objective optimization method of remanufacturing processing workshop scheduling under uncertain conditions

ZHANG Ming-xin,ZHANG Xi,PENG Jian-gang,CHEN Hong-hai

(School of Machinery and Automobile Engineering,Hefei University of Technology,Hefei 230009,China)

Abstract:The multi-objective optimization method of remanufacturing processing workshop scheduling under uncertain conditions is proposed to solve the uncertainty problem of the processing time and cost for scheduling the remanufactured parts.In this method,the fuzzy variables are used to express the uncertain parameters,and the minimized processing time and cost are taken as the targets,and the fuzzy chance-constrained programming model with multi-objective decision under uncertain conditions is established,which can give solution through using the hybrid intelligence algorithm.To approach the uncertain function,the data generated from the fuzzy simulation are used for training neural networks.The modified particle swarm algorithm is used for overcoming the defect of the low convergence rate and local optimization to optimize the neural networks.The well-trained neural networks are assigned to the modified genetic algorithm to establish the scheduling model.Finally,the feasibility of the model and algorithm is verified through the simulation example.

Key words:remanufacturing;processing workshop scheduling;fuzzy chance-constrained programming;hybrid intelligence algorithm

收稿日期：2015-02-09；修回日期：2015-04-01

基金项目：国家重点基础研究发展计划(973计划)资助项目(2011CB013406)

作者简介：张铭鑫(1980-),男,河北崇礼人,合肥工业大学讲师.

doi:10.3969/j.issn.1003-5060.2016.04.001

中图分类号:TH186

文献标识码：A

文章编号：1003-5060(2016)04-0433-08