基于模糊机会约束规划的再制造装配车间调度优化方法

张铭鑫　葛茂根　张　玺　刘从虎　凌　琳　扈　静

合肥工业大学，合肥，230009

基于模糊机会约束规划的再制造装配车间调度优化方法

张铭鑫葛茂根张玺刘从虎凌琳扈静

合肥工业大学，合肥，230009

针对再制造零部件质量的不确定性导致工位装配时间波动范围大和调度模型难以准确描述的问题，采用基于可信性测度的模糊变量表示再制造零部件的装配时间，建立基于置信水平下的模糊机会约束规划调度模型，并提出求解该模型的混合智能优化算法：应用模糊模拟技术产生样本数据；利用反向传播算法训练多层前向神经网络逼近不确定函数；将训练后的神经网络与遗传算法相结合，以优化再制造装配车间调度问题。实例验证了该模型和算法的可行性。

再制造；装配车间调度；模糊机会约束规划；混合智能算法

0　引言

再制造是指通过回收、拆卸、分拣、清洗、喷涂、翻修及再装配等环节，修复或改造废旧产品，恢复零部件或产品性能的技术和活动[1]。与传统制造过程相比，再制造过程对象是报废的成形零件，存在着尺寸超差、残余应力、内部裂纹和表面变形等一系列缺陷。因此，再制造车间具有多重不确定性，集中表现为[2]：①再制造产生的原因及发生时间、地点、数量等难以准确预测；②再制造产品的性能、质量及制造需求不确定；③产品的再制造工艺路线、再制造周期及再制造成本不确定；④再制造的目标具有多样性，如减少资源消耗、保护环境、降低生产成本和提高服务质量等；⑤再制造后产品的市场需求、价格等难以准确预计。

如何在不确定环境下对再制造车间生产调度进行优化设计，保证再制造生产过程顺利运行，已成为再制造企业提高生产管理水平的关键环节之一。再制造调度主要包括拆卸调度、再加工调度和再装配调度[2]。目前，已有学者对再制造生产调度进行了研究。Li等[3]提出了一种混合遗传算法对再制造生产计划进行优化，且运用优先随机批量机制对其进行仿真。Jac等[4]研究了分组作业调度问题，建立了混合整数规划模型，使用智能算法进行求解。目前再制造调度研究文献主要集中于再制造加工调度，而对再制造拆卸和装配调度研究较少。再制造装配过程中，零部件是由再利用件、再制造件和新品件组成，文献[5-6]描述了再制造装配质量的复杂性，得出零部件的装配质量的不确定性导致工位装配时间波动很大，精确的装配时间难以获得的结论。由于再制造产业的特殊性，对于这些不确定性信息，很难估计它的概率分布规律，只能凭借经验或历史数据给出大致的区间估计，故采用模糊理论来描述不确定信息。模糊集合理论[7]自从提出以来，在自动控制、模式识别等许多领域获得了广泛的应用。研究者就模糊调度问题开展了许多研究。孙燕等[8]提出一种基于微粒群算法的求解模糊机会约束规划的混合智能算法，通过仿真实验验证了其可行性。胡恒等[9]针对加工时间和交货期都不确定的模糊调度问题，提出一种基于多群体并行的遗传算法。

本文在借鉴现有研究成果的基础上，采用模糊变量来描述再制造车间装配时间的不确定性，构建了基于模糊机会约束规划的再制造装配车间的不确定性模型，提出了一种求解该模型的混合智能算法，并给出了求解方法及相应流程，最后，通过仿真实例验证了该混合智能算法对解决再制造装配车间调度问题的可行性。

1　再制造装配车间调度问题模型

1.1模糊变量及其数学描述

不确定环境下的工位装配时间一般采用随机变量或模糊变量来描述，其中描述随机变量的概率密度函数是以大量稳定的统计数据为基础的。对于再制造装配车间而言，零部件质量受回收数量、拆卸数量和库存数量等因素的影响，其不确定性往往导致工位装配时间范围波动很大，因此本文采用基于可信性测度的模糊变量来描述再制造车间工位装配时间。

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

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

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

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

1.2问题描述

再制造装配车间调度问题类似于流水车间调度问题。描述如下：假定一个再制造装配车间有n个产品要在m台机器上进行装配，由于要组装n个产品的零部件质量等级不同，导致工位装配时间和装配成本随零部件质量等级波动范围大，是变化的不确定量；每个产品的装配工序都相同，并且以相同的次序在各机器上装配；同时忽略装配工位的流转时间、准备时间、装配时间和卸载时间，统称为装配时间；在满足工序顺序约束、机器约束和交货期约束等前提下以最小化预定置信水平下最大装配时间的悲观值为调度目标。该模型满足如下假设：①所有产品在每台机器上装配次序相同；②不同产品之间具有相同的优先级；③同一台机器在某一时刻只能装配一个产品，同一产品的同一道工序在同一时刻只能被一台机器装配；④产品的每道工序一旦开始，装配便不能中断；⑤所有产品在零时刻都可以被装配。

