基于模糊機會約束規劃的再制造裝配車間調度優化方法

張銘鑫　葛茂根　張　璽　劉從虎　凌　琳　扈　靜

合肥工業大學，合肥，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年生。合肥工業大學機械與汽車工程學院副教授。