考慮多時(shí)間因素的綠色柔性作業(yè)車間動(dòng)態(tài)調(diào)度*

衛(wèi)少鵬，王 婷，2，周 彤

(1.貴州大學(xué)管理學(xué)院，貴陽(yáng) 550025；2.貴州省互聯(lián)網(wǎng)+協(xié)同智能制造重點(diǎn)實(shí)驗(yàn)室，貴陽(yáng) 550025)

0 引言

隨著精益生產(chǎn)的盛行，制造業(yè)在生產(chǎn)過(guò)程中對(duì)質(zhì)檢的應(yīng)用越來(lái)越廣泛。為了減少殘次品的數(shù)量，綠色柔性作業(yè)車間調(diào)度需要對(duì)關(guān)鍵工件的特殊工序穿插質(zhì)檢環(huán)節(jié)。質(zhì)檢環(huán)節(jié)使得緊鄰工序間隙較大，造成機(jī)器空轉(zhuǎn)能耗較高，尤其是返修、報(bào)廢等問(wèn)題的存在，嚴(yán)重影響了生產(chǎn)過(guò)程的流暢性，極大擾動(dòng)了原始生產(chǎn)計(jì)劃。綠色動(dòng)態(tài)車間調(diào)度基于事件驅(qū)動(dòng)的重調(diào)度策略，通過(guò)重新調(diào)整工件的加工順序，同時(shí)匹配高效率、低能耗的加工機(jī)器，從而達(dá)到節(jié)能減排、按時(shí)交貨的雙重目標(biāo)。

當(dāng)前，國(guó)內(nèi)外學(xué)者對(duì)柔性作業(yè)車間動(dòng)態(tài)調(diào)度的研究成果較為豐富。Nouiri M等[1]針對(duì)機(jī)器故障問(wèn)題提出了一種動(dòng)態(tài)節(jié)能調(diào)度；張守京等[2]針對(duì)重調(diào)度問(wèn)題提出了免疫度概念；成榮榮等[3]基于完工時(shí)間和總成本指標(biāo)進(jìn)行建模，分別對(duì)4類動(dòng)態(tài)事件設(shè)計(jì)了重調(diào)度策略；孫麗珍等[4]針對(duì)工件批量加入和機(jī)器故障問(wèn)題的重調(diào)度問(wèn)題采取了改進(jìn)的遺傳算法進(jìn)行求解；Liu B等[5]設(shè)計(jì)了一種快速分布估計(jì)算法帶有模糊時(shí)間的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問(wèn)題；李聰波等[6]建立了多目標(biāo)重調(diào)度節(jié)能優(yōu)化模型，引入多目標(biāo)引力搜索算法進(jìn)行求解；王雷等[7]引入了可變重調(diào)度區(qū)間策略，避免了重調(diào)度和原調(diào)度方案差別過(guò)大；陳超等[8]提出了一種退火遺傳算法求解動(dòng)態(tài)節(jié)能調(diào)度問(wèn)題；劉燚等[9]將事件驅(qū)動(dòng)策略和滾動(dòng)窗口技術(shù)應(yīng)用于動(dòng)態(tài)調(diào)度問(wèn)題。

綜上所述，以往的動(dòng)態(tài)調(diào)度研究?jī)H關(guān)注加工環(huán)節(jié)的相關(guān)指標(biāo)優(yōu)化，較少考慮到輔助加工時(shí)間的影響，如：調(diào)整時(shí)間、質(zhì)檢時(shí)間。輔助環(huán)節(jié)對(duì)生產(chǎn)系統(tǒng)的效率和能耗均有較大影響，探明其影響機(jī)理極其重要。鑒于此，以下動(dòng)態(tài)車間調(diào)度選取最大完工時(shí)間和機(jī)器總能耗為優(yōu)化指標(biāo)，同時(shí)考慮機(jī)床輔助環(huán)節(jié)的調(diào)整時(shí)間和質(zhì)檢時(shí)間，建立了綠色動(dòng)態(tài)車間調(diào)度模型，用線性加權(quán)法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)。采用新型群體智能算法—頭腦風(fēng)暴算法進(jìn)行求解，對(duì)編碼環(huán)節(jié)進(jìn)行改進(jìn)，引進(jìn)了轉(zhuǎn)換機(jī)制，設(shè)計(jì)了多層編碼方式，有效提高了最優(yōu)解的收斂速度和精度。