1.3调度建模

由于再制造装配时间为模糊变量，因此开始时间、完工时间也都是模糊变量。在这样的模糊环境下，再制造装配车间调度模型无法像经典约束条件那样，给出一个精确的数学模型和确定的可行集。模糊机会约束规划是由Liu等[15]提出的一类模糊规划，其显著特点是模糊约束条件至少以一定的置信水平成立，允许所做决策在一定程度上不满足约束条件，只要求该决策使约束条件成立的可信性不小于决策者预先给定的置信水平。它为不确定性决策问题提供了解决思路。

对于求极小化问题，模糊机会约束规划模型通常表示为

式中，x为决策向量；ξ为模糊向量；f(x,ξ)为目标函数；gi(x,ξ)为约束函数；α、β分别为决策者预先给定的置信水平。

在装配时间为模糊变量的再制造装配车间中，交货期约束可以描述为模糊机会约束，即

现取预定置信水平下最小化最大装配时间悲观值作为优化目标，其模糊机会约束模型描述为

同时，还要受到产品装配顺序约束和机器资源的约束，即

综上所述，装配时间为模糊变量的模糊机会约束规划模型可表示为

2　模型求解

2.1混合智能算法介绍

求解模糊机会约束规划主要有两种方法。第一种方法是转化为确定性的等价规划，但这种方法要求目标函数和约束条件的参数符合某种特征分布。由于再制造车间的不确定性，导致相关参数呈现模糊性特性，故无法转化为清晰等价形式。第二种方法是逼近法，通过模拟仿真生成大量样本数据集来逼近机会约束函数，结合智能算法来优化求解模型。第二种方法更符合再制造生产实际，本文在参考文献[10,16]基础上设计一种将模糊模拟技术、神经元网络和遗传算法相结合而成混合智能算法，用来对模糊机会约束规划进行求解。在仿真平台上，运用模糊模拟技术，产生大量的输入输出样本数据；利用样本数据结合反向传播算法训练多层前向神经网络，逼近不确定函数；将不确定函数嵌入到遗传算法中，检验染色体的可行性和计算染色体的目标值，优化再制造装配调度问题。

2.2模糊模拟

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

利用模糊模拟计算事情的可信性：

L=Cr{g(x,ξ)≤0}≥α

算法步骤[8]如下：

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

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

(3)计算

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

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

(3)计算

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

本文利用仿真软件Extend建立上述模糊模拟模型，进行多次仿真试验，检验模糊机会约束规划模型的约束条件，并计算优化目标值，为训练神经网络提供近似样本数据。

2.3神经网络的函数逼近

2.3.1多层前向神经元网络

人工神经网络是由许多神经元连接而成，用以抽象简化和模拟人脑行为的一类适应系统。Minsky等[17]提出的多层前向神经元网络是目前使用较多的网络结构，已经被广泛用于函数逼近、模式识别和网络优化等领域，已经证明对于任何在闭区间的一个连续函数都可以用一个三层前向神经元网络来逼近。因此，我们通过模糊模拟产生的大量样本数据，训练神经网络来逼近p+1个不确定函数，即

2.3.2反向传播算法训练神经网络

反向传播算法是训练多层前向神经网络的基本方法，它实际上是一种梯度下降的最小化方法。该过程是通过选择权重来极小化网络输出和实际输出之间的误差，是一种无约束化的计算方法。

一般以网络输出的误差平方和

最小作为网络训练的理想结果。其中ω为权重向量、F(xi,ω)为神经网络的输出映射函数，(xi,yi)为训练数据。主要步骤[10]如下。

危害玉米健株生长最主要的地下害虫有地老虎、蝼蛄、金针虫的，其主要危害就是此类地下害虫会吞噬玉米的种子，啃食玉米的根茎部，造成苗株无法发芽或者苗株在生长初期变黄死亡，田间出现缺苗现象，若不加以管控，严重些会导致田间整片没有苗株生长。

(1)初始化权重向量ω，并令μ=1,β=4/3,α=0.05,学习速率η=0.01,预先确定的精确度E0=0.05,适应参数λ=1,k=0。

(2)k←k+1。

(3)根据下列两式调整权值ω：

(4)根据下式计算误差Ek：

式中，dk,i为期望输出；yk,i为实际输出；Φ(x)=ln(cos(βx))/β。

(5)如果k

