云制造下小批量定制產(chǎn)品的服務(wù)組合雙層優(yōu)選方法

袁 偉,郭 偉,2,王 磊+,馬 劍

(1.天津大學(xué) 機械工程學(xué)院,天津 300072;2.天津仁愛學(xué)院 機械工程學(xué)院,天津 301636)

0 引言

隨著信息化技術(shù)的發(fā)展,各行業(yè)也朝著數(shù)字化、網(wǎng)絡(luò)化、智能化的方向前進,我國相繼出臺了“中國制造2025”和“互聯(lián)網(wǎng)+”等發(fā)展實施戰(zhàn)略,旨在促進新一代信息技術(shù)與制造業(yè)深度融合,推動實體經(jīng)濟轉(zhuǎn)型升級[1-2]。而制造業(yè)與信息技術(shù)的融合則催生出了更多面向服務(wù)的新型制造模式,也將制造行業(yè)的焦點聚集在資源使用效率和共享程度問題上,為此李伯虎院士提出了一種網(wǎng)絡(luò)化制造新模式——云制造[3-4]。云制造模式促進了制造行業(yè)整體資源的利用及合作共享,提高了制造企業(yè)的市場競爭力,而隨著全球市場的發(fā)展以及客戶多樣化個性化動態(tài)化的需求擴大,小批量定制產(chǎn)品在市場上獲得了越來越多的份額[5]。小批量定制產(chǎn)品能夠讓客戶獲得與自身需求相一致的準確產(chǎn)品,但個性化定制在商業(yè)運作原理上與大批量生產(chǎn)存在顯著差異,其一般采用非標(biāo)定制模式進行生產(chǎn),導(dǎo)致制造成本高;而現(xiàn)有企業(yè)的生產(chǎn)系統(tǒng)、信息化管理方法以及所具備的生產(chǎn)能力都很難滿足這種個性化生產(chǎn)的需要[6-7]。因此,結(jié)合云制造模式對小批量定制產(chǎn)品的生產(chǎn)制造進行需求任務(wù)的有效分解和制造資源的優(yōu)選匹配成為了關(guān)鍵途徑。云制造模式需同時協(xié)調(diào)需求方和供應(yīng)方的相關(guān)信息,對于用戶復(fù)雜的制造需求還需選擇多個細粒度的簡單云制造服務(wù)組合形成粗粒度的復(fù)雜云服務(wù),因而云制造服務(wù)組合模型的構(gòu)建及其求解算法決定了所選服務(wù)組合方案的優(yōu)劣[8-9]。

目前,國內(nèi)外學(xué)者已經(jīng)對云制造模式下服務(wù)匹配的相關(guān)問題進行了大量研究。為解決云制造環(huán)境下?lián)碛写_定性子任務(wù)加工順序的服務(wù)組合靈活性差的問題,鄭煒等[10]提出用于描述加工順序的工藝邏輯矩陣,將加工順序交換機制加入算法中并建立基于雙層蟻群算法進行求解的服務(wù)組合優(yōu)選模型。針對云制造下服務(wù)組合如何滿足供需雙方偏好的問題,陳友玲等[11]建立了以服務(wù)需求方約束和資源提供方約束為基礎(chǔ)的雙方約束模型,并提出一種改進的快速非支配排序遺傳算法進行求解;馬仁杰等[12]提出一種基于區(qū)間和灰色關(guān)聯(lián)度的云制造服務(wù)綜合匹配推薦方法,對服務(wù)資源類型和質(zhì)量信息等進行匹配和過濾。針對服務(wù)組合優(yōu)選中的解空間大、求解效率低等問題,ZHOU等[13]構(gòu)建了以時間、成本、可靠性和可用性為評價指標(biāo)的評價模型,通過混合人工蜂群算法求解出最佳服務(wù)組合;BOUZARY等[14]基于灰狼優(yōu)化器(Grey Wolf Optimization,GWO),通過更好的交叉變異探索能力提升求解的效率。針對云環(huán)境下制造服務(wù)供需匹配中雙方的動態(tài)變化問題,XUE等[15]提出一種基于計算實驗的評價框架來驗證服務(wù)匹配策略性能,以提升服務(wù)匹配策略的適應(yīng)性能力。針對云制造環(huán)境下資源組合的地域分散性強、供應(yīng)復(fù)雜化等特征,朱李楠等[16]提出一種改進的差分進化算法,設(shè)計了一種最佳運輸方案選擇策略以解決資源組合的調(diào)度問題;王旭亮等[17]提出一種基于切削算法框架并適用于跨企業(yè)、多約束、多品種、小批量的有限能力調(diào)度算法,為供應(yīng)鏈中供需企業(yè)的協(xié)同生產(chǎn)計劃進行尋優(yōu),實現(xiàn)生產(chǎn)資源的優(yōu)化配置。在面向云制造下服務(wù)商的供應(yīng)選擇上,SIMEONE等[18]針對服務(wù)方和需求方的多樣化,建立了深度神經(jīng)網(wǎng)絡(luò)為客戶提供決策推薦,實現(xiàn)服務(wù)匹配中的供應(yīng)優(yōu)選。

