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

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

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

0 引 言

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

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

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

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

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

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

1 問題描述

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

表1 符號及說明

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

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

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

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

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

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

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

2 數(shù)學(xué)模型

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

(1)

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

(2)

(3)

(4)

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

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

minf=min(Tmax+EC+C)

(5)

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

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

(6)

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

3 分層協(xié)同進(jìn)化算法設(shè)計(jì)

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

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

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

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

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

步驟1：初始化算法參數(shù)。進(jìn)化代數(shù)g=0，h=0。基于定制件加工時(shí)間反向搜索生成第一層初始種群，PL=PL(0)，J(0)=J1+J2+…+JN+M，J=J(0)；

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

步驟3：計(jì)算種群個(gè)體適應(yīng)度值f；

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

步驟5：選擇第二層進(jìn)化種群染色體中的兩個(gè)父代個(gè)體生成差分矢量，選擇另一個(gè)體與差分矢量求和生成實(shí)驗(yàn)個(gè)體；

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

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

步驟8：父代個(gè)體與實(shí)驗(yàn)個(gè)體交叉生成新個(gè)體；

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

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

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

4 實(shí)例驗(yàn)證及分析

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

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

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

表2 非定制件部分工序

表3 定制件部分工序

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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