陳文洲, 李登峰, 鄭小雪

(1. 福州大學經濟與管理學院,福州 350108; 2. 電子科技大學經濟與管理學院,成都 611731; 3. 閩江學院新華都商學院,福州 350108)

0 引言

隨著經濟的快速發(fā)展,世界各國制造業(yè)越來越關注綠色生產,生產制造過程不斷地進行著轉型升級。在企業(yè)生產產品過程中,碳排放量是評價綠色制造的重要指標之一,低碳生產與企業(yè)的可持續(xù)發(fā)展密切相關。由于綠色制造環(huán)節(jié)所涉及到的評價指標復雜多樣,因此國內外在車間調度中對綠色制造的研究相對較少。文獻[1]在柔性作業(yè)車間調度問題中考慮了加工過程的碳排放量,并將能源消耗成本與提前/延期成本作為調度目標,建立了低碳調度雙目標數學模型;文獻[2]考慮了在隨機加工時間下的總碳排放量,并建立了調度的多目標模型;文獻[3]建立了以最大完工時間最小和碳排放量最小的雙目標柔性作業(yè)車間調度問題模型。

分布式柔性作業(yè)車間調度問題(Distributed flexible job-shop scheduling problem,簡稱為DFJSP)是柔性作業(yè)車間調度問題的擴展,該問題不僅要解決工件在不同車間中的合理分配,還要解決車間內工序的加工順序和機器的選擇問題,是NP-hard問題。由于DFJSP的復雜性,大部分文獻研究的是單目標DFJSP,較少研究多目標DFJSP。為了有效求解DFJSP, 文獻[4]設計了CRODFJSP(Chemical Reaction Optimization metaheuristic for DFJSP)算法,但只考慮了單目標問題;文獻[5]提出改進的差分進化算法求解雙目標DFJSP;文獻[6]利用目標級聯(lián)法和遺傳算法相結合求解以最小化總完工時間為目標的單目標DFJSP。在求解作業(yè)車間調度的眾多算法中,人工蜂群算法因操作簡便,參數設置少等特點,近些年在車間調度中的應用越來越廣泛[7]。

綜上所述,大部分針對綠色制造的研究都是在車間調度或是柔性作業(yè)車間調度中,尚未發(fā)現面向分布式柔性作業(yè)車間調度問題的低碳研究。因此,本文從生產的實際角度出發(fā),迎合當下綠色制造的熱點,不僅研究考慮加工過程碳排放量的分布式柔性作業(yè)車間雙目標調度問題,而且針對該問題對人工蜂群算法進行有效設計,提出兩階段編碼策略,引入均勻交叉、IPOX交叉、單點變換等操作與基于Pareto優(yōu)化的外部存檔相結合增強算法的局部搜索與全局尋優(yōu)能力,實驗結果表明,改進算法在收斂速度與解的質量方面得到有效。

1 考慮低碳的DFJSP優(yōu)化模型

1.1 問題描述

1.2 模型構建

(1)模型假設

1)同一工件在不同車間中加工所需的工序是相同的;

2)同一機器同一時刻只能加工一道工序;

3)在0時刻,所有機器均可用,所有工件均可被加工;

4)同一工件的不同工序存在優(yōu)先關系,后道工序須在前道工序加工完成后才能開始;

5)不同工件之間不存在優(yōu)先關系;

6)由于各機器間的性能存在差異,不同機器加工同一工件所需的時間不盡相同。

(2)符號定義

Cij表示Oij的完工時間;

(3)構建的數學模型

(1)

(2)

s.t.

(3)

(4)

(5)

式(1)、式(2)為目標函數,式(1)表示最小化最大完工時間,式(2)表示最小化總碳排放量;式(3)～式(5)為約束條件,式(3)表示后道工序在前道工序完成后才開始,式(4)表示工件的每道工序只能在一臺機器上加工,式(5)表示一個工件的所有工序只能在同一車間加工,不能跨車間完成。

2 改進的人工蜂群算法

人工蜂群算法是一種基于種群的元啟發(fā)式算法,模仿蜂群的覓食行為[8-9]。在人工蜂群算法中,有采蜜蜂、觀察蜂和偵察蜂3種蜜蜂。正在開采蜜源的蜜蜂被稱為采蜜蜂,在蜂巢中等待對蜜源做出選擇決定的蜜蜂被稱為觀察蜂,隨機尋找新的蜜源的蜜蜂被稱為偵察蜂。人工蜂群算法最初是為解決多目標連續(xù)優(yōu)化問題而設計的,而本文所研究的DFJSP是典型的離散優(yōu)化問題。因此,為了有效求解DFJSP,本文從編碼解碼和三種蜂的搜索策略方面對人工蜂群算法進行改進設計。

2.1 編碼解碼