以上研究聚焦于云制造下的服務(wù)組合優(yōu)選模型和求解算法,在模型上大多選擇將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,在算法層面依靠不同的啟發(fā)式算法及變異操作提高求解的速率。然而,這類處理一方面忽視了候選集的產(chǎn)生過程,導(dǎo)致算法尋優(yōu)空間大,求解效率低,這是由于算法的尋優(yōu)能力不僅依賴于其本身的求解邏輯,還依賴于輸入的數(shù)據(jù)源;另一方面,這類處理對最終的優(yōu)選模型采用多目標(biāo)轉(zhuǎn)為單目標(biāo)的方法,如文獻[10]和文獻[16],其權(quán)重的選取帶有較強的主觀性。更重要地,在對制造任務(wù)進行分解時,如文獻[11]～文獻[15],多采用粗粒度模式與既定的任務(wù)加工順序,而文獻[16]～文獻[18]從更廣域的云協(xié)作視角解決企業(yè)間的資源調(diào)度問題以及對需求方的資源推薦問題,這類任務(wù)分解模式在實際應(yīng)用中會因分配不夠明細而難以完全應(yīng)對需求來匹配特性企業(yè),企業(yè)間的協(xié)同交互性低,不利于加工生產(chǎn)的實時調(diào)控,更不利于定制化產(chǎn)品的小批量生產(chǎn)特性和對成品的高標(biāo)準要求。在云制造中,任務(wù)的基本粒度是指服務(wù)所執(zhí)行操作的基本單元,可分為產(chǎn)品級、部件級、零件級和工序級等。對于小批量定制化產(chǎn)品而言,應(yīng)對其需求進行細化分解、逐一分析來實現(xiàn)面向服務(wù)的云制造生產(chǎn)模式。因此部分企業(yè)建立了區(qū)域內(nèi)加工資源共享平臺,特別是長三角一帶的模具加工協(xié)作集群、高精密航空類零件的協(xié)作加工等,其以平臺為基礎(chǔ),通過企業(yè)資源高度共享與專業(yè)化協(xié)作分工,實現(xiàn)細粒度加工任務(wù)與服務(wù)的高精度匹配。但目前卻少有文獻對細粒度資源服務(wù)組合的模式及其優(yōu)選方法進行分析與建立。

在這種背景下,本文提出了以零件的加工特征作為任務(wù)基本粒度,以零件的工藝信息和區(qū)域制造資源為基礎(chǔ),建立需求信息模型和制造資源供應(yīng)信息模型對供需兩方進行描述。為充分表達與存儲供需信息,本文引入知識圖譜技術(shù),結(jié)合節(jié)點關(guān)系以及實例化數(shù)據(jù)構(gòu)建利于匹配的需求—特征圖譜、制造資源供應(yīng)圖譜,再通過特征級服務(wù)排序優(yōu)選階段進行供應(yīng)商初篩,并在該階段設(shè)立了加工合格率、滿意度評價值、交付按時率、供應(yīng)偏好值4個評價指標(biāo)并依托變異系數(shù)法進行賦權(quán)求和。最后建立以工藝總成本、工藝總時間及總碳排放作為優(yōu)化目標(biāo)、特征間的優(yōu)先級關(guān)系作為約束的多目標(biāo)優(yōu)化模型,并通過融入次候選集變異算子的改進遺傳算法NSGA-Ⅲ對其進行求解,以獲得最佳的制造服務(wù)組合方案。

在該方法下,通過將特征作為基本單元進行供應(yīng)企業(yè)優(yōu)選,優(yōu)化目標(biāo)不僅涵蓋成本和時間要素,還考慮了以碳排放量為指標(biāo)的綠色生產(chǎn)要求,響應(yīng)國家“碳達峰、碳中和”的低碳生產(chǎn)目標(biāo)的同時,有效地實現(xiàn)了面向服務(wù)的制造。該方法可以用在基于云制造的零件全工藝流程的規(guī)劃管理中,如新研發(fā)零件,通過服務(wù)組合能夠有效利用區(qū)域內(nèi)的優(yōu)質(zhì)供應(yīng)商,實現(xiàn)研發(fā)階段的制造高效化;該方法也可用于部分工藝流程在云制造下進行外協(xié)加工的決策管理中,如企業(yè)面臨對復(fù)雜零件加工能力不足的情形。

1 供需信息描述與圖譜建立

在高共享的區(qū)域云制造模式下,選用合理的匹配粒度構(gòu)建大數(shù)據(jù)驅(qū)動下的資源優(yōu)選配置模型,是提高匹配效率、促進生產(chǎn)制造協(xié)同化發(fā)展的關(guān)鍵點。由此,面向定制需求將工藝規(guī)劃任務(wù)粒度分解至特征層面,再基于零件工藝特征進行需求信息描述與供應(yīng)信息描述。較傳統(tǒng)的加工車間分類或零件加工單元分類該方式粒度更細,分類更有針對性。

1.1 零件的工藝信息描述

1.1.1 零件的工藝信息模型

為便于工藝信息的匹配,本文在建立供需圖譜之前,將對零件的相關(guān)信息進行定義描述。

零件的加工特征包括零件特定的幾何構(gòu)形,以及具有實際工程意義和滿足制造要求等信息集合,是形成零件幾何形狀和信息模型的基本單元,其知識化描述是工藝路線規(guī)劃的前提和基礎(chǔ)[19]。

在構(gòu)建零件的信息模型時,可以將工件拆解成若干個加工特征,其在數(shù)學(xué)上表達為:

(1)

其中:PMF為待加工工件的特征集合,ProM為工序模型,MFi為特征單元。

根據(jù)云制造所需的機加工特性表達,工件的特征單元MF又可描述為如下的七元組形式:

MF={ID,FT,SF,MC,AF,PC,PFs}。

(2)

其中:ID表示該特征單元的序列編號,FT表示其加工特征類型,SF表示其尺寸特征,MC表示其材料特征,AF表示其精度特征,PC表示特征單元的加工鏈,PFs表示該特征單元的先行特征集,即加工順序更優(yōu)先的特征單元的序列編號集合。

根據(jù)現(xiàn)行標(biāo)準,綜合考慮云制造下的加工要素匹配,可將加工特征類型FT分成16大類[20]。即FT={凸臺類,腔孔類,槽類,凸起類,圓角類,外圓類,臺階類,平面類,旋轉(zhuǎn)特征類,球冠類,輪廓類,螺紋類,標(biāo)記類,滾花類,一般移除體積類,肋頂類}。

