時間-能耗-質量權衡優化的柔性作業車間多目標調度研究

趙慧娟 范明霞 姜盼松 溫祿興

(青島科技大學經濟與管理學院 山東 青島 266000)

0 引 言

《中國制造2025》中明確指出,全面推行綠色制造,實施綠色制造工程,在兼顧環境影響和資源效益的同時保證企業經濟效益和社會效益。同時,由于制造企業訂單存在多品種、小批量的特點,生產方式需更加靈活高效,柔性作業車間調度(Flexible Job-Shop Scheduling Problem,FJSP)因其突破資源剛性約束、靈活多變,成為制造企業的主流調度方式。在此背景下,柔性作業車間綠色調度問題成為企業和學術界關注的焦點。在實際生產中,調度問題通常需要兼顧時間、能耗、產品質量等多個目標,在不同時期或情境下,各優化目標的重要度往往不同,決策者針對不同時期或情境做出最優調度安排成為關鍵。因此,本文研究多目標柔性作業車間綠色調度問題具有現實意義和應用價值。

柔性作業車間綠色調度問題是在傳統調度問題的基礎上,協同考慮經濟指標與綠色指標。周炳海等[1]針對加工時間和交貨期的柔性流水線,考慮不相關并行機、換模時間、加工次序等約束研究能耗和準時交貨期雙目標調度問題。雷德明等[2]研究柔性流水線調度問題,在總能耗不超過給定閾值的條件下最小化最大完工時間和總延遲時間,并轉化為最小化最大完工時間、總延遲時間和總能耗三目標。鐘祾充等[3]、李益兵等[4]、楊立熙等[5]考慮到碳排放問題,確定最小化最長完工時間和碳排放總量的優化目標,來研究柔性作業車間和置換流水車間的綠色調度問題。Schulz等[6]、包哲人等[7]除考慮能耗和最大完工時間外,同時考慮經濟指標能耗成本,更加貼合企業實際關注點。李浩等[8]考慮到時間、成本、機器負荷,建立多目標的柔性車間調度問題。劉欣玥等[9]、孟磊磊等[10-11]對能耗成本深度研究,通過關機/重啟節能策略、超低待機節能策略實現主動調度節能,但相較于關機/重啟節能策略,超低待機節能策略可在不停機情況下降低加工間隔狀態功率,避免機器頻繁啟動,更迎合企業實際生產狀況。此外,李聰波等[12]也考慮到緊急任務或機器故障等動態事件對柔性作業車間綠色調度的影響,建立面向節能的動態重調度優化模型,更具靈活性和適應性。

與此同時,眾多專家學者對柔性作業車間綠色調度問題的求解方法進行了研究。綠色調度問題需同時考慮經濟指標和綠色指標,鑒于此類問題的復雜性,學者們常采用智能優化算法求解。Wu等[13]考慮到開/關機和機器變功率兩種節能措施建立能耗模型,采用非支配序列的遺傳算法求解模型,并通過實驗驗證算法的有效性。Gong等[14]建立雙重柔性作業車間調度模型,利用提出的混合遺傳算法求解該模型,與NSGA-Ⅱ對比表明,提出的混合遺傳算法在精度和效率方面更具優勢。Mansouri等[15]結合啟發式算法和MOGA解決綠色調度問題,結果表明該算法在帕累托解的質量方面優于常規算法。Far等[16]采用一種自適應兩階段子種群遺傳算法(SATPSPGA)求解雙目標模糊混合整數線性規劃(FMILP)模型的近似最優解,通過與NSGA-Ⅱ的求解結果對比驗證該算法的有效性。

綜上所述,現有研究仍存在一定不足:(1) 對于多目標柔性作業車間調度問題,通常需決策者預先給出各目標的權重組合,將多目標轉化為單目標,或一次僅考慮一個目標。而實際生產中,不同時期或不同情境下目標重要度不同,即各目標的權重變化,少有學者研究不確定權重下柔性作業車間綠色調度問題。(2) 關于柔性作業車間綠色調度問題的求解目標,學者們多關注時間、成本或能耗等指標,而質量作為企業在市場立足的重要保障,卻少有研究兼顧。鑒于此,本文建立以最大完工時間、能耗和異常指數的歸一加權和最小為調度目標的柔性作業車間綠色調度模型,設計一種改進遺傳算法(Improved Genetic Algorithm,IGA)求解模型,得到不同權重組合下最優調度的決策結果,為不確定條件下的調度決策提供參考。

