定制件柔性工藝路線的車間調(diào)度優(yōu)化研究*

周 珂，呂 民，夏自祥,3，李小冬

(1.濟寧學院 機械工程系,山東 曲阜 273155;2.哈爾濱工業(yè)大學 機電工程學院,黑龍江 哈爾濱 150001;3.中國礦業(yè)大學 機電工程學院,江蘇 徐州 221116)

0 引 言

隨著我國智能制造水平不斷提升，定制化生產(chǎn)得以實現(xiàn)，定制化產(chǎn)品需求越來越旺盛[1]。在生產(chǎn)中，臨時件、加急件的存在經(jīng)常擾亂正在執(zhí)行的制造任務，定制產(chǎn)品的增多使得車間調(diào)度更加復雜。頻繁更換工件種類的調(diào)度方案在一定程度上降低了生產(chǎn)效率。在大規(guī)模生產(chǎn)和定制生產(chǎn)共存的環(huán)境下，如果定制產(chǎn)品只利用大規(guī)模生產(chǎn)排產(chǎn)后的設備空閑時間進行加工，將會延長定制品的市場響應周期，降低產(chǎn)品的市場競爭力。

在大規(guī)模生產(chǎn)環(huán)境下，機械產(chǎn)品的工藝設計主要考慮采用哪種工藝能夠保證制造精度，以當前的生產(chǎn)批量使用哪些設備能夠達到成本最低的目的。在能夠滿足精度要求的前提下選擇制造成本最低的設備，制訂工藝路線，編制工藝卡片，并據(jù)此進行車間調(diào)度，組織生產(chǎn)。

在智能制造環(huán)境下，定制產(chǎn)品比非定制產(chǎn)品的利潤高，與成本相比，市場響應能力是企業(yè)爭取訂單的關鍵。因此，定制化產(chǎn)品工藝設計的目的，是在保證制造精度和其他產(chǎn)品工期的基礎上，充分利用現(xiàn)有設備和各種工藝方案，盡量縮短定制產(chǎn)品工期。不同加工方法和加工設備對應不同的工藝路線，而工藝路線直接影響車間調(diào)度。由于制訂工藝路線時只參考了設備空閑率，可能導致無法同時滿足定制品和非定制品交貨期。因此，需要將工藝路線和車間調(diào)度同時考慮進行制造過程優(yōu)化。

近年來，國內(nèi)外很多學者對車間調(diào)度優(yōu)化進行了研究；張浩[2]采用改進型啟發(fā)式搜索算法對板材長度可變的二維矩形排樣優(yōu)化問題展開研究，采用基于疊板數(shù)分層的多叉樹遞歸搜索算法解決了考慮疊板組批的切割與排樣協(xié)同優(yōu)化問題；胡東方等[3]利用改進的信息熵免疫算法對復雜產(chǎn)品定制設計的柔性化和智能化展開了研究；潘瑞林等[4]針對冷軋企業(yè)大批量生產(chǎn)模式與多品種、小批量的市場需求之間存在的矛盾，構建了基于改進粒子群的模糊聚類算法并進行求解；趙桂芝等[5]采用改進免疫克隆算法對農(nóng)機轉向器生產(chǎn)車間對突發(fā)事件調(diào)度不及時及車間調(diào)度問題進行了研究；湯洪濤等[6]采用了混合布谷鳥搜索求解算法對不確定的動態(tài)事件干擾混流生產(chǎn)車間預先調(diào)度實施的問題進行了研究；解瀟晗等[7]采用目標加權法對柔性作業(yè)車間低能耗調(diào)度問題展開了研究，并在MATLAB中對生產(chǎn)實例進行了仿真；魯宏浩等[8]利用分布估計—蟻群混合算法對柔性作業(yè)車間調(diào)度問題及其優(yōu)化方法進行了研究；張源等[9]利用改進差分進化算法對于混合流水車間調(diào)度問題進行了研究；Chaudhry I A等[10]對一般柔性作業(yè)車間調(diào)度的算法進行了綜述。

在以上研究中，前提條件是工序已知且加工順序固定，而定制件存在柔性工藝路線。因此，在當前大規(guī)模生產(chǎn)和定制生產(chǎn)并存的環(huán)境下，迫切需要一種考慮定制件柔性工藝路線的車間調(diào)度優(yōu)化方法。

筆者針對定制件生產(chǎn)周期長難以排產(chǎn)的問題，建立柔性工藝路線車間調(diào)度數(shù)學模型。