1.1.2 加工特征的約束處理

在工藝規(guī)劃中,由于各工藝工序任務(wù)間有優(yōu)先級關(guān)系,受到工序排序規(guī)則的約束,需要滿足“先粗后精”、“先主后次”、“先基準后其他”等基本條件,故各任務(wù)間具有時序性,應(yīng)在工作流建模的基礎(chǔ)上進行任務(wù)分解[21]。

為此,整合各條件后將加工特征定義以下約束關(guān)系:

(1)先粗后精型約束關(guān)系 該約束主要針對各特征級內(nèi)部的加工方法,加工方法順序隨工藝方案確定,如粗銑—半精銑—精銑。

(2)主次優(yōu)先型約束關(guān)系 主次特征由零部件的應(yīng)用功能決定,在設(shè)計階段根據(jù)用戶需求設(shè)計零件結(jié)構(gòu),結(jié)合實際功能特性可得到主次優(yōu)先關(guān)系。如同一平面類特征擁有普通精度要求的臺階類特征和高精要求的腔孔類特征,則前者為次要特征,后者為主要特征。

(3)基準優(yōu)先型約束關(guān)系 基準由零部件的設(shè)計信息決定,在面向基準特征與其依賴特征的加工時,應(yīng)優(yōu)先加工基準特征。

(4)非破壞型約束關(guān)系 如“先面后孔”的通用規(guī)則等決定的約束關(guān)系。

利用以上4類特征約束關(guān)系可構(gòu)建各工藝任務(wù)間的關(guān)聯(lián)關(guān)系,以優(yōu)先關(guān)系實例化后通過約束矩陣進行量化處理。

1.2 供需信息建模

在區(qū)域云制造環(huán)境下,為了實現(xiàn)需求與供應(yīng)的精準匹配,需要構(gòu)建需求端與供給端的信息模型。

1.2.1 需求信息模型

在需求端,以零件的信息模型為基礎(chǔ),融合需求商所要求的加工數(shù)量、成本限額、時間限額等要素,可構(gòu)建需求層面的任務(wù)信息。

需求信息如圖1所示,可表達為:

圖1 需求信息模型圖

DI={PMF(n),PM,TQ,CC,AD}。

(3)

其中:PMF(n)為需求端待加工零件的n個特征單元集合,PM為加工數(shù)量,TQ為時間限額,CC為成本限額,AD為需求方位置信息。

1.2.2 供應(yīng)信息模型

在資源供應(yīng)端,以企業(yè)可提供的閑置加工資源為主,面向需求端通過資源集成與優(yōu)化配置,完成從面向生產(chǎn)的制造到面向服務(wù)的制造的轉(zhuǎn)型,促進區(qū)域云制造下加工服務(wù)的協(xié)同化發(fā)展。在企業(yè)制造資源供應(yīng)信息上,以企業(yè)的名稱代號nE、位置信息adE及制造資源mEs作為供應(yīng)信息數(shù)據(jù),其表達形式為:

SI={nE,adE,mEs}。

(4)

其中:nE為企業(yè)代號;adE為服務(wù)供應(yīng)企業(yè)的位置信息;mEs為企業(yè)所能提供的制造資源集合,mEs包含n個制造資源mE,即

(5)

mE主要包括7類信息,其表達式如下:

mEj={FT,SF,MC,AF,mAbility,mFC,mPlan}。

(6)

其中:FT為可加工特征類型,SF為企業(yè)設(shè)備在該特征下所能加工的尺寸信息,MC為可加工的工藝材料信息,AF為工藝精度信息,mAbility為該特征類型下供應(yīng)企業(yè)的單位時間生產(chǎn)能力,mFC為該特征類型下供應(yīng)企業(yè)的單位產(chǎn)量加工成本,mPlan為該特征所用設(shè)備短期運載情況。

1.3 供需信息知識圖譜構(gòu)建

為充分表達需求信息同時便于檢索,本文引入知識圖譜技術(shù)用以實現(xiàn)多層次多要素信息的結(jié)構(gòu)化表達,構(gòu)建利于匹配的制造資源供應(yīng)圖譜、需求—特征圖譜。知識圖譜在邏輯上可分為模式層與數(shù)據(jù)層兩個層次,模式層構(gòu)建在數(shù)據(jù)層之上,是工藝知識圖譜的核心,主要通過本體庫來規(guī)范數(shù)據(jù)層的一系列事實表達[22]。本文在圖譜的構(gòu)建中,為減少數(shù)據(jù)的冗余,保證索引關(guān)系的準確性與一致性,采用自頂向下設(shè)計,定義數(shù)據(jù)模式,根據(jù)信息模型并結(jié)合實際生產(chǎn)數(shù)據(jù)凝練構(gòu)建4類關(guān)系如表1所示。將供需信息模型及關(guān)系賦予到圖譜的模式層,完成其本體化表達。

表1 關(guān)系類型及其示例

在模式層實體關(guān)系數(shù)據(jù)的引導(dǎo)下,對工業(yè)生產(chǎn)數(shù)據(jù)進行預(yù)處理,得到實例數(shù)據(jù)的形式化表達,以〈實體,關(guān)系,實體〉及〈實體,屬性,屬性值〉作為基本表達方式構(gòu)建知識圖譜的數(shù)據(jù)層,并在實際應(yīng)用中不斷擴充。