1 問(wèn)題描述與數(shù)學(xué)建模

1.1 問(wèn)題描述

考慮多時(shí)間因素的柔性作業(yè)車間綠色動(dòng)態(tài)調(diào)度描述如下：假設(shè)n個(gè)工件在m臺(tái)機(jī)器上加工，每個(gè)工件有h道工序，所有工序按照固定的工藝路線在柔性機(jī)器上完成操作。其中，所有工序Ojh在加工之前要考慮調(diào)整時(shí)間，部分關(guān)鍵工序在加工前要同時(shí)考慮調(diào)整時(shí)間和質(zhì)檢時(shí)間。

在生產(chǎn)過(guò)程中，機(jī)器的能耗可以分為兩部分：加工能耗和等待能耗。加工能耗指的是機(jī)器在加工各道工序時(shí)產(chǎn)生的必要能耗；等待能耗指的是機(jī)器處于調(diào)整時(shí)間、質(zhì)檢時(shí)間以及空閑時(shí)間時(shí)產(chǎn)生的非必要能耗，這部分能耗在保證工藝質(zhì)量的前提下，應(yīng)盡可能減少。結(jié)合實(shí)際情況，質(zhì)檢過(guò)程處理結(jié)果分為兩種：合格和返修。若該工序的質(zhì)檢結(jié)果為合格，則直接進(jìn)入下一道工序的加工；若結(jié)果為返修，則需要返回到有問(wèn)題的指定工序進(jìn)行加工，再以指定工序?yàn)槠鹗脊ば蛑敝镣瓿杉庸と蝿?wù)。此外，調(diào)度過(guò)程需滿足以下假設(shè)條件：①所有工件均可在0時(shí)刻進(jìn)行加工；②每臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；③所有工序一旦開始就不能中止；④同一工件的加工工序分先后順序；⑤質(zhì)檢時(shí)間和調(diào)整時(shí)間之間不分先后順序，可以同時(shí)并行；⑥不考慮機(jī)器故障問(wèn)題。圖1為不考慮質(zhì)檢擾動(dòng)的原始調(diào)度甘特圖。

圖1 未考慮質(zhì)檢時(shí)間的動(dòng)態(tài)調(diào)度甘特圖

考慮質(zhì)檢擾動(dòng)的重調(diào)度甘特圖如圖2所示。

圖2 考慮質(zhì)檢時(shí)間的動(dòng)態(tài)調(diào)度甘特圖

圖中紅色方格和綠色方格表示質(zhì)檢工序的時(shí)間，紅色方格表示工件的工藝加工質(zhì)量不達(dá)標(biāo)，需重新加工；綠色方格表示檢驗(yàn)合格，直接加工下一道工序。調(diào)整時(shí)間和質(zhì)檢時(shí)間不分先后，可同時(shí)進(jìn)行。

1.2 能耗模型

(1)加工能耗：機(jī)器對(duì)工件進(jìn)行車、銑、磨等工藝加工時(shí)，所消耗的能量。這部分能耗可通過(guò)二次多項(xiàng)式擬合曲線求得，公式為：

(1)

式中，E1為加工能耗；α1、α2是二次多項(xiàng)式的擬合曲線系數(shù)；xijh為0-1變量；Ym1為機(jī)器加工功率；m為機(jī)器總數(shù)；Pijh為第j個(gè)工件的第h道工序在機(jī)器i上加工時(shí)間。

(2)空轉(zhuǎn)能耗：機(jī)器在等待加工的過(guò)程中消耗的能量，包括：工件等待時(shí)間、機(jī)器調(diào)整時(shí)間、工件質(zhì)檢時(shí)間，公式為：

(2)

式中，E2為空轉(zhuǎn)能耗；xijh為0-1變量；Ym2為機(jī)器空轉(zhuǎn)功率；Cjh為第j個(gè)工件的第h道工序加工完成時(shí)間。