1 多目標柔性作業車間綠色調度問題建模

1.1 問題描述

在現實生產中,企業需滿足交貨期、能耗和質量等多項指標要求,實際生產決策是綜合考慮各項目標后安排生產調度。然而,針對不同時期或不同情境,各目標的權重不同,如環境政策對于能耗指標的要求、客戶訂單對產品交貨期和質量的要求均影響各目標權重的確定,決策者如何在不同時期或不同情境下確定最優生產調度?此外,當各目標權重表現為一個模糊區間時,決策者如何根據各目標的權重區間確定最優生產調度?為解決上述問題,本文以最小化最大完工時間、能耗和產品異常指數的歸一加權和為目標,建立多目標柔性作業車間綠色調度模型。

此類問題具體表述為:假設車間現有m臺可用機器M={M1,M2,…,Mm},有n個待加工工件J={J1,J2,…,Jn},各工件由預先設定的zi道加工工序組成,zi道工序間有工藝上的先后約束關系。工序Oij可選m臺機器中pij臺機器加工,每臺機器可加工Gk道工序。各工件的所有工序同時在生產線上加工,不同機器加工不同工序的時間、能耗及質量不同,實例如表1所示。表1為一個包括2個工件、4臺機器的多目標柔性作業車間調度問題的加工參數表。以工件J1的第一道工序O11為例,工序O11可選機器M1和M3進行加工,加工時間分別為22和19,加工能耗分別為3和2,機器次品率分別為0.01和0.1。

表1 多目標柔性作業車間調度實例

在對本文提出的問題建模前,為保證研究結果的嚴謹性和準確性,提出如下假設:

(1) 各工件的工序加工相互獨立,工件無優先級。

(2) 每個工件在t=0時刻均可被加工,每個機器在t=0時刻都可用。

(3) 各工序可選的機器有多臺,但每道工序僅能選擇一臺機器加工。

(4) 各工件需按加工工藝順序加工,只有完成上道工序,才可加工下道工序。

(5) 機器一旦啟動,只有加工完所需加工的所有工序才可停止運行,非加工時間保持空載狀態。

(6) 工件的裝夾時間計為加工時間。

(7) 同一時刻每臺機器一次僅能加工一個工件。

(8) 機器連續運轉,且機器間的緩存區無限大。

1.2 相關符號定義

zi:工件Ji加工工序數。

Oij:工件Ji的第j個加工工序。

Gk:機器k加工工序數。

pij:工序Oij的可選機器數。

M(Oij):工序Oij的可選機器集合。

Xijk:0-1變量,工序Oij在機器Mk加工為1,反之為0。

1.3 模型建立

基于問題描述和模型假設,結合本文調度目標為最大完工時間T、能耗E和產品次品率Q的加權和,建立多目標柔性作業車間綠色調度模型。

(1) 最大完工時間Tmax。產品交貨期是客戶極為關注的指標,因此將柔性作業車間調度問題中最大完工時間作為本文首要目標。所有機器的最大完工時間表示為:

(1)

(2) 能耗E。車間能耗包括加工能耗、空載能耗、啟動能耗、公共能耗等,由于啟動能耗僅在工件開始加工時產生,啟動能耗為定值且只發生一次,調度變化不會影響啟動能耗。因此本文主要考慮加工能耗、空載能耗和公共能耗。車間加工能耗Ew表示為:

(2)

式中:若工序Oij在機器Mk上加工,則Xijk為1,反之為0。

空載能耗是指機器加工完成工件Ji,下一加工工件未到達產生的能耗,可表示為空閑時間與空載功率乘積的集合。空載總能耗Ef表示為:

(3)