在數(shù)據(jù)存儲方面,基于實際生產(chǎn)數(shù)據(jù)的復(fù)雜性,采用圖數(shù)據(jù)庫的存儲形式更有優(yōu)勢。這是由于涉及到多度的關(guān)聯(lián)查詢、模糊查詢,以及實際運行時的增刪改查等操作,基于圖數(shù)據(jù)庫的效率會比關(guān)系數(shù)據(jù)庫的效率高出數(shù)千倍乃至數(shù)萬倍。本文采用Neo4j圖數(shù)據(jù)進行數(shù)據(jù)的存儲及可視化表達。較其他圖數(shù)據(jù)庫,Neo4j遵循屬性圖數(shù)據(jù)模型,在大規(guī)模數(shù)據(jù)中檢索遍歷速度更快,且支持多度關(guān)系查詢及模糊查詢等。

如圖2所示為本文構(gòu)建圖譜的整體過程,以及實例化的部分制造資源供應(yīng)圖譜、需求—特征圖譜。

圖2 供需圖譜構(gòu)建過程

2 面向特征級服務(wù)的一層優(yōu)選過程

在特征級服務(wù)優(yōu)選中,主要分為需求任務(wù)發(fā)布階段、信息匹配篩選可用供應(yīng)資源階段和特征級服務(wù)排序優(yōu)選階段3個階段。

(1)需求任務(wù)發(fā)布階段 該階段由需求方根據(jù)需求信息模型DI進行任務(wù)描述,如圖1所示,DI五元組所包含的加工數(shù)量PM、時間限額TQ、成本限額CC、需求方位置信息AD將作為一級任務(wù)指標(biāo)的屬性與約束,而DI五元組中的特征集PMF將進一步拆分為若干個特征單元MFi,每個特征單元MFi由七元組{ID,FT,SF,MC,AF,PC,PFs}構(gòu)成,特征單元MFi將作為二級任務(wù)指標(biāo)進行特征級任務(wù)的服務(wù)篩選,由此形成完整的需求信息。相關(guān)數(shù)據(jù)以增量形式存入圖數(shù)據(jù)庫中完成新需求—特征子圖譜的構(gòu)建,借助于圖數(shù)據(jù)庫特有的靈活性與敏捷性,可以對已存在的圖結(jié)構(gòu)動態(tài)增加新的邊及節(jié)點。以此實現(xiàn)將總?cè)蝿?wù)拆解成若干個子任務(wù)并完成數(shù)據(jù)的存儲。

(2)信息匹配可用供應(yīng)資源階段 在匹配可用供應(yīng)資源時,使用預(yù)先構(gòu)建的制造資源供應(yīng)圖譜,該圖譜由各服務(wù)供應(yīng)方將自己可提供的加工服務(wù)輸入到云制造服務(wù)平臺后形成。匹配時,以特征級需求任務(wù)為單位對企業(yè)進行篩選,選擇滿足該特征級任務(wù)下全指標(biāo)要求的企業(yè)作為初步候選服務(wù)集。其中序列編號ID作為特征標(biāo)識、優(yōu)先工藝集PFs作為特征間順序約束關(guān)系不在篩選中體現(xiàn)。執(zhí)行該階段時采用Neo4j的Cypher語言可通過對相關(guān)資源及其屬性進行多度關(guān)系查詢,如通過“MATCH(A)-[∶‘include’]-(B)-[r]-(C∶‘FT’)WHEREC.name=‘平面類’RETURNA,B,C”等語句不需建立復(fù)雜連接即可檢索到滿足要求的相關(guān)節(jié)點及其子節(jié)點及屬性,提高檢索效率。

(3)特征級服務(wù)排序優(yōu)選階段 根據(jù)步驟(2)得到的初步候選服務(wù)集作進一步優(yōu)選,考慮加工合格率PYF、滿意度評價值S、交付按時率TL、供應(yīng)偏好值Bias四個主要因素。

1)加工合格率PYF。指服務(wù)供應(yīng)企業(yè)往期加工該特征類型的合格品總量Ne占加工該特征類型總量Ns的百分比。該指標(biāo)在一定程度上表達了企業(yè)對該特征類型的加工能力,即是否能夠加工好該特征類型的工件。

(7)

2)滿意度評價值S。指服務(wù)供應(yīng)企業(yè)的往期客戶對該服務(wù)企業(yè)的綜合評價,其中S∈[0,1]。該指標(biāo)在一定程度上表達了企業(yè)的服務(wù)能力。

(8)

3)交付按時率TL。指服務(wù)供應(yīng)企業(yè)往期在承接任務(wù)時,于預(yù)定時間內(nèi)交付的次數(shù)Na占總承接的次數(shù)NT的百分比。該指標(biāo)在一定程度上表達了企業(yè)自身的項目管理能力和準時性。

(9)

4)供應(yīng)偏好值Bias。指服務(wù)供應(yīng)企業(yè)往期在承接任務(wù)時,加工該特征類型的數(shù)量Nv占加工所有類型的總數(shù)量Nall的百分比。該指標(biāo)在一定程度上表達了企業(yè)在特征加工選型方面的偏好,即是否更傾向于加工該特征類型的工件。

(10)

加工合格率PYF、滿意度評價值S、交付按時率TL、供應(yīng)偏好值Bias四個因素的取值范圍都在[0,1]之間。在進行下一步的多目標(biāo)優(yōu)化之前,考慮到會因候選服務(wù)集過多而難尋優(yōu)的情況,為降低服務(wù)組合優(yōu)選算法的尋優(yōu)空間,在本階段會先進行一輪篩選得到二輪候選服務(wù)集,再進行后續(xù)求解。