綜上所述，能夠得到所有機(jī)器的綜合能量消耗表達(dá)式為：

(3)

式中，E為機(jī)床總能耗。

1.3 綠色動(dòng)態(tài)調(diào)度模型

綠色柔性作業(yè)車間動(dòng)態(tài)調(diào)度模型，同時(shí)兼顧經(jīng)濟(jì)指標(biāo)和綠色指標(biāo)，即最大完工時(shí)間和機(jī)器總能耗。模型函數(shù)和約束條件為：

(4)

式中，Cmax為最大完工時(shí)間。其中，Cmax=min(max(Cj))為最大完工時(shí)間的計(jì)算公式。約束條件為：

Hijh=Cj(h-1)+Vijh

(5)

式中，Hijh為工件j的第h道工序在機(jī)器i上的允許開始加工時(shí)間；Vijh為工件j的第h道工序在機(jī)器i上的調(diào)整時(shí)間。

Hijk=Cj(k-1)+Rijh

(6)

式中，Rij為工件j的第h道工序在機(jī)器i上的質(zhì)檢時(shí)間。

Hijh′=max(Hijh,Hijk)

(7)

式中，Hijh′為工件j的第h道工序在機(jī)器i上的實(shí)際開始加工時(shí)間。

Cjh=Hijh′+Pijh

(8)

式中，Cjh為工件j的第h道工序的完工時(shí)間

(9)

式中，mjh為第j個(gè)工件的第h道工序的可選加工機(jī)器數(shù)；xijh為0-1變量。

式(5)表示調(diào)整時(shí)間約束；式 (6)質(zhì)檢時(shí)間約束；式(7)表示質(zhì)檢時(shí)間與機(jī)器調(diào)整時(shí)間中的較大者；式(8)表示同一時(shí)刻同臺(tái)機(jī)器只能加工一道工序；式(9)屬于機(jī)器約束，表示同一時(shí)刻同一道工序能且只能被一臺(tái)機(jī)器加工。

多目標(biāo)優(yōu)化模型的求解大致可分為兩類：加權(quán)優(yōu)化模型和帕累托優(yōu)化模型。為了便于決策者調(diào)節(jié)指標(biāo)權(quán)重，尋找更有針對(duì)性的調(diào)度方案，選取加權(quán)優(yōu)化模型進(jìn)行求解。采用加權(quán)歸一的方式，將多個(gè)目標(biāo)的量綱進(jìn)行統(tǒng)一，式(4)可進(jìn)一步描述為：

(10)

2 頭腦風(fēng)暴算法

頭腦風(fēng)暴算法是一種模擬人類群體決策過(guò)程的群體智能優(yōu)化算法。采用文獻(xiàn)[10]的頭腦風(fēng)暴算法流程框架，在單目標(biāo)算法的基礎(chǔ)上引進(jìn)能耗指標(biāo)，設(shè)計(jì)了多目標(biāo)頭腦風(fēng)暴優(yōu)化算法。通過(guò)k-means聚類方法，不斷把解集里的較好解挑選出來(lái)并聚集在一個(gè)較小的解空間里，提高了全局搜索能力；在舊解的基礎(chǔ)上產(chǎn)生新解的迭代方式保證了種群的多樣性，增強(qiáng)了局部搜索能力。

2.1 編碼

編碼是頭腦風(fēng)暴算法的關(guān)鍵環(huán)節(jié)，能夠保證算法的收斂速度。為了避免單一編碼方式導(dǎo)致解的表達(dá)不清楚，采用文獻(xiàn)[11]設(shè)計(jì)的多層編碼方式。每個(gè)個(gè)體分為兩層{工序?qū)覵 ,機(jī)器層M }，采用整數(shù)編碼方式。如：{31232 / 31213}，工序?qū)訑?shù)字代表工件編號(hào)，數(shù)字重復(fù)出現(xiàn)的次數(shù)表示工件的某道工序，即第4位的3表示工件3的第二道工序；機(jī)器層數(shù)字代表機(jī)器編號(hào)。