DFJSP在編碼上要考慮3個問題:車間分配、工序加工順序、機器選擇。因此本文提出一種兩階段編碼方式:在第一階段,首先對工件進行車間選擇,確定各工件被分配到的車間號;第二階段對每個車間內的工件的所有工序進行排序和機器選擇,確定工序的加工順序和進行加工的機器。假設有3個工件,2個車間,工序序列[1 1 1 2 2 2 2 3 3 3]中的數字表示工件號,各數字出現的次數表示該工件的總工序,其中工件1有3道工序。如圖1所示,工件2和工件3被分配到車間1中加工,工件3的3道工序分別在機器2、機器1和機器3上加工。

圖1 DFJSP的兩階段編碼

2.2 種群初始化

在人工蜂群算法中,初始種群代表初始解的質量,在一定程度上影響著算法運行過程的收斂速度。生成的初始種群不僅要體現多樣性,避免算法陷入局部最優(yōu)困境,同時還需保證種群的質量,提高算法收斂速度。因此,為合理生成初始種群,保證種群的質量和多樣性,在第一階段編碼上,采用基于工件數少的策略和隨機策略生成車間序列,數量各占種群規(guī)模的50%;第二階段中隨機對工序進行排序,通過基于累計加工時間最短策略和隨機策略生成機器序列,數量各占種群規(guī)模的50%。

2.3 基于pareto優(yōu)化的外部存檔

與單目標優(yōu)化問題不同,優(yōu)化的多個目標之間存在沖突。常見的多目標優(yōu)化方法主要有聚合方法、字典序法、帕雷托方法和混合方法等[10]。不少學者使用聚合方法對多個目標賦予一定的權重值,將多目標問題轉換為單目標問題,但多個目標間的權重值的選取一般具有主觀性,難以定量衡量,細微的偏差就可能導致完全不同的結果。而在人工蜂群算法中結合帕雷托優(yōu)化方法來控制蜜蜂的搜索行為,能夠較好地求解多目標問題[11]。因此本文在算法中引入Pareto優(yōu)化方法并結合外部存檔記錄Pareto解集。在算法開始迭代時,對種群進行Pareto快速非支配排序,篩選出Pareto解集并保存于外部存檔,每次迭代后更新外部檔案,剔除外部檔案中被支配的個體,直至算法運行結束。最終外部存檔的Pareto解集即為優(yōu)化問題的最優(yōu)解集。

2.4 采蜜蜂

在ABC算法中,采蜜蜂負責對解空間進行鄰域改良搜索,搜尋可能存在的更優(yōu)解。為了保證有效地進行鄰域搜索,在采蜜蜂階段只對工序序列進行變換,即在保證車間序列不變情況下,通過變換,找出當前分配的車間下最優(yōu)的工序排序和機器選擇方案。工序序列采用均勻交叉策略[12],即隨機產生由0和1組成的與工序總數相同的序列,隨機選取一個外部檔案中的蜜源,將該個體與1位置對應的工序與父代交換,其余位置保持不變。機器序列采用IPOX[13]與基于累計加工時間最小策略[14]各生成一組機器序列,根據帕雷托支配準則從中選擇較優(yōu)的與當前蜜源進行帕雷托支配判斷,若支配當前蜜源,則用新蜜源替代當前蜜源,并更新外部存檔。

2.5 觀察蜂

觀察蜂根據采蜜蜂提供的信息,依概率對當前蜜源進行鄰域搜索。根據文獻[15]提出的快速非支配排序法對種群所有蜜源計算跟隨概率,將種群中每個蜜源與其他所有蜜源進行Pareto非支配判斷,該蜜源支配的蜜源數占種群蜜源總數的比值即為跟隨概率。再通過輪盤賭方式判斷是否進行觀察蜂操作。觀察蜂使用與采蜜蜂相同的鄰域搜索策略判斷是否更新蜜源,若是,則新蜜源替換當前蜜源,并更新帕雷托外部存檔。

2.6 偵察蜂

在采蜜蜂與觀察蜂搜索之后，可能出現蜜源在一定次數的改良搜索后質量未得到改善,此時有可能導致算法陷入局部收斂困境中。為避免算法局部收斂并提高解集的多樣性,通過偵察蜂操作對蜜源進行重構,增加種群多樣性。對當前蜜源的車間序列進行單點變換,按初始化策略生成工序和機器序列,替代當前蜜源。車間序列的單點變換策略是指在各車間中隨機選擇一個工件進行交換,其中3個車間10個工件的單點變換如圖2所示。

圖2 單點變換策略

2.7 改進的人工蜂群算法框架

本文提出的用于解決考慮低碳的DFJSP改進的人工蜂群算法的基本框架如圖3所示。

圖3 改進的人工蜂群算法

3 仿真分析

為了驗證本文改進的人工蜂群算法求解考慮低碳的分布式柔性作業(yè)車間調度的性能。本文以MATLAB R2016b為編程環(huán)境,在配置為Intel(R) Core(TM) i5-8250U, 1.6 GHz CPU,8.00 GB RAM, Windows10 64位操作系統(tǒng)的計算機上運行。本文選取Brandimarte標準測試算例來測試算法的性能,并設計了兩組實驗驗證算法求解低碳分布式柔性作業(yè)車間調度的有效性。