指標(biāo)權(quán)重的確定是多要素綜合評價中的關(guān)鍵環(huán)節(jié),權(quán)重確定的是否合理將直接影響評價結(jié)果的可靠性和有效性[23]。在本階段以特征為粒度的服務(wù)篩選中,4類因素的權(quán)重確定可以采用主觀賦權(quán)法或客觀賦權(quán)法。其中,主觀賦權(quán)法大多需要依賴專家經(jīng)驗知識,實施難度較大且具有主觀性和不確定性,而客觀賦權(quán)法主要由數(shù)據(jù)樣本的特征決定。為綜合考量由4類因素影響力進行的排序優(yōu)選以實現(xiàn)協(xié)同效應(yīng),可采用變異系數(shù)法進行權(quán)重賦值。該方法能夠客觀地體現(xiàn)指標(biāo)的區(qū)分度,根據(jù)各指標(biāo)在所有被評價對象上觀測值的變異程度大小來對其賦權(quán),具體步驟如下:

步驟1數(shù)據(jù)歸一化。因特征級服務(wù)排序優(yōu)選階段的4類指標(biāo)取值均在[0,1]內(nèi),故無需歸一化,可得評價指標(biāo)的數(shù)據(jù)矩陣Xe。Xe為含4項評價指標(biāo)、n個評價對象的4×n的矩陣。

(11)

在矩陣Xe中,PYFi、Si、TLi、Biasi分別表示第i個評價對象的加工合格率、滿意度評價值、交付按時率和供應(yīng)偏好值。

步驟2計算各指標(biāo)的平均值與標(biāo)準差。

(12)

(13)

其中S1、S2、S3、S4分別表示4類指標(biāo)的標(biāo)準差。

步驟3計算各指標(biāo)的變異系數(shù)。該變異系數(shù)反映了各指標(biāo)的相對變異程度。

(14)

步驟4對變異系數(shù)進行歸一化處理,得到各指標(biāo)的權(quán)重。

(15)

從而得到最終的指標(biāo)權(quán)重{w1,w2,w3,w4}。以該權(quán)重對4項指標(biāo)進行賦權(quán)求和得到供應(yīng)商特征級服務(wù)的綜合評估分數(shù)Cs。通過在各特征粒度下對供應(yīng)商的綜合評估分數(shù)Cs進行排序,設(shè)立優(yōu)選百分比α得到候選集。本文在后續(xù)的尋優(yōu)中,會用到主候選集、次候選集兩類,對其分別設(shè)立優(yōu)選比α1、α2。優(yōu)選比的數(shù)值可根據(jù)實際情況進行設(shè)置,如將α1設(shè)為10%,α2設(shè)為30%,則排序在前10%的優(yōu)質(zhì)企業(yè)會被選為主候選集,排序在10%～30%之間的企業(yè)會被選為次候選集。主候選集是服務(wù)組合模型求解時的主要供應(yīng)商,次候選集僅作為后續(xù)算法在物流層面優(yōu)化的備選項。

在獲取相關(guān)統(tǒng)計指標(biāo)時,可以結(jié)合歷史存儲圖譜進行快速查詢與計算。對于云平臺而言,當(dāng)歷史訂單完成后,需求—特征圖譜即轉(zhuǎn)為歷史數(shù)據(jù),通過對歷史需求—特征圖譜的需求數(shù)據(jù)與其對接的制造資源數(shù)據(jù)間的關(guān)聯(lián)關(guān)系采用Cypher的聚合函數(shù),可以實現(xiàn)Ne、Nv等指標(biāo)的快速統(tǒng)計。

3 制造資源服務(wù)組合的二層優(yōu)選過程

3.1 服務(wù)組合優(yōu)選的集成規(guī)劃模型

為響應(yīng)“碳達峰、碳中和”的戰(zhàn)略目標(biāo),制造資源的服務(wù)組合不僅考慮到成本和時間要素,同時也對碳排放進行優(yōu)化選擇。因此,在上一階段篩選出優(yōu)質(zhì)供應(yīng)商后,以工藝總成本、工藝總時間及總碳排放為優(yōu)化目標(biāo)建立目標(biāo)函數(shù),以特征間優(yōu)先級關(guān)系為約束條件構(gòu)建約束矩陣進行優(yōu)化求解,實現(xiàn)二層優(yōu)選。

3.1.1 目標(biāo)函數(shù)

服務(wù)組合選型優(yōu)化目標(biāo)以成本、時間和低碳為主。成本控制的核心涵蓋制造成本和物流成本兩大塊,工藝總時間包括各任務(wù)加工時間和跨企業(yè)運輸時間,綠色生產(chǎn)主要以控制設(shè)備加工中的碳排放量為主。由此構(gòu)建如下優(yōu)化目標(biāo)函數(shù):

(1)工藝總成本目標(biāo)函數(shù)

(16)

式中:PCn為工藝總成本,mFCi為第i類特征單位產(chǎn)量加工成本,adEi為第i類特征加工企業(yè)的位置信息,Tc為運輸成本因子,PM為加工數(shù)量。

(2)工藝總時間目標(biāo)函數(shù)

(17)

其中:TC為工藝總時間,mAbilityi為第i類特征供應(yīng)企業(yè)的單位時間生產(chǎn)能力,adEi為第i類特征加工企業(yè)的位置信息,Tc為運輸時間因子,PM為加工數(shù)量。

(3)加工總碳排放目標(biāo)函數(shù)

碳排放含量的計算參照文獻[24]和文獻[25],基于本方案的應(yīng)用背景,為保證合理的粒度計算,將相關(guān)過程作合并處理,構(gòu)造碳排放目標(biāo)函數(shù)如下:

(18)

其中:CE為碳排放總量,Mci為第i類特征供應(yīng)企業(yè)所用設(shè)備的碳排放因子,mAbilityi為第i類特征供應(yīng)企業(yè)的單位時間生產(chǎn)能力,PM為加工數(shù)量。

3.1.2 約束處理