2.2 重調(diào)度種群初始化

為了提高初始化種群的質(zhì)量，依據(jù)種群個(gè)體的位置矢量向工序排序轉(zhuǎn)換。首先，得到隨機(jī)排序的工序?qū)蛹蟂0的位置矢量，按照位置矢量大小重排后，得到優(yōu)化后的集合S。

表1 個(gè)體位置矢量向工序排序轉(zhuǎn)換

由表2可知：解碼后的工序優(yōu)先度為O21→O31→O32→O11→O22。

(2)機(jī)器層編碼方案

機(jī)器層編碼為工序指派機(jī)器的集合M，其基因是工序所選擇的可用機(jī)器。首先，得到隨機(jī)指派集合M0的位置矢量，若位置矢量是整數(shù)則為有效編碼，即為指派機(jī)器編碼；否則屬于無(wú)效編碼，對(duì)位置矢量的大小向下取整，待指派的機(jī)器集合M。個(gè)體位置矢量向指派機(jī)器轉(zhuǎn)換如表2所示。

表2 個(gè)體位置矢量向指派機(jī)器轉(zhuǎn)換

最后，將編碼工序?qū)雍蜋C(jī)器層編碼組合在一起，表示優(yōu)化后的1個(gè)可行解: {31 232 / 31 213}。為了避免非法染色體的產(chǎn)生，第2層編碼對(duì)應(yīng)指派工序的機(jī)器為該工序的“第幾個(gè)”可用機(jī)器，而不是全部機(jī)器。

2.3 適應(yīng)度函數(shù)

在頭腦風(fēng)暴算法迭代的過(guò)程中，適應(yīng)度值越高，被保留的概率就越大。以下研究的適應(yīng)度函數(shù)設(shè)置為式(10)。

2.4 BSO解的分類和聚類

BSO的聚類過(guò)程是決定優(yōu)化效果的關(guān)鍵步驟，主要作用是將不同的個(gè)體分類，讓相似個(gè)體處于同一個(gè)類中。由于k-means聚類算法具有運(yùn)算速度快、簡(jiǎn)單等優(yōu)點(diǎn)，故采用k-means不斷把較好解挑選出來(lái)，并聚集在一個(gè)較小的解空間里。

BSO的分類操作是基于已有的舊解來(lái)產(chǎn)生新解。分類操作采用高斯變異方式：

(11)

其中，w1+w2+wn=1。

(12)

式中，T為最大迭代數(shù)；t為當(dāng)前迭代數(shù)；k為控制搜索步長(zhǎng)的調(diào)整系數(shù)，作用是平衡算法的收斂速度；rand()為隨機(jī)函數(shù)。

2.5 算法測(cè)試

為了驗(yàn)證算法的性能，選取3個(gè)標(biāo)桿案例[12-14]中的算法與當(dāng)前算法進(jìn)行對(duì)比，指標(biāo)選取最大完工時(shí)間，參數(shù)設(shè)置和標(biāo)桿文獻(xiàn)相同。標(biāo)桿文獻(xiàn)的算例規(guī)模分別為：6×6、8×6、10×6，結(jié)果如表3所示。

表3 不同規(guī)模問(wèn)題的算法對(duì)比

從表中可以看出，IBSO算法的收斂速度和精度均優(yōu)于其他算法，驗(yàn)證了算法的可行性和高效性。在6×6的實(shí)例中，IBSO稍稍優(yōu)于CE-MOFJSP；在8×6的實(shí)例中，IBSO算法的性能最大提高了18.3%，且迭代次數(shù)遠(yuǎn)遠(yuǎn)低于標(biāo)桿文獻(xiàn)的迭代次數(shù)，優(yōu)化效果最為明顯；在10×6的實(shí)例中，性能也提高了14.5%。

3 實(shí)驗(yàn)與結(jié)果分析