(7)如果E>E0，那么k=0,λ=exp(-μ/E2)并返回步骤(2)。

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

(1)编码和解码。由于再制造产品装配顺序相同，染色体采用自然数来表示工件的加工顺序。例如[4 2 1 5 3]，表示该批产品的加工顺序为J4、J2、J1、J5、J3，一条染色体对应一个可行的调度方案。

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

(3)适应度函数。将训练后的神经网络嵌入到遗传算法中，根据输出最大装配时间悲观值将染色体由好到坏排序，采用基于序的评价函数eval(Chromoi)=a(1-a)i-1进行评价，其中，a为评价参数，eval表示评价函数，Chromoi表示第i个染色体。

(4)选择。从父代染色体种群中选择适应值最高的个体遗传到下一代种群中。本文采用最常用的轮盘赌选择法进行选择。

(5)交叉。采用随机两点交叉，其操作规则是，首先随机选取两个基因作为交叉基因，交叉后，判断染色体中[1,n]区间内缺失的自然数，然后将未参与交叉基因中重复的自然数替换成缺失的自然数。

(6)变异。随机选取染色体中的部分基因进行互换，以维护种群的多样性。

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

综上所述，混合智能算法主要步骤如图1所示。

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

3　算例分析

以某再制造装配车间为例，现准备装配7个产品，装配工序由5台机器完成。根据对历史数据的统计分析，总结出组装产品的再制造件在不同失效等级的概率及对应情况下的模糊加工时间(用三角模糊数表示)和交货期机会约束，如表1所示。如组装产品J1的零部件失效等级为二级的概率约为0.56，在机器M1上的工序装配时间为(16,17,19)min，即最乐观加工时间为16min，最可能加工时间为17min，最悲观加工时间为19min。产品J1在置信水平0.7下，交货期为485min；在置信水平0.8下，交货期为500min；在置信水平0.9下，交货期为515min。

表1　废旧件模糊装配时间及交货期机会约束

本次试验通过仿真软件Extend建立模糊模拟仿真模型，样本容量为1000，模糊模拟次数为1000，以获得样本数据；基于这些样本数据，利用反向传播算法(初始化权重0.9)训练神经元网络(7个输入神经元，15个隐层神经元，8个输出神经元)来逼近不确定函数；把训练好的神经元网络嵌入到遗传算法中，种群规模50，最大迭代次数1000，交叉概率0.8，变异概率0.1，基于序的评价常数a=0.05，优化目标为满足工序顺序约束、机器约束和交货期约束等前提下最小化预定置信水平下最大装配时间的悲观值。在CPU为CORE-2T5600，主频为1.83GHz，内存为2GB的硬件环境上应用MATLABR2009编写仿真实验程序。依次改变置信水平，通过运行混合智能算法得到的调度结果如表2所示。由表2可以看出，不同的置信水平下，调度方案是不完全相同的，表中的调度结果不一定是最优解，但是能够保证在满足相关约束和在一定置信水平前提下，最大的装配时间悲观值最小。随着置信水平的增大，系统的稳定性增强，装配周期也随着增大，表明再制造企业决策者要根据管理目标，选择相应的置信水平，折中选择相应的调度方案。由于篇幅所限，只给出置信水平为0.8时，算法最优结果的迭代过程图(图2)。从图2可以看出，由于混合智能算法计算量较大，仿真运行时间也较长，在一定置信水平下，该解是一种较理想的妥协解。

表2　不同置信水平下的调度结果

图2　调度结果收敛曲线

4　结论

(1)针对不确定环境下的再制造装配车间调度问题，采用基于可信性测度的模糊变量描述装配时间，建立了约束条件以一定置信水平成立的模糊机会约束规划调度模型，并研究了模型的求解方法。

(2)提出了一种集模糊模拟、神经网络和遗传算法相结合的混合智能算法。应用模糊模拟技术在仿真软件平台上产生样本数据，通过反向传播算法训练神经网络以逼近不确定函数，并将训练好的神经网络和遗传算法相结合，求解再制造装配调度问题。

(3)通过实例对模型和算法的可行性进行了验证。该模型和算法为不确定性环境下再制造装配车间调度理论提供了新的思路和方法。

[1]徐滨士,刘世参,史佩京,等.汽车发动机再制造效益分析及对循环经济的贡献[J].中国表面工程,2005(1):1-7.

XuBinshi,LiuShican,ShiPeijingetal.StudyontheContributionofEngineRemanufacturingtotheRecycleEconomy[J]ChinaSurfaceEngineering,2005(1):1-7.

[2]GuideJrVDR.ProductionPlanningandControlforRemanufacturing:IndustryPracticeandResearchNeeds[J].JournalofOperationsManagement,2000,18(4): 467-483.