在工藝規(guī)劃中,受到工序排序規(guī)則的約束,各工藝工序任務(wù)間有優(yōu)先級關(guān)系,需要滿足先粗后精型約束關(guān)系、主次優(yōu)先型約束關(guān)系、基準優(yōu)先型約束關(guān)系、非破壞型約束關(guān)系4類特征約束關(guān)系。這些條件形成了特征間的優(yōu)先關(guān)系,在需求—特征圖譜中可將其表達,如圖3所示,MF6與MF7存在先后關(guān)系,MF6為MF7的先行特征,須先加工MF6后才可加工MF7;而MF3與MF5為并行關(guān)系,可不考慮優(yōu)先順序。

圖3 特征工藝間關(guān)系圖

特征之間的優(yōu)先關(guān)系可轉(zhuǎn)化為特征間約束矩陣CMij:

(19)

其中:CMij表示特征MFi與特征MFj之間的優(yōu)先關(guān)系,n為零件的總特征數(shù)。CMij根據(jù)4類特征約束關(guān)系中的規(guī)則取得,如下:

3.2 基于NSGA-Ⅲ算法的模型求解

面向服務(wù)的組合優(yōu)選規(guī)劃模型本質(zhì)是多目標(biāo)優(yōu)化問題,解決此類問題有多種方法,DEB等[26]提出第三代非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅲ),該算法在帶精英策略的非支配排序遺傳算法(NSGA-Ⅱ)基礎(chǔ)上,采用了基于參考點的選擇機制進行系統(tǒng)分析而選擇優(yōu)異解。NSGA-Ⅲ是針對高維多目標(biāo)優(yōu)化計算代價大,難以挑選Pareto解的情況而開發(fā)的,該應(yīng)用場景適用于本模型,因而本文采用該算法進行求解。為了將細粒度的服務(wù)優(yōu)選模型有效地融入算法中,本文提出一種基于特征粒度的制造資源排序編碼方式以及引入一類次候選集變異算子進行遺傳進化。

3.2.1 編碼方式

服務(wù)組合優(yōu)選問題屬于NP-hard問題,尤其是工藝規(guī)劃上還涉及到廣泛的約束問題,為將制造資源信息進行有效編碼以提高尋優(yōu)效率,本文提出一種基于特征粒度的制造資源排序混合編碼方式。該方式采取整數(shù)編碼和排序編碼組合的多染色體混合編碼,能夠完整地表達所選用的制造資源及工藝順序。

對于需求方所要求待加工的n個特征,本混合編碼方式將采用長度為2n的染色體。其中前半段是長度為n的排序型編碼染色體,表示各特征的工藝順序;后半段是長度為n的實數(shù)型編碼染色體,表示針對已排序的特征所分別選用的制造資源供應(yīng)企業(yè)ID序號。

如圖3中的8個待加工特征,編碼后的染色體可表達如圖4所示,其長度為16,前8個為特征的工藝順序,后8個為該順序下各特征選取的制造資源供應(yīng)企業(yè)ID序號。此染色體也可用二元組形式表達為{(1,5),(3,2),(4,4),(2,6),(6,3),(7,3),(5,7),(8,9)},意為特征MF1是第一個加工特征,其選用的供應(yīng)企業(yè)ID為5;MF3為第二個加工特征,其選用的供應(yīng)企業(yè)ID為2,以此類推。

圖4 面向制造資源排序的染色體混合編碼方式

3.2.2 次候選集變異算子

對于優(yōu)選模型的求解,核心是挑選出優(yōu)質(zhì)且物流服務(wù)組合便捷的供應(yīng)商。在一層選優(yōu)時形成了主候選集與次候選集,主候選集將作為初始染色體生成與進化的主體?？紤]到企業(yè)供應(yīng)能力的差異性與區(qū)域運輸物流的效益,如企業(yè)A在特征集服務(wù)MF1上的綜合評估分數(shù)Cs能夠達到前5%,而在特征集服務(wù)MF6上的Cs只能達到前30%,當(dāng)MF1與MF6間不存在斷層供應(yīng)商時,意味著兩類加工需求均能在企業(yè)A進行,此時可以在遺傳算法尋優(yōu)時以ε的概率將企業(yè)A作為MF6的一個次候選集變異算子引入進化過程,讓最終的求解結(jié)果有更好的適應(yīng)性。

使用次候選集變異算子產(chǎn)生變異的過程如圖5所示,預(yù)先設(shè)置變異概率Pm與次候選集選擇概率ε,對原始染色體的制造資源編碼部分進行變異操作,圖中為后8位編碼。

圖5 考慮次候選集的變異操作

變異實施過程為:

(1)對制造資源部分染色體的每一個基因以概率Pm指定其為變異點,如圖5中ID為“6”的基因在此次被選為變異點;

(2)該指定變異點將有1-ε的概率會在其基因的主候選集中產(chǎn)生變異,同時有ε的概率會在其次候選集中產(chǎn)生變異。

(3)若在主候選集中產(chǎn)生變異,則從其主候選集中選擇企業(yè)ID進行變異操作即可;若在其次候選集中產(chǎn)生,則需要先找到該基因的前一個基因,如圖5中的“4”,然后在基因為“6”的次候選集中尋找是否有ID為“4”的企業(yè),若有即可選擇ID“4”進行變異操作,否則保持原來的基因“6”。

3.2.3 求解過程

基于NSGA-Ⅲ算法的服務(wù)組合優(yōu)選模型求解如圖6所示,具體步驟如下:

圖6 NSGA-Ⅲ算法流程圖

步驟1初始化算法參數(shù),包括總迭代次數(shù)、交叉率Pc、變異率Pm、次候選集選擇概率ε等。

步驟2以主候選集空間初始化參考點和種群N,輸入約束條件。

步驟3對父代種群Pt,通過選擇、交叉、帶次候選集的變異操作產(chǎn)生子種群Qt,計算個體的適應(yīng)度,即PCn、TC、CE的函數(shù)值。