用Matlab2018a軟件進(jìn)行程序編譯，實(shí)驗(yàn)環(huán)境配置如下：Intel Core i5-4210 2.6GHz CPU、4.00RAM、Windows 10 64位操作系統(tǒng)。參數(shù)設(shè)置為：終止迭代數(shù)500；種群規(guī)模50；Pclustering=0.8;Pgenetation=0.2。為了衡量原始調(diào)度和重調(diào)度的偏離度，采用相對(duì)偏差來(lái)表示原始調(diào)度和重調(diào)度間的完工時(shí)間和能耗偏差，公式如下：

(13)

(14)

因?yàn)楫?dāng)前沒(méi)有綠色柔性作業(yè)車間動(dòng)態(tài)調(diào)度的標(biāo)準(zhǔn)實(shí)例，所以機(jī)器的加工數(shù)據(jù)采用來(lái)自文獻(xiàn)[15]的10×10測(cè)試數(shù)據(jù)，而測(cè)試數(shù)據(jù)不包含調(diào)整時(shí)間，將工序?qū)?yīng)的調(diào)整時(shí)間設(shè)定為不超過(guò)4的隨機(jī)數(shù)，質(zhì)檢時(shí)間和擾動(dòng)工序?yàn)殡S機(jī)生成。機(jī)器能耗的設(shè)置參考文獻(xiàn)[16] ，機(jī)器的額定功率和空載功率設(shè)置如表4所示。

表4 所有機(jī)器的加工功率 (kW)

算例為10個(gè)工件在10臺(tái)機(jī)器上加工，共有30道工序。需要質(zhì)檢的工序?yàn)椋?-1、3-1、4-1、6-1，對(duì)應(yīng)的質(zhì)檢時(shí)間為：4.8 min、5 min、6.3 min、5.5 min。質(zhì)檢時(shí)間是固定的，不隨機(jī)器的不同而改變。運(yùn)算結(jié)果如表5所示。

表5 數(shù)值計(jì)算結(jié)果

從表5可以看出，完工時(shí)間指標(biāo)和能耗指標(biāo)是互斥的。原始調(diào)度和重調(diào)度方案隨著α值的升高，完工時(shí)間逐漸縮短，而能耗不斷增加。根據(jù)指標(biāo)權(quán)重的特點(diǎn)將生產(chǎn)模式分為三類，便于企業(yè)決策者挑選適合的最優(yōu)解。

為了反映重調(diào)度和原始調(diào)度的偏差變化情況，繪制了完工時(shí)間和能耗的偏差變化趨勢(shì)，如圖3所示。

圖3 完工時(shí)間和能耗的偏差變化趨勢(shì)