公共能耗是維持車間正常運行所必需的能耗,與最大完工時間有關。公共能耗由最大完成時間與公共功率Pc的乘積表示:

Ec=Pc·Tmax

(4)

因此,車間總能耗E表示為:

(5)

(6)

本文的目標函數是使歸一化的最大完工時間、能耗和異常指數的加權和最小,故建立如下多目標柔性作業車間調度模型,式(8)為各目標歸一化處理公式。

(7)

x′=(x-xmin)/(xmax-xmin)

(8)

(9)

(10)

(11)

(12)

(13)

α+β+γ=1

(14)

式(9)表示任一工序只能選擇在一臺機器上加工,且只能加工一次;式(10)表示工序一旦開始加工,不可中斷;式(11)表示同一機器同一時刻僅能加工一道工序;式(12)表示同一工件的不同工序之間的順序約束;式(13)表示機器在t=0時刻都可用;式(14)是對各目標權重的約束。

2 改進遺傳算法設計

本文建立包括最大完工時間、能耗和質量的多目標柔性作業車間調度模型,結合模型特點提出一種改進遺傳算法(IGA)。在IGA中,染色體編碼采用工序碼和機器碼結合的雙層編碼方式,采用隨機生成和局部選擇相結合的初始化策略;通過適用度函數篩選優勢個體和淘汰劣勢個體,一方面將優勢個體添加至優勢集合,另一方面將優勢個體與輪盤賭選擇后的種群組合成新種群,既保證優勢個體不被破壞又提升新種群質量;交叉和變異階段,分別對工序層和機器層進行交叉和變異,提高子代種群多樣性,交叉階段對工序層進行基因沖突檢驗,變異階段對設備層進行基因匹配檢驗,避免不良基因產生;最后,通過優勢集合選優獲得最優個體。具體改進算法流程見圖1。

圖1 改進算法流程

圖2 編碼示意圖

2) 初始種群。為保證初始種群多樣性和設備負荷均衡,本文采用隨機生成和局部選擇相結合的初始化策略。局部選擇策略是根據工序數和設備數,預先設定各機器可加工工序的合理范圍,并基于此選擇初始種群。本文設定兩種策略的個體生成比例分別為70%和30%。

3) 適應度計算。本文調度目標為最大完工時間T、能耗E和質量Q的歸一加權和,對各目標函數歸一化處理后,分別賦予權重α、β和γ,多目標調度模型函數為式(15),定義f(x)=1/z作為適應度函數。

(15)

由于每次初始種群的個體不同,導致不同種群的歸一化結果無可比性。本文算法通過適用度函數篩選優勢個體和淘汰劣勢個體,并將優勢個體添加至優勢集合,最終通過后期優勢集合選優解決此問題。

4) 選擇。采用輪盤賭法選擇新種群,并將適用度計算的優勢個體添加至新種群,以提升種群質量。

5) 交叉。算法分別對工序層和機器層交叉。

(1) 工序層交叉。交叉操作見圖3。

圖3 工序層交叉操作

步驟1將所有工序隨機分成兩個集合,分別表示為Parent1和Parent2。

步驟2隨機選擇兩個交叉點。

步驟3基因交換生成子代染色體Child1和Child2。

步驟4由于交叉造成子代染色體基因所占比例改變,致使染色體不滿足約束成為非法染色體,故而進行基因沖突檢驗。如圖3中子代Child1多出基因6和基因2,而缺少基因3和基因4,故需將交叉區的基因6和基因2置換為基因3和基因4。

最終,子代Child1中基因6置換為基因4、基因2置換為基因3,子代Child2中的基因4置換為基因6,基因3置換為基因2,工序層交叉操作后完成。

(2) 機器層交叉。由于機器層染色體的基因位置對應相同的工序,故機器層染色體交叉僅需重復工序層操作的步驟1-步驟3,無須基因沖突檢驗。

6) 變異。本文采用換位變異法對工序層和設備層進行變異操作。

(1) 工序層變異。隨機交換工序層染色體的兩基因位。