步驟4混合Pt和Qt得到一個新種群Rt,即Rt=Pt∪Qt,其規(guī)模為2N。對Rt進行非支配排序并劃分為不同層級的非支配解集合(F1,F2,F3,…,FL,…,FW)。

步驟6從St中選擇解產(chǎn)生下一代父種群Pt+1。若St的數(shù)量等于N,則Pt+1=St,否則,先將St中的集合(F1,F2,F3,…,FL-1)放入Pt+1,然后再從FL中根據(jù)基于參考點選擇機制選取其余解。

基于參考點的選擇方法為:首先找到種群St的理想點Z*=(PCn*,TC*,CE*),其中PCn*,TC*,CE*分別為種群St所有解中各目標(biāo)函數(shù)值的最小值,然后歸一化種群和參考點。通過計算St中的每個解到每條參考線的垂直距離,然后用最短的距離連接解與參考點,這樣就可以在FL中用一種新的小生境保護方法選擇個體。生境數(shù)ρj是F1到FL-1層中與第j個參考點相連的個體數(shù)。這種小生境技術(shù)是為了提高NSGA-Ⅲ的分布性,所以首先需要找到具有最小生境數(shù)ρj的參考點i,然后確定FL中有沒有個體與參考點i相連。若有個體與參考點i相連,則根據(jù)ρj的值選擇一個個體進入Pt+1;否則,此次迭代將不考慮這個參考點,而是用另外具有最小生境數(shù)的參考點重復(fù)上述操作,直到Pt+1的值等于N的值。

步驟7若滿足終止條件,則輸出最終的解,否則重復(fù)步驟2。

4 實例分析

為驗證在制造資源組織和服務(wù)組合優(yōu)選任務(wù)上本方案的可行性,以某新研發(fā)零件為例匹配相應(yīng)的生產(chǎn)企業(yè),執(zhí)行如下過程:

(1)面向特征級服務(wù)的一層優(yōu)選

該新研發(fā)零件共有9個特征需要進行外協(xié)加工,如圖7所示,圖中DI_new代表其需求數(shù)據(jù),包括{PMF(9),PM=500,TQ=230,CC=6.80,AD=(117.348347,38.970762)},即特征單元PMF,加工數(shù)量500、時間限額230 h、成本限額6.8萬元、需求方位置信息AD(117.348347,38.970762)。9個特征單元的從屬特性包括特征類型FT、尺寸特征SF、材料特征MC、精度特征AF、加工鏈PC、先行特征集PFs,為便于展示,圖中僅呈現(xiàn)MF9的相關(guān)屬性特征,特征單元MF1～MF8的特征類型FT依次為平面類、外圓類、凸起類、旋轉(zhuǎn)特征類、槽類、肋頂類、圓角類、臺階類。

圖7 案例的需求—特征圖譜

通過圖譜中特征間的優(yōu)先關(guān)系可得其約束矩陣為:

根據(jù)需求數(shù)據(jù)對供應(yīng)方進行信息匹配與質(zhì)量排序。本次實例名單共328家供應(yīng)商,每家可提供若干個特征加工服務(wù)。通過以特征的工藝需求進行匹配得到滿足特征MF1條件的企業(yè)有192家,MF2有107家,MF3有132家,MF4有190家,MF5有156家,MF6有171家,MF7有168家,MF8有134家,MF9有114家,特征下各企業(yè)的加工合格率PYF、滿意度評價值S、交付按時率TL和供應(yīng)偏好值Bias如表2所示。對4個指標(biāo)以變異系數(shù)法進行賦權(quán)求和得到特征下各企業(yè)綜合評估分數(shù)Cs,再以Cs進行排序得到表2中的結(jié)果。

表2 特征下各企業(yè)的指標(biāo)排序信息

將排序結(jié)果以優(yōu)選比α計算得到候選集,本文將主、次候選集對應(yīng)的α1、α2分別設(shè)為10%、30%。得到特征單元MF1下的主、次候選集分別為19個、38個,MF2下為11個、22個,MF3下為13個、26個,MF4下為19個、38個,MF5下為16個、32個,MF6下為17個、34個,MF7下為17個、34個,MF8下為13個、26個,MF9下為11個、22個。如表3所示為所得到的部分優(yōu)質(zhì)供應(yīng)商信息。

表3 主次候選集部分供應(yīng)企業(yè)信息

(2)資源服務(wù)組合的二層優(yōu)選

對所得到的企業(yè)制造資源候選集,依據(jù)建立的約束矩陣CM,以3.1節(jié)中的3個目標(biāo)函數(shù)為優(yōu)化目標(biāo),基于制造資源排序混合編碼方式進行染色體編碼,以次候選集變異算子執(zhí)行進化中的變異操作,在NSGA-Ⅲ算法下尋優(yōu)。

接下來將從算法求解結(jié)果解碼到實際方案的可行性、與其他算法對比解集的分布情況、多次實驗求解結(jié)果的穩(wěn)定性展開作分析。

1)結(jié)果可行性分析。

設(shè)置種群規(guī)模為175,交叉概率為0.9,變異概率為0.15,次候選集選擇概率為0.1,最大迭代次數(shù)300,以非支配排序計算得到Pareto解集。如圖8所示為該Pareto解集的示意圖,對Pareto解集以需求信息中的時間限額TQ230 h,成本限額CC6.8萬元進行過濾,取解集中第一條數(shù)據(jù)進行染色體解碼,對其所選擇的工藝順序與加工企業(yè)進行分析。

圖8 Pareto解集示意圖

