陳文洲, 李登峰, 鄭小雪

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

0 引言

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

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

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

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

1.1 問題描述

1.2 模型構(gòu)建

(1)模型假設(shè)

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

2)同一機(jī)器同一時(shí)刻只能加工一道工序;

3)在0時(shí)刻,所有機(jī)器均可用,所有工件均可被加工;

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

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

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

(2)符號(hào)定義

Cij表示Oij的完工時(shí)間;

(3)構(gòu)建的數(shù)學(xué)模型

(1)

(2)

s.t.

(3)

(4)

(5)

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

2 改進(jìn)的人工蜂群算法

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

2.1 編碼解碼

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

圖1 DFJSP的兩階段編碼

2.2 種群初始化

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

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

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

2.4 采蜜蜂

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

2.5 觀察蜂

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

2.6 偵察蜂

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

圖2 單點(diǎn)變換策略

2.7 改進(jìn)的人工蜂群算法框架

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

圖3 改進(jìn)的人工蜂群算法

3 仿真分析

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

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

表1 Brandimarte算例實(shí)驗(yàn)結(jié)果比較

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

為了直觀展現(xiàn)算法的收斂性,取表1中兩算法所得結(jié)果相同的算例MK08作為收斂性對(duì)比實(shí)驗(yàn),以最小化最大完工時(shí)間作為測(cè)試收斂性指標(biāo)與IGA算法得到的結(jié)果進(jìn)行比較,算法收斂曲線的比較結(jié)果如圖4所示。

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

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

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

表2 不同算法的結(jié)果對(duì)比

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

圖5 解1的調(diào)度甘特圖

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

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

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

將FJSP與同構(gòu)雙車間DFJSP采用本文的人工蜂群算法求解得到的解匯總?cè)绫?所示。

表3 本文算法求解不同調(diào)度類型的調(diào)度結(jié)果

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

4 總結(jié)

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

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