[3]LiJianzhi,MiguelG,ZhuYun.AHybridSimulationoptimizationMethodforProductionPlanningofDedicatedRemanufacturing[J].InternationalJournalofProductionEconomics, 2009, 117(2): 286-301.

[4]MinJ,KimJS,LeeDH.SchedulingAlgorithmstoMinimizetheTotalFamilyFlowTimeforJobShopswithJobFamilies[J].InternationalJournalofProductionResearch, 2011, 49(22): 6885-6903.

[5]GeMaogen,LiuConghu,LiuMingzhou.TheOnlineQualityControlMethodsfortheAssemblingofRemanufacturedEngines’CylinderBlockandCoverunderUncertainty[J].TheInternationalJournalofAdvancedManufacturingTechnology, 2014,74(1/4):225-233.

[6]LiuMingzhou，LiuConghu,XingLingling,etal.QualityOrientedAssemblyGroupingOptimalAllocationMethodforRemanufacturedComplexMechanicalProducts[J].ChineseJournalofMechanicalEngineering, 2014,50(8):150-155.

[7]ZadehlA.FuzzySets[J].InformationandControl,1965,8:383-353.

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

SunYan,TanYing,ZengJianchao.ParticleSwarmOptimizationforFuzzyChanceConstrainedProgrammingModel[J].SystemsEngineeringandElectronics,2009,31(2):376-379.

[9]胡恒,鲁建厦,李英德.基于多群体并行遗传算法的混流混合车间模糊调度研究[J].浙江工业大学学报,2012,40(5):554-558.

HuHeng,LuJiansha,LiYingde.StudyofMixed-ModelHybridShopFuzzySchedulingProblemBaseonMulti-PopulationsParallelGeneticAlgorithm[J].JournalofZheJiangUniversityofTechnology,2012,40(5):554-558.

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

[11]LiuB,LiuYK.ExpectedValueofFuzzyVariableandFuzzyExpectedValueModels[J].IEEETransactionsonFuzzySystems,2002,10(4):445-450.

[12]LiuB.TowardFuzzyOptimizationwithoutMathematicalAmbiguity[J].FuzzyOptimizationandDecisionMaking,2002,1(1):13-28.

[13]NahmiasS.FuzzyVariables[J].FuzzySetsandSystems,1978,1(2):97-110.

[14]LiuB.TheoryandPracticeofUncertainProgramming[M].Heidelberg:PhysicaVerlag,2002.

[15]LiuB,IwanmuraK.Chance-constrainedProgrammingwithFuzzyParamerers[J].FuzzySetsandSystems,1998,94(2): 227-237.

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

ZhangGuojun,LiChanjuan,ZhuHaiping,etal.AHybridIntelligentAlgorithmforJob-shopSchedulingunderUncertainInformationEnvironment[J].ChinaMechanicalEngineering,2007,18(16): 1939-1942.[17]MinskyM,PapertS.Perceptrons[M].Cambridge,MA:MITPress, 1969.

(编辑袁兴玲)

Optimization Method of Remanufacturing Assembly Shop Scheduling Based on Fuzzy Chance-constrained Programming

Zhang MingxinGe MaogenZhang XiLiu ChonghuLing LinHu Jing

Hefei University of Technology,Hefei,230009

The quality uncertainty during the process of parts reassembling caused the big range of the fluctuation of the assembly time and difficult description of scheduling mode. Aiming at this problem, the assembly time of the reassembled parts was represented by the fuzzy variable based on credibility measure to establish the scheduling model with the fuzzy chance-constraints based on the confidence level. Then, a hybrid intelligent optimization algorithm was proposed combined with a neural network and genetic algorithm, where the neural network based on back propagation algorithms was to approximate the undetermined relation function between the input and output data generated by using the fuzzy simulation technique and the genetic algorithm embedded the trained neural network was to solve the scheduling model. Finally, a study case was given to prove the feasibility of the proposed model and algorithm.

remanufacturing；assembly shop scheduling；fuzzy chance-constrained programming；hybrid intelligent algorithm

2014-08-22

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

TH186DOI：10.3969/j.issn.1004-132X.2015.11.011

张铭鑫，男，1980年生。合肥工业大学机械与汽车工程学院讲师、博士研究生。主要研究方向为生产系统建模与仿真等。葛茂根，男，1979年生。合肥工业大学机械与汽车工程学院副教授。张玺，男，1985年生。合肥工业大学机械与汽车工程学院博士研究生。刘从虎，男，1981年生。合肥工业大学机械与汽车工程学院博士研究生。凌琳，女，1987年生。合肥工业大学机械与汽车工程学院助教、博士。扈静，女，1976年生。合肥工业大学机械与汽车工程学院副教授。