1 問題描述

筆者建立考慮定制件柔性工藝路線的車間調(diào)度數(shù)學模型，其符號及說明如表1所示。

表1 符號及說明

考慮定制件柔性工藝路線的車間調(diào)度問題可描述為：車間中存在N個待加工非定制工件PN={PNi|i=1,2,…,N}，M個待加工定制工件PC={PCi|i=1,2,…,M}，L臺可用加工設備M={Ml|l=1,2,…,L}。

工件Pi(i=1,2,…,N+M)的加工過程由Ni個工序PPi1,PPi2,…,PPiNi組成，其中，非定制件的工藝路線固定(即工序及其順序固定)，定制件的工藝路線存在柔性(即定制件的工序存在若干種不同方案)，工序PPij可在{Mk|k=1,2,…,K}中任何一臺設備上完成(K為能夠完成工序PPij的設備總數(shù))。工序PPij的加工等待時間為TWij，使用設備Ml時工序PPij加工時間為TMijl，工序PPi(j-1)至工序PPij的運輸時間為TTij，工序PPij加工前的裝夾時間為TAij，工序PPij加工結束的拆卸時間為TDij。設備Ml單位時間能耗為ECl。工件Pi(i=1,2,…,N+M)的工序須符合工藝路線要求，即PPi1→PPi2→…→PPiJ。

另外，工件在同一時刻只有一臺設備對其加工，設備同一時刻只能加工一個工件，即：加工過程須滿足不可中斷約束、工件唯一性約束和設備唯一性約束：

(1)工件Pi(i=1,2,…,N+M)的工序PPij，可在預先給定的設備集{Mk|k=1,2,…,K}的任一臺設備上加工，且?PPij，使|Mij|>1；

(2)每個工件Pi(i=1,2,…,N+M)的工序須符合當前工藝路線要求，即PPi1→PPi2→…→PPiJ；

(3)工件的工藝路徑多樣(不同工件的工藝路線可能相同或不同)，即?Pk,Pj(k≠j),l，使得Mkl≠Mjl；

(4)工件不可重入，即對?PPij,PPik(j≠k)，Mij∩Mik=φ。

2 數(shù)學模型

求解考慮定制件柔性工藝路線的車間調(diào)度問題，即是在滿足非定制件工期的約束條件下，確定定制件的工藝路線，安排全部工件的每道工序的加工設備及加工順序，以達到最小化定制件完工時間Tmax、能耗EC和成本C的目的，具體為：

(1)

Tmax=max{Ti|i=1,2,…,M}

(2)

(3)

(4)

式中：Ti—第i個工件的完工時間；M—定制件包括的工件數(shù)量；TMl—第l臺加工設備Ml的總加工時間。

本文的調(diào)度優(yōu)化目標是定制件的完工時間短、總能耗和總成本低，目標函數(shù)為：

minf=min(Tmax+EC+C)

(5)

約束條件是滿足非定制件工期要求，約束表達為：

Ti≤DLi(i=1,2,…,N)

(6)

在考慮定制件柔性工藝路線的車間調(diào)度問題中，存在3個決策過程：(1)確定定制件的工藝路線，即加工工序及順序；(2)按照當前的工藝路線將全部工件(包括定制件和非定制件)對應的工序，分配給具備加工能力的設備(即Mij={Mk|Mij=k=1,2,…,K}中的某臺機床設備)進行加工；(3)確定設備Ml(l=1,2,…,L)上相應工序Pij的加工順序。

3 分層協(xié)同進化算法設計

針對考慮定制件柔性工藝路線的車間調(diào)度問題，本文設計了分層協(xié)同進化算法，將確定定制件的工藝路線作為第一層，將按照當前定制件工藝路線分配加工設備并安排加工順序作為第二層，協(xié)同迭代進行求解。

分層協(xié)同進化算法流程如圖1所示。

圖1 分層協(xié)同進化算法流程

采用二元組(i,)對第一層染色體進行編碼，進入第二層優(yōu)化時，采用第一層當代(i,)組成三元組(i,,)對第二層染色體進行編碼；三元組(i,,)表示第i個工件的第j個工序i，安排在機器k上加工，基因從左到右的排列順序表示全部工序的加工順序。因此，第二層優(yōu)化中每條染色體都是由所有工序組成的一個有序序列，染色體的長度等于全部工件的工序總數(shù)。

在迭代中，筆者采用POX交叉算子進行交叉來保證工件出現(xiàn)的次數(shù)和工序之間的順序約束關系[11]。其具體步驟為：