從圖3可知，隨著完工時(shí)間指標(biāo)權(quán)重的增大，RT1直線的波動(dòng)較小。這是因?yàn)樵颊{(diào)度和重調(diào)度完工時(shí)間的偏差值始終穩(wěn)定在8附近，帶入完工時(shí)間偏差式(13)后，結(jié)果變化不大；RT2直線波動(dòng)較大，由最大值0.45降至0.2，能耗擾動(dòng)偏差降低了55.6%。由于重調(diào)度方案的加工工序變多，必要的等待能耗和加工能耗增大，致使算法的搜索迭代空間更大，能耗結(jié)果的分布更加離散。隨著能耗指標(biāo)的增大，搜索強(qiáng)度提高，使得能耗偏差逐漸縮小至一定范圍內(nèi)。圖4為原始調(diào)度和重調(diào)度的最優(yōu)前沿分布圖。

圖4 原始調(diào)度和重調(diào)度的最優(yōu)前沿分布

由圖4可以看出原始調(diào)度和重調(diào)度的帕累托解均勻、全面地分布在最優(yōu)前沿上，驗(yàn)證了算法和模型的有效性和可行性。原始調(diào)度方案和對(duì)應(yīng)的重調(diào)度方案，其完工時(shí)間偏差值和能耗偏差值較為穩(wěn)定，表明基于以上模型和算法的調(diào)度方案可有效將質(zhì)檢工序帶來(lái)的完工時(shí)間擾動(dòng)和能耗擾動(dòng)控制在一定范圍內(nèi)，保障了生產(chǎn)過(guò)程的穩(wěn)定性和高效性。由于篇幅有限，僅展示重調(diào)度之后的甘特圖。

根據(jù)企業(yè)面臨的實(shí)際情景，以速度為導(dǎo)向規(guī)則的重調(diào)度甘特圖如圖5所示，完工時(shí)間為28.2 min，能耗為1 064 kJ。

圖5 速度導(dǎo)向下的重調(diào)度甘特圖

圖中，紅色和綠色方格表示質(zhì)檢時(shí)間，紅色表示需要返工，綠色表示質(zhì)檢合格；質(zhì)檢時(shí)間上方的條紋方格，表示調(diào)整時(shí)間，且調(diào)整操作和質(zhì)檢操作可以同時(shí)進(jìn)行。黑色方格表示工件返工后被重新調(diào)度后所進(jìn)行的安排。從圖中可以看出，所有工序在各機(jī)床的分配較為均勻，機(jī)器負(fù)載也更為合理。

不同模式下的原始調(diào)度方案不同，故對(duì)應(yīng)的重調(diào)度方案也不同。當(dāng)企業(yè)需要推行綠色生產(chǎn)，則以能耗為導(dǎo)向規(guī)則進(jìn)行重調(diào)度，甘特圖如圖6所示，完工時(shí)間為44 min，能耗為859 kJ。

圖6 能耗導(dǎo)向下的重調(diào)度甘特圖

圖中，機(jī)器3、6、9承擔(dān)了較多的加工任務(wù)，且每道工序的加工時(shí)間也較長(zhǎng)。通過(guò)分析機(jī)器的加工特性可知，機(jī)器3、6、9的節(jié)能屬性較好，加工功率較低，故工件都傾向于流向這幾臺(tái)機(jī)器。機(jī)器8在加工各工件的功率只有3 kJ，而流向該機(jī)器的只有工序3-1，這是由于機(jī)器8的整體加工時(shí)間過(guò)長(zhǎng)，限制了更多的工序流向該機(jī)器。

兩種規(guī)則導(dǎo)向所產(chǎn)生的實(shí)際效應(yīng)差異較大。速度相差15.8 min，速度導(dǎo)向下的調(diào)度方案速度提高了35.9%；能耗相差205 kJ,能耗導(dǎo)向下的調(diào)度方案可以節(jié)省能耗19.3%。企業(yè)決策者根據(jù)生產(chǎn)的實(shí)際需要，可靈活選擇不同的方案，保障企業(yè)效益最大化。

4 結(jié)論

以綠色柔性作業(yè)車間為研究對(duì)象，針對(duì)質(zhì)檢擾動(dòng)引起的完工時(shí)間長(zhǎng)和能耗高的問(wèn)題，對(duì)綠色動(dòng)態(tài)調(diào)度優(yōu)化問(wèn)題進(jìn)行了研究，得出以下結(jié)論：

(1)建立節(jié)能調(diào)度數(shù)學(xué)模型，采用改進(jìn)的頭腦風(fēng)暴算法進(jìn)行求解，可有效將質(zhì)檢擾動(dòng)的影響控制在一定范圍內(nèi)，保證了生產(chǎn)的穩(wěn)定性和流暢性。用算例進(jìn)行檢驗(yàn)，原始調(diào)度和重調(diào)度的帕累托最優(yōu)解集的分布較為均勻、全面，驗(yàn)證了模型和算法的有效性

(2)改進(jìn)了頭腦風(fēng)暴算法，提高了最優(yōu)解的收斂速度和精度。在編碼環(huán)節(jié)引進(jìn)了轉(zhuǎn)換機(jī)制和多層編碼策略，有效提高了初始種群的質(zhì)量。通過(guò)與其他算法作對(duì)比，驗(yàn)證了算法的可行性與高效性。

(3)決策者根據(jù)生產(chǎn)情境選擇恰當(dāng)?shù)木G色柔性作業(yè)車間動(dòng)態(tài)調(diào)度方案，在保障交付期的前提下，將生產(chǎn)能耗降至最低，有利于企業(yè)降低生產(chǎn)成本、推行可持續(xù)發(fā)展戰(zhàn)略。