針對本文算法的雙目標性能進行實驗測試,實驗參數設置為：種群規(guī)模為100,最大迭代數為100。由于對比的IGA[16]多目標優(yōu)化算法是以最小化最大完工時間和最小化關鍵機器負載為指標,為了保證對比實驗的準確合理性,實驗將調度目標中的碳排放指標變換為關鍵機器負載指標進行算法收斂性實驗設計。其中,每個Brandimarte算例獨立運行20次,運行結果如表1所示。其中,n為工件數,m為機器數,Cmax為20次運行中最大完工時間最優(yōu)值,Av(C)為各次運行結果的最大完工時間平均值,Wmax為關鍵機器負載最優(yōu)值。

表1 Brandimarte算例實驗結果比較

由表1可知,在10個算例的測試結果中,本文所提算法與IGA算法相比,有5個算例的結果更優(yōu),2個算例結果相同,3個算例結果較差?？傮w上,本文的算法優(yōu)于IGA算法,并且從獲得的完工時間均值上看,本文的算法有更好的穩(wěn)定性。說明本文改進的人工蜂群算法求解雙目標柔性作業(yè)車間調度問題是有效的。

為了直觀展現算法的收斂性,取表1中兩算法所得結果相同的算例MK08作為收斂性對比實驗,以最小化最大完工時間作為測試收斂性指標與IGA算法得到的結果進行比較,算法收斂曲線的比較結果如圖4所示。

圖4 算法收斂曲線對比(MK08)

由圖4可知,本文算法比IGA算法更早得到了問題的最優(yōu)解,說明本文改進的人工蜂群算法收斂速度更快,收斂性能更優(yōu)。

本文設計的求解低碳分布式柔性作業(yè)車間調度有效性的實驗分為兩組,實驗1是FJSP實驗,實驗數據采用文獻[17-18]的調度數據;實驗2是雙車間同構DFJSP,是將實驗1的單車間數據復制為雙車間的調度數據進行實驗。其中,實驗1的調度結果如表2所示。

表2 不同算法的結果對比

從表2可以看出,本文的算法生成了6組帕雷托解,帕雷托解優(yōu)于其他對比算法。并且各帕雷托解的碳排放量總體水平低于其他對比算法,其中解1的調度甘特圖如圖5所示。實驗結果表明,本文提出的基于帕雷托優(yōu)化的人工蜂群算法能夠有效求解FJSP問題。

圖5 解1的調度甘特圖

實驗2是雙車間同構分布式柔性作業(yè)車間調度問題,利用本文的算法求解得到的帕雷托最優(yōu)解分別為(f1=64,f2=638.5)、(f1=65,f2=624.9)。調度甘特圖分別如圖6和圖7所示。

圖6 同構雙車間DFJSP甘特圖(f1=64,f2=638.5)

圖7 同構雙車間DFJSP甘特圖(f1=65,f2=624.9)

將FJSP與同構雙車間DFJSP采用本文的人工蜂群算法求解得到的解匯總如表3所示。

表3 本文算法求解不同調度類型的調度結果

從表3可以得出,DFJSP得到的調度結果明顯優(yōu)于FJSP,這主要由于在DFJSP中,工件有了更多可用車間和可用機器。而有效的調度算法能夠保證在DFJSP的復雜環(huán)境中,快速找到有效的調度方案,利用不同車間的生產資源來滿足制造過程的需求,使得所研究的各項調度指標值趨于更優(yōu)。

4 總結

本文研究了同構雙車間DFJSP,建立了考慮碳排放量和完工時間的DFJSP雙目標優(yōu)化模型。為了有效求解調度問題模型,設計了改進的人工蜂群算法,提出兩階段編碼方式,采用0-1均勻交叉、兩點交叉和基于累計時間最短策略等提高采蜜蜂和觀察蜂的鄰域搜索質量,利用單點變換策略提高偵察蜂的全局尋優(yōu)能力。最后通過FJSP和同構雙車間DFJSP兩組實驗來驗證所提算法的有效性,并分析了在不同調度類型下,調度結果所呈現的特征。實驗結果表明,該算法算法收斂速度較快,收斂質量較好,可以有效解決考慮低碳的分布式柔性車間調度雙目標優(yōu)化問題。并且發(fā)現在分布式生產環(huán)境下,合理調度各車間的生產資源,能夠有效提升加工效率,減少碳排放,打破單車間的生產限制。

在實際的生產過程中,遇到的問題是復雜多樣的,更合理有效契合實際生產環(huán)境的調度方案需要考慮更多的因素,因此本文研究的問題在接下來的研究中將深入探討在考慮碳排放的同時,如何能夠有效保證產品的加工質量以及研究加工質量的評定指標等多目標問題。