步驟1：初始化算法參數(shù)。進化代數(shù)g=0，h=0?；诙ㄖ萍庸r間反向搜索生成第一層初始種群，PL=PL(0)，J(0)=J1+J2+…+JN+M，J=J(0)；

步驟2：染色體長度LL(g)=J，基于負載均衡生成第二層初始種群；

步驟3：計算種群個體適應度值f；

步驟4：判斷是否滿足終止條件1，若滿足則執(zhí)行步驟10，若不滿足則執(zhí)行步驟5；

步驟5：選擇第二層進化種群染色體中的兩個父代個體生成差分矢量，選擇另一個體與差分矢量求和生成實驗個體；

步驟6：解碼實驗個體，判斷生成的調(diào)度方案是否有效。若方案有效，則進入步驟8；若方案無效，則進入步驟7進行實驗個體修正；

步驟7：修正無效方案對應的實驗個體，檢查并修正：數(shù)量大于N+M或存在重復工件編號的個體；解碼后Mij?{Mk|k=1,2,…,K}的個體；設備編號數(shù)量大于L的個體等；

步驟8：父代個體與實驗個體交叉生成新個體；

步驟9：基于適應度選擇個體；第二層進化代數(shù)h加1，返回步驟3；

步驟10：判斷第一層進化代數(shù)是否為0，若為0則用0代f最小值為f賦值f=f(0)；若不為0則將g代f最小值(minf(g))與當前f值比較，并取其中更小者保留在f中；

步驟11：判斷是否滿足終止條件2，若滿足則輸出工藝路線及調(diào)度方案，若不滿足則g=g+1，h=0，PL=PL(g)，J=J(g)，執(zhí)行步驟2。

4 實例驗證及分析

某工業(yè)集團25車間中共有正常排產(chǎn)的10批非定制工件和新加入排產(chǎn)的2批定制工件，涉及11臺可用設備。

實例中涉及的非定制件部分工序如表2所示。

實例中涉及的定制件部分工序如表3所示。

表2 非定制件部分工序

表3 定制件部分工序

定制件生產(chǎn)任務下達前，原非定制件調(diào)度方案如圖2所示。

圖2 原非定制件調(diào)度方案

定制件生產(chǎn)任務下達后，將所有工件生產(chǎn)任務合并。非定制件優(yōu)先的調(diào)度方案如圖3所示。

圖3 非定制件優(yōu)先的調(diào)度方案

定制件優(yōu)先且不考慮柔性工藝路線的調(diào)度方案如圖4所示。

圖4 定制件優(yōu)先且不考慮柔性工藝路線的調(diào)度方案

在滿足非定制件工期約束下，以最小化定制件完工時間、總能耗、總成本為目標，考慮柔性工藝路線的工件調(diào)度方案如圖5所示。

圖5 考慮柔性工藝路線的工件調(diào)度方案

在定制件優(yōu)先，且不考慮柔性工藝路線的調(diào)度方案中，工件1～10總完工時間為136 d，定制件11、12合計完工時間為30 d，全部工件總完工時間為166 d；

在定制件優(yōu)先，且考慮柔性工藝路線的調(diào)度方案中，工件1～10總完工時間為133 d，定制件11、12合計完工時間為14 d，全部工件總完工時間為147 d。

對比兩種方案發(fā)現(xiàn)：考慮定制件柔性工藝路線的調(diào)度方案，在滿足非定制件工期約束的前提下，定制件完工時間縮短了53%。

5 結束語

本文建立的考慮定制件柔性工藝路線的車間調(diào)度數(shù)學模型，描述了包含可變工藝路線的定制件的車間調(diào)度問題。實例驗證表明，文中設計的分層協(xié)同進化算法，求解考慮定制件柔性工藝路線的車間調(diào)度問題可行且有效；對比不同方案發(fā)現(xiàn)，考慮定制件柔性工藝路線的調(diào)度方案，在滿足非定制件工期約束的前提下，能夠更加快速地完成定制件訂單，提高定制件的市場響應速度，提升產(chǎn)品市場競爭力。

從優(yōu)化后的方案可以看出，要進一步縮短生產(chǎn)周期，需要對批量較大的工件批次進行合理分解，下一步研究中，筆者將根據(jù)瓶頸設備集優(yōu)化工件批次，建立考慮柔性加工批次和工藝路線的調(diào)度模型進行優(yōu)化。