(2) 設備層變異。由于機器層染色體的基因位可選機器有限(工序只能被特定設備集加工),致使機器層變異操作可能產生非法基因,故而變異操作后需對染色體進行基因匹配檢驗。隨機選擇機器層染色體的兩個基因位,如圖4所示。基因位2表示工序O12,其可選機器集為{M2,M4,M5}。基因位5表示工序O15,其可選設備集為{M1,M3,M4,M6}。設備層換位需考慮各位置的工序是否可選該機器加工,工序O15可在機器M4加工,故可將基因位5的基因變異為4。而工序O12不可選機器M6,故基因位2僅能在工序O12的剩余機器集隨機選擇機器。

圖4 設備層變異過程

7) 優勢集合選優。本文優化目標為最大完工時間T、能耗E和質量Q的歸一化加權和,適用度計算階段是對各子目標歸一化處理后排序,然而不同種群的歸一化加權和無法直接比較,故而本文提出增加優勢集合選優階段。通過適用度計算,保留各種群的優勢個體形成優勢集合,算法終止后對優勢集合篩選,得到最優個體。

3 案例分析

本文案例分析主要包含兩部分:(1) 為檢驗本文改進遺傳算法對實際生產調度問題求解的效果,根據實際生產過程的真實數據,選取傳統遺傳算法(GA)和改進的遺傳算法(IGA)兩種智能算法作對比,基于案例驗證改進遺傳算法的有效性和優越性。(2) 從應用案例的角度,對實際問題進行分析,基于改進遺傳算法求解不同權重下的最優調度方案以及給定權重區間的最優調度方案。

3.1 案例介紹

表2 生產實測數據

續表2

表3 機器空載能耗

3.2 IGA性能分析

3.2.1單目標優化

以3.1節的案例作為實驗對象,分別運用GA和IGA對單目標問題求解。設置最大完工時間、能耗和質量的權重比分別為[1,0,0]、[0,1,0]、[0,0,1],即每次求解僅考慮單個目標。兩種算法分別求解單目標問題的收斂曲線見圖5-圖7。觀察圖5-圖7發現,改進遺傳算法的收斂速度和尋優效果要明顯優于傳統遺傳算法。

圖5 兩種算法求解最大完工時間目標的收斂曲線

圖6 兩種算法求解能耗目標的收斂曲線

圖7 兩種算法求解質量目標的收斂曲線

基于傳統遺傳算法和改進遺傳算法分別運算20次,以20次運行結果的適應度均值、最優解、最劣解和平均偏差四個指標衡量算法的優劣,見表4。對比兩種智能算法的求解結果發現,改進的遺傳算法在求解三個單目標問題時,平均適應度、最優解、最劣解和平均偏差均優于傳統遺傳算法。因此,本文算法在求解單目標問題時有更強尋優能力。

表4 算法求解單目標問題的性能分析

3.2.2多目標優化

以3.1節的案例作為實驗對象,分別運用GA和IGA對多目標問題求解。由于最小最大完工時間、能耗和產品質量三個目標量綱不同,因此需做歸一化處理。對三個目標分別賦權1/3、1/3、1/3后,求解多目標的最優調度方案。兩種算法求解多目標問題的收斂曲線見圖8,可以看出,GA在第150代左右開始尋得最優解,但算法陷入局部最優,IGA在120代得到最優解。從收斂速度和尋優效果方面,改進遺傳算法在求解多目標問題時更具優勢。

圖8 兩種算法求解多目標問題的收斂曲線

為進一步比較兩種算法的求解效果,兩種算法分別運行20次后,保留20次運算結果的調度方案,歸一化處理后計算模型目標值,求解結果見圖9,算法性能分析見表5。由表5發現,改進的遺傳算法在求解多目標問題時,總目標均值、最優值、最劣值均優于傳統遺傳算法,由于改進遺傳算法解的多樣性更強,導致平均偏差略高于傳統遺傳算法。綜合考慮各項指標,改進的遺傳算法在求解多目標問題時更具優勢。

圖9 運算結果對比

表5 算法求解多目標問題的性能分析

3.3 多目標柔性作業車間綠色調度問題求解

(16)