如圖9所示,該結(jié)果解碼后的工藝流動順序為(1,3,4,2,6,7,5,8,9),由5個企業(yè)協(xié)作完成。其中,MF1由一家供應(yīng)商完成,MF3、MF4由同一供應(yīng)商完成,MF2、MF6、MF7由同一供應(yīng)商完成,MF5由一家供應(yīng)商完成,MF8、MF9由同一供應(yīng)商完成,且僅有MF2在其次候選集企業(yè)中進行加工,其余均在其主候選集中完成。可知,該結(jié)果滿足約束矩陣CM且供應(yīng)主體為主候選集。

圖9 計算結(jié)果解碼圖

為進一步校驗工藝的流動順序,對主、次候選集進行地址標(biāo)記,如圖10所示,將所選的5家供應(yīng)商以虛線框于圖中圈出,可以發(fā)現(xiàn)5家供應(yīng)商都聚集在同一小區(qū)域內(nèi)。對5家供應(yīng)商地點與需求方地點進行放大,如圖中所示,以箭頭標(biāo)記了工序的流動順序,可以發(fā)現(xiàn),從需求方地址開始,經(jīng)過5家供應(yīng)商后又回到需求方附近,形成了閉環(huán),進一步驗證了該結(jié)果在物流層面的可行性。

圖10 加工路線圖

2)與其他算法對比解集的分布情況。

為對比本文所提出的帶次候選集變異算子的NSGA-Ⅲ算法(簡寫為NSGA-Ⅲ-CS)在細粒度制造資源服務(wù)組合問題上的求解效果,特設(shè)置了對照實驗,分別為常規(guī)NSGA-Ⅲ算法、帶次候選集變異算子的NSGA-Ⅱ算法(簡寫為NSGA-Ⅱ-CS)、常規(guī)NSGA-Ⅱ算法。以1)中的實驗參數(shù)用上述4類算法進行計算求解,其中常規(guī)NSGA-Ⅲ算法與常規(guī)NSGA-Ⅱ算法無次候選集選擇概率。

將所得結(jié)果繪制箱線圖,如圖11所示。由圖中各算法的結(jié)果分布情況可以發(fā)現(xiàn),無論是在工藝費用、加工時間還是碳排放量上,NSGA-Ⅲ-CS的求解效果均優(yōu)于其他3類算法。此外,NSGA-Ⅱ算法在求解時存在少量異常值,在NSGA-Ⅱ同類算法對比中,NSGA-Ⅱ-CS算法的解分布會更優(yōu)于常規(guī)NSGA-Ⅱ算法。

圖11 算法對比箱線圖

3)多次實驗求解結(jié)果的穩(wěn)定性。

為驗證該算法求解的穩(wěn)定性,以1)中實驗參數(shù)對其運行10次。10次計算速度如圖12所示,對每次所得Pareto解集下的工藝費用、加工時間和碳排放量分別計算均值,得到了3個目標(biāo)下的10次結(jié)果,由圖中數(shù)據(jù)及趨勢可知,各目標(biāo)下的實驗結(jié)果波動較小,證明了該算法在應(yīng)用時具有一定的魯棒性。

圖12 10次實驗結(jié)果圖

因此,本文所提出的基于特征粒度的制造資源服務(wù)組合雙層優(yōu)選方法在應(yīng)用中能夠有效地匹配優(yōu)質(zhì)供應(yīng)商,同時最小化物流成本;在其中使用的帶次候選集變異算子的NSGA-Ⅲ算法較其他算法的優(yōu)化效果更好,且運行穩(wěn)定。

5 結(jié)束語

本文面向小批量定制產(chǎn)品,以區(qū)域云制造環(huán)境下的任務(wù)分配和資源組合優(yōu)化問題為研究重點,提出將零件的加工特征作為任務(wù)粒度進行資源匹配,并建立了需求信息描述模型、制造資源供應(yīng)信息模型。之后引入知識圖譜技術(shù),采用自頂向下設(shè)計,完成信息模型的本體化表達與模式層建立,構(gòu)建需求—特征圖譜、制造資源供應(yīng)圖譜,并以圖數(shù)據(jù)庫進行存儲。在優(yōu)選匹配時,聚焦需求,以需求任務(wù)發(fā)布階段、信息匹配篩選可用供應(yīng)資源階段、特征級服務(wù)排序優(yōu)選階段3個層次完成制造資源的一層優(yōu)選;將篩選后的優(yōu)質(zhì)供應(yīng)企業(yè)以工藝總成本、工藝總時間及總碳排放為優(yōu)化目標(biāo)建立目標(biāo)函數(shù),以特征間優(yōu)先級關(guān)系構(gòu)建約束矩陣,并基于本文提出的制造資源排序混合編碼方式對資源及工藝順序進行染色體編碼,最后通過帶次候選集變異算子的NSGA-Ⅲ算法對該多目標(biāo)優(yōu)化問題進行求解,實現(xiàn)二層優(yōu)選。

該方案適用于小批量定制產(chǎn)品的組合生產(chǎn)和企業(yè)請求外協(xié)加工時的協(xié)同生產(chǎn)等情形。通過實例分析驗證了該方法的可行性,同時與其他算法相比,本文所提出的帶次候選集變異算子的NSGA-Ⅲ算法能夠在求解時得到更好的優(yōu)化結(jié)果,多次運行的穩(wěn)定性較好,能夠在匹配優(yōu)質(zhì)供應(yīng)商的同時,最小化物流成本,為細粒度的資源服務(wù)組合問題提供一種可靠的解決方法。目前本文構(gòu)建的圖譜主要是用于供需數(shù)據(jù)的存儲與快速檢索,以及在匹配中關(guān)聯(lián)關(guān)系的實時查詢,下一步計劃將知識圖譜在推理與聚類推薦等方面的優(yōu)勢融入優(yōu)選方法中,使特征級服務(wù)的一層優(yōu)選能通過過濾和相似度匹配等算法更好地應(yīng)對大規(guī)模數(shù)據(jù)的需求,提升方法的求解效率。