考慮低碳的分布式柔性作業(yè)車間調(diào)度優(yōu)化*

陳文洲, 李登峰, 鄭小雪

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

0 引言

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

分布式柔性作業(yè)車間調(diào)度問(wèn)題(Distributed flexible job-shop scheduling problem,簡(jiǎn)稱為DFJSP)是柔性作業(yè)車間調(diào)度問(wèn)題的擴(kuò)展,該問(wèn)題不僅要解決工件在不同車間中的合理分配,還要解決車間內(nèi)工序的加工順序和機(jī)器的選擇問(wèn)題,是NP-hard問(wèn)題。由于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)問(wèn)題;文獻(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)度的眾多算法中,人工蜂群算法因操作簡(jiǎn)便,參數(shù)設(shè)置少等特點(diǎn),近些年在車間調(diào)度中的應(yīng)用越來(lái)越廣泛[7]。

綜上所述,大部分針對(duì)綠色制造的研究都是在車間調(diào)度或是柔性作業(yè)車間調(diào)度中,尚未發(fā)現(xiàn)面向分布式柔性作業(yè)車間調(diào)度問(wèn)題的低碳研究。因此,本文從生產(chǎn)的實(shí)際角度出發(fā),迎合當(dāng)下綠色制造的熱點(diǎn),不僅研究考慮加工過(guò)程碳排放量的分布式柔性作業(yè)車間雙目標(biāo)調(diào)度問(wèn)題,而且針對(duì)該問(wèn)題對(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 問(wèn)題描述

1.2 模型構(gòu)建

(1)模型假設(shè)

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

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

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

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

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)表示后道工序在前道工序完成后才開(kāi)始,式(4)表示工件的每道工序只能在一臺(tái)機(jī)器上加工,式(5)表示一個(gè)工件的所有工序只能在同一車間加工,不能跨車間完成。

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

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

2.1 編碼解碼

DFJSP在編碼上要考慮3個(gè)問(wèn)題:車間分配、工序加工順序、機(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)行過(guò)程的收斂速度。生成的初始種群不僅要體現(xiàn)多樣性,避免算法陷入局部最優(yōu)困境,同時(shí)還需保證種群的質(zhì)量,提高算法收斂速度。因此,為合理生成初始種群,保證種群的質(zhì)量和多樣性,在第一階段編碼上,采用基于工件數(shù)少的策略和隨機(jī)策略生成車間序列,數(shù)量各占種群規(guī)模的50%;第二階段中隨機(jī)對(duì)工序進(jìn)行排序,通過(guò)基于累計(jì)加工時(shí)間最短策略和隨機(jī)策略生成機(jī)器序列,數(shù)量各占種群規(guī)模的50%。

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

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

2.4 采蜜蜂

在ABC算法中,采蜜蜂負(fù)責(zé)對(duì)解空間進(jìn)行鄰域改良搜索,搜尋可能存在的更優(yōu)解。為了保證有效地進(jìn)行鄰域搜索,在采蜜蜂階段只對(duì)工序序列進(jìn)行變換,即在保證車間序列不變情況下,通過(guò)變換,找出當(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ù)的比值即為跟隨概率。再通過(guò)輪盤賭方式判斷是否進(jìn)行觀察蜂操作。觀察蜂使用與采蜜蜂相同的鄰域搜索策略判斷是否更新蜜源,若是,則新蜜源替換當(dāng)前蜜源,并更新帕雷托外部存檔。

2.6 偵察蜂

在采蜜蜂與觀察蜂搜索之后，可能出現(xiàn)蜜源在一定次數(shù)的改良搜索后質(zhì)量未得到改善,此時(shí)有可能導(dǎo)致算法陷入局部收斂困境中。為避免算法局部收斂并提高解集的多樣性,通過(guò)偵察蜂操作對(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è)試算例來(lái)測(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)定性。說(shuō)明本文改進(jìn)的人工蜂群算法求解雙目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題是有效的。

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

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

由圖4可知,本文算法比IGA算法更早得到了問(wèn)題的最優(yōu)解,說(shuō)明本文改進(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問(wèn)題。

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

實(shí)驗(yàn)2是雙車間同構(gòu)分布式柔性作業(yè)車間調(diào)度問(wèn)題,利用本文的算法求解得到的帕雷托最優(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)資源來(lái)滿足制造過(guò)程的需求,使得所研究的各項(xiàng)調(diào)度指標(biāo)值趨于更優(yōu)。

4 總結(jié)

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

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