為觀察權重變化對目標值的影響,基于改進的遺傳算法對各權重組合下的目標函數運算10次,將不同權重組合的最優目標值擬合為三維空間圖,如圖10所示。

圖10 不同權重組合下最優調度的求解結果

觀察圖10可以發現:

(1) 整體而言,目標值z隨子目標權重的變化而變化。隨著最大完工時間和能耗兩指標權重的增加,目標值z呈現先增加后下降的趨勢。

(2) 三維曲面圖的目標最小值對應的權重組合分別為[1,0,0]、[0,1,0]、[0,0,1],三種權重組合下該模型轉化為單目標優化模型,即對應調度方案中的單目標為全局最優。權重組合[1,0,0]表示完成時間目標權重為1,其余兩目標權重為0,此時目標轉化為將最大完工時間最小化,最優調度甘特圖見圖11;權重組合[0,1,0]表示能耗目標權重為1,其余兩目標權重為0,此時目標轉化為將能耗降至最低,最優調度甘特圖見圖12;權重組合[0,0,1]表示質量目標權重為1,其余兩目標權重為0,此時目標轉化為將異常指數降至最低,最優調度甘特圖見圖13;曲面最高點大致位于三個子目標權重相等的位置,此時均衡考慮各目標,最優調度甘特圖見圖14。各調度方案下求解結果如表6所示。

圖11 僅考慮最小最大完工時間目標的最優調度甘特圖

圖12 僅考慮最小能耗目標的最優調度甘特圖

圖13 僅考慮最小異常指數目標的最優調度甘特圖

圖14 綜合考慮各目標的最優調度甘特圖

表6 各調度方案求解結果

由表6可知,當僅考慮最小最大完成時間目標時,完成時間達到了最小值69,其適用于企業需要提高生產效率、快速加工的情況。但與僅考慮最小能耗目標的方案相比,其完成時間僅縮短2 min,無顯著優勢,且其能耗與異常指數均高于僅考慮能耗組。當企業在生產中已經產生過多能耗,需要加以限制時,企業會著重考慮將能耗最小化。當僅考慮質量時,異常指數僅為2.13,明顯低于其余三組,然而此時是以犧牲完成時間和能耗為代價的。均衡考慮各目標時,與單目標優化方案相比,在完成時間、能耗、異常指數三個方面達到相對均衡,適用于企業在生產過程中沒有特殊要求、生產情況較穩定時。

(3) 根據三維曲面圖,針對不同的目標權重系數,均可得到相應的最優調度結果。在實際生產中,子目標重要度往往較為模糊,即權重表現為數值區間。決策者可基于圖10圈定權重區間獲得最優調度方案。例如,當α∈[0.3,0.5]、β∈[0.2,0.3],權重區間內最小目標值所對應的方案即為該區間的最優調度,最小目標值為0.197,完成時間為78,能耗為861.68,異常指數為3.69,最優調度方案的甘特圖見圖15。

圖15 權重區間內最優調度方案甘特圖

4 結 語

本文針對柔性作業車間綠色調度問題,建立完工時間、能耗和質量權衡優化的調度模型,并提出一種改進的遺傳算法用于解決此類問題。在算法中,種群初始化階段采用隨機生成和局部選擇相結合的初始化策略,既保證初始種群的質量又提升個體多樣性;適用度計算階段,通過適用度函數篩選優勢個體和淘汰劣勢個體,將優勢個體添加至優勢集合并與輪盤賭選擇后的種群組合成新種群,既保證優勢個體不被破壞又提升新種群質量;交叉和變異階段是對工序層和機器層分別進行交叉和變異,提高子代種群多樣性。交叉階段對工序層進行基因沖突檢驗,變異階段對設備層進行基因匹配檢驗,避免不良基因產生;算法終止后,通過優勢集合選優獲得最優個體。最后,將改進的遺傳算法用于實際問題,結果表明改進遺傳算法的有效性,同時形成不同權重組合下最優調度的決策模型,為變動權重或模糊權重區間下的調度決策問題提供參考。

目前對于柔性作業車間調度的研究主要圍繞靜態調度問題,下一步的研究方向為柔性作業車間的動態調度問題。