一種用于PFSP節(jié)能優(yōu)化的混合禁忌搜索算法

張雨晨, 熊福力

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055)

0 引言

隨著綠色制造的全球化與生產(chǎn)力的提高，能源需求量日益增加，能源消耗造成的環(huán)境問(wèn)題日益突出[1]。通過(guò)節(jié)能與環(huán)境保護(hù)的手段可有效地推進(jìn)可持續(xù)發(fā)展政策，具有顯著的經(jīng)濟(jì)效益和社會(huì)效益。為了滿足綠色生產(chǎn)和客戶滿意度的要求，企業(yè)必須同時(shí)考慮訂單接受和生產(chǎn)計(jì)劃。訂單接受與調(diào)度(OAS,order acceptance and scheduling)問(wèn)題決定接受哪些訂單并決策接受訂單的加工順序，根據(jù)文獻(xiàn)[2-3]的研究，它有著與大多數(shù)車間調(diào)度問(wèn)題相同的特點(diǎn)。置換流水車間調(diào)度問(wèn)題(PFSP,permutation flow shop problem)是流水車間調(diào)度問(wèn)題中一類典型的子問(wèn)題，也是調(diào)度問(wèn)題的研究熱點(diǎn)[4]。它通常側(cè)重于優(yōu)化生產(chǎn)效率指標(biāo)，如總完成時(shí)間、拖期、加權(quán)完工時(shí)間等[5-6]。而能源效率優(yōu)化是企業(yè)實(shí)現(xiàn)可持續(xù)發(fā)展的關(guān)鍵因素之一，因此，進(jìn)行訂單選擇與生產(chǎn)調(diào)度的統(tǒng)一決策，使企業(yè)能夠獲得更加穩(wěn)定有效的決策方案。車間能效優(yōu)化相關(guān)研究已有杰出成果，文獻(xiàn)[7-8]提出同時(shí)優(yōu)化能源消耗與總完工時(shí)間的多目標(biāo)數(shù)學(xué)規(guī)劃模型。劉向[9]提出一種混合遺傳算法求解面向節(jié)能降耗的調(diào)度模型。Shabtay[10-11]提出了集成提前/拖期懲罰和交貨期分配的數(shù)學(xué)模型。優(yōu)化PFSP的方法有很多，如精確求解算法、構(gòu)造啟發(fā)式算法與智能優(yōu)化算法。其中智能優(yōu)化算法更適合優(yōu)化PFSP，尤其是禁忌搜索[12]、遺傳算法、迭代局部搜索、粒子群算法等。

本文突破了傳統(tǒng)PFSP的角度，建立了置換流水車間訂單接受與調(diào)度(PFSOAS,permutation flow shop order acceptance and scheduling)問(wèn)題，旨在最大化企業(yè)生產(chǎn)總凈利潤(rùn)(TNR,total net revenue)。本文于傳統(tǒng)禁忌搜索的基礎(chǔ)上，提出了一種節(jié)能混合禁忌搜索算法(EHTS,energy-saving hybrid tabu search)，它整合了一種能耗調(diào)整策略與交貨期配置策略，實(shí)現(xiàn)對(duì)能耗的二次降低，加入了一種訂單接受與拒絕(OAR,order acceptance and rejection)的編碼方式，并設(shè)計(jì)了NEH構(gòu)造啟發(fā)式算法產(chǎn)生禁忌搜索算法的初始解，以改善算法優(yōu)化質(zhì)量。通過(guò)上述改進(jìn)，提高了算法解決本文所提出的特殊的PFSOASP的尋優(yōu)能力。通過(guò)大量實(shí)際算例的統(tǒng)計(jì)實(shí)驗(yàn)，分析了該算法的優(yōu)異性能，接著描述了所提出的PFSOAS模型，并且通過(guò)實(shí)驗(yàn)分析了EHTS算法求解PFSOAS問(wèn)題的有效性與優(yōu)越性。

1 問(wèn)題描述

由客戶提供一批訂單集合I，與訂單i相關(guān)的指標(biāo)分別是固定收入Ri，相同的截止日期D與交貨期d，拖期懲罰權(quán)重wi，客戶期望的交貨期區(qū)間。PFSOAS問(wèn)題通過(guò)決定接受那些訂單，決策已接受訂單的加工順序與確定訂單開(kāi)始加工時(shí)間使總利潤(rùn)最大化。

1.1 相關(guān)假設(shè)與參數(shù)說(shuō)明

相關(guān)假設(shè)：每臺(tái)機(jī)器上每個(gè)訂單的處理時(shí)間為已知且恒定的；每個(gè)階段在同一時(shí)刻只能處理一個(gè)訂單；生產(chǎn)過(guò)程中無(wú)搶占，即某訂單只有在上一個(gè)訂單完工后才可被加工；任何接受的訂單只有當(dāng)前階段的完成處理后才能在下一階段處理，準(zhǔn)備時(shí)間為0；工作臺(tái)之間緩沖區(qū)無(wú)限大；每臺(tái)機(jī)器在調(diào)度開(kāi)始時(shí)處于空閑狀態(tài)，并且一次最多可處理一個(gè)接受的訂單；機(jī)器上訂單的建立時(shí)間和釋放時(shí)間忽略不計(jì)。

表1 模型參數(shù)說(shuō)明

1.2 PFSOAS模型

目標(biāo)函數(shù)：

maxTNR

(1)

(2)

其中:TEC為對(duì)接受訂單進(jìn)行加工的總能源成本，ECi為加工訂單i時(shí)所需的機(jī)器能耗。

(3)

(4)

s.t.：

(5)

2≤i≤n,2≤k≤m

(6)

(7)

si,k=max(ci,(k-1),c(i-1),k), 2≤i≤n,2≤k≤m

(8)

ci,k=si,k+pi,k·xi

?i∈I,k∈K

(9)

Ci=ci,m,?i∈Io

(10)

(11)

(12)

ci,k≥ci,(k-1)+xipi,k,?i∈I,k∈K

(13)

ci,(k-1)≤si,k,?i∈Io,k∈K

(14)

c(i-1),k≤si,k,?i∈Io,k∈K

(15)

(16)

(17)

βi,k,t+γi,k,t≤1,?i∈I,k∈K,t∈T

(18)

yi,k,t=γi,k,t,?i∈I,k∈K,t∈T

(19)

式(5)計(jì)算拖期懲罰權(quán)重。式(6)與式(7)計(jì)算機(jī)器空閑時(shí)間。式(8)與式(9)分別計(jì)算開(kāi)始時(shí)間與完工時(shí)間。式(10)表示訂單i的總完工時(shí)間。式(11)表示生產(chǎn)效率的約束。式(12)表示交貨日期的約束。式(13)表示只有在第k-1階段處理了接受的訂單后，才能在第k階段處理接受的訂單。式(14)和式(15)表示任務(wù)不可中斷和機(jī)器不可被搶占，式(16)表示對(duì)訂單集中每個(gè)訂單進(jìn)行一次接受與拒絕，式(17)確保每個(gè)階段的所有訂單僅處理一次，式(18)確保每臺(tái)機(jī)器一次只能處理一個(gè)訂單，式(19)表示若γi,k,t=0，則第k個(gè)機(jī)器在t時(shí)刻關(guān)閉；否則γi,k,t=1。

2 節(jié)能混合禁忌搜索算法

本文提出的EHTS算法以NEH構(gòu)造啟發(fā)式算法產(chǎn)生初始解，提出了一種OAR編碼方式，同時(shí)設(shè)計(jì)了一種能耗調(diào)整策略，在保持加工所有接受訂單的最大完工時(shí)間不變下，使算法在求解的過(guò)程中利用分時(shí)電價(jià)的特點(diǎn)，實(shí)現(xiàn)對(duì)能耗的二次降低，與一種交貨期配置策略相結(jié)合，實(shí)現(xiàn)TNR的提高。

2.1 EHTS算法流程

根據(jù)以上描述，EHTS算法總體為三階段優(yōu)化過(guò)程，第一階段用于優(yōu)化總凈利潤(rùn)，第二階段作為節(jié)能調(diào)整階段，降低能耗成本，第三階段配置最佳交貨期，使總凈利潤(rùn)得到上升的空間。EHTS算法流程如圖1所示。

圖1 EHTS算法流程圖

針對(duì)相同交貨期下FPFSOAS問(wèn)題的EHTS算法流程描述如下：

1)以總凈利潤(rùn)作為目標(biāo)值，采用NEH啟發(fā)式算法生成初始解，初始化禁忌表；

2)對(duì)步驟1)后產(chǎn)生的初始解進(jìn)行禁忌搜索，每次迭代計(jì)算目標(biāo)值時(shí)使用訂單接受與拒絕方法重新編碼，更新局部最優(yōu)解和禁忌表；

3)檢驗(yàn)是否滿足終止準(zhǔn)則，若滿足則終止算法迭代，解碼得到相應(yīng)解決方案，否則返回步驟2)進(jìn)行下一次迭代；

4)解碼并保存最大總凈利潤(rùn)近優(yōu)解，并計(jì)算該解決方案中每個(gè)訂單每道工序的完工時(shí)間；

5)根據(jù)能耗調(diào)整策略，對(duì)高峰期兩邊的工序加工時(shí)間進(jìn)行二次調(diào)整。

6)在交貨期有效區(qū)間內(nèi)進(jìn)行交貨期配置。

2.2 節(jié)能調(diào)整

第一階段提出的基于OAR編碼方式與NEH產(chǎn)生初始解的改進(jìn)禁忌搜索方法，能夠以較低的耗電成本生成最大總凈利潤(rùn)的調(diào)度，但某些訂單仍會(huì)產(chǎn)生較高的電能消耗。使用能耗調(diào)整策略調(diào)整了第一階段優(yōu)化生成的解決方案，從而避免某些訂單的生產(chǎn)仍處于用電高峰期。

調(diào)整規(guī)則：從最后一個(gè)接受的訂單的最后一道工序開(kāi)始，并以逆序的方式從最后一個(gè)訂單調(diào)整到從用電高峰期開(kāi)始生產(chǎn)的第一個(gè)訂單，使用這種調(diào)整策略對(duì)非高峰期的所有訂單的加工順序重新調(diào)度，并將這些工序從高峰時(shí)段移開(kāi)，直到非高峰期的所有訂單完成調(diào)度。節(jié)能調(diào)整流程如圖2所示。

圖2 節(jié)能調(diào)整流程圖

2.3 交貨期配置策略

本文以最大化考慮能耗成本與拖期懲罰的總凈利潤(rùn)目標(biāo)，組成總凈利潤(rùn)的兩個(gè)指標(biāo)；能耗成本與拖期懲罰均與時(shí)間有關(guān)，企業(yè)可以根據(jù)總凈利潤(rùn)的優(yōu)化情況，向客戶提交不超過(guò)最晚交貨期的交付時(shí)間，因此交貨期配置策略會(huì)對(duì)總凈利潤(rùn)的再次提高具有一定很大的可能性。交貨期配置策略從上一階段已經(jīng)調(diào)整好的非高峰期生產(chǎn)的第一道工序開(kāi)始，保持非高峰期時(shí)段的工序不變，整體在交貨期區(qū)間內(nèi)移動(dòng)，根據(jù)設(shè)置好的移動(dòng)時(shí)間長(zhǎng)度，尋找到使得總凈利潤(rùn)增長(zhǎng)的交貨期。交貨期配置策略的流程如圖3所示。

圖3 交貨期配置策略

2.4 編碼方式

訂單接受與拒絕的編碼方式為π=(πOAS,πREJ)，即拒絕訂單的編碼拼接于接受訂單的編碼之后，其中πOAS,πREJ∈{1,2, ,n}。在每一次迭代中檢驗(yàn)每條解上各訂單的完工時(shí)間是否超過(guò)交貨期上限，最初I為根據(jù)針對(duì)最大完工時(shí)間和能耗成本的編碼方式產(chǎn)生的一條解，πOAS為一個(gè)空集合，πREJ為一個(gè)空拒絕訂單集，調(diào)度I中所有工件并檢驗(yàn)每一個(gè)訂單的總完工時(shí)間；若訂單i在交貨期上限之前完工，則從I刪除訂單i，并將訂單i的編碼從πOAS集合中的第一個(gè)有效位置開(kāi)始添加；否則將訂單i添加到πREJ；重復(fù)該過(guò)程，直到檢測(cè)到I編碼集合變?yōu)榭占稀?/p>

例如6訂單2工序的情況，且每個(gè)訂單具有相同交貨期，判斷每一個(gè)訂單的最大完工時(shí)間是否超過(guò)交貨期上限后，拒絕最后2個(gè)訂單，則該解表示為π={6,5,2,4,3,1}，其中接受訂單集合為{6,5,2,4}，拒絕訂單集合為{3,1}。

2.5 初始解的產(chǎn)生

對(duì)于置換流水線調(diào)度問(wèn)題，NEH 算法是目前最有效的啟發(fā)式算法之一[13]，它最早由文獻(xiàn)[14]提出。本文使用NEH算法產(chǎn)生初始解。初始訂單集的訂單按目標(biāo)值的降序排序，調(diào)度排序前兩個(gè)的訂單以獲得部分解決方案，依次將其余訂單插入當(dāng)前排序中所有空位，保留目標(biāo)值最優(yōu)的當(dāng)前排序，直至未排序的訂單數(shù)為零為止。NEH算法流程如圖4所示。

圖4 NEH算法流程

2.6 鄰域移動(dòng)方式

假設(shè)π為當(dāng)前解，通過(guò)兩點(diǎn)交換或插入方式獲得一定大小的當(dāng)前解鄰域N(π)。本文中選擇兩點(diǎn)交換和插入操作的概率相等。

兩點(diǎn)交換：隨機(jī)生成兩個(gè)位置，直接交換π中兩個(gè)位置上的個(gè)體以獲得N(π)；

前插/后插：將隨機(jī)位置上的個(gè)體插入到另一位置上的個(gè)體之前或之后。

2.7 禁忌表

禁忌表作為禁忌搜索的存儲(chǔ)結(jié)構(gòu)，可防止搜索過(guò)程中出現(xiàn)循環(huán)和避免陷入局部最優(yōu)。禁忌表的主要指標(biāo)為禁忌對(duì)象和禁忌長(zhǎng)度。為了避免算法迭代中出現(xiàn)重復(fù)移動(dòng)，將每次迭代的局部最優(yōu)解的鄰域操作放入禁忌表中，這些元素在下次搜索時(shí)將不會(huì)被考慮；禁忌表長(zhǎng)度為禁忌表中禁忌對(duì)象的最大值，其大小會(huì)影響算法效果，通過(guò)Taguchi方法調(diào)整禁忌表長(zhǎng)度。

2.8 藐視準(zhǔn)則與終止準(zhǔn)則

在本文中，當(dāng)禁忌搜索算法中出現(xiàn)候選解全部被禁忌，或者某個(gè)禁忌候選解的適應(yīng)度值優(yōu)于當(dāng)前最好解的適應(yīng)度值，則解禁某個(gè)禁忌候選解作為新的當(dāng)前最好解。

本文將最大迭代次數(shù)設(shè)置為終止準(zhǔn)則。

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

所有實(shí)驗(yàn)在環(huán)境Intel? CoreTMi5-4300U，主頻為2.2 GHz，內(nèi)存為16 GB的個(gè)人電腦上運(yùn)行，編程環(huán)境為Matlab R2017a。實(shí)驗(yàn)設(shè)定訂單數(shù)量n為10、20、30、40或50，工序數(shù)m為6、8、10，組成15種例如10/6，20/8，30/10等形如n/m的訂單規(guī)模，15種規(guī)模對(duì)應(yīng)150個(gè)隨機(jī)算例，每個(gè)算例運(yùn)行30次。根據(jù)文獻(xiàn)[15]，訂單加工時(shí)間pi,k在[0.3, 2,5]中隨機(jī)生成的，機(jī)器的不同運(yùn)行方式的能耗在[2,20]內(nèi)隨機(jī)產(chǎn)生。工廠為24小時(shí)輪班式工作制，分時(shí)電價(jià)如表2所示。每種規(guī)模里所有訂單的相同固定收入Ri在[1 000,2 000]內(nèi)隨機(jī)產(chǎn)生。本文用于測(cè)試同一算例的所有算法的終止條件為最大迭代次數(shù)Max_Iter=200。

表1 電鈴故障模式

交貨期根據(jù)所有訂單的總加工時(shí)間平均值產(chǎn)生，如式(20)所示：

(20)

3.1 算法性能對(duì)比

大量研究表明，遺傳算法(GA,genetic algorithm)、禁忌搜索算法(TS,tabu search)、迭代局部搜索算法(ILS,iterated local search)等用于求解傳統(tǒng)PFSP是有效的。通過(guò)對(duì)比本文所提出的EHTS算法、僅加入OAR編碼方式的改進(jìn)禁忌搜索(ITS-OAR,improved tabu search-OAR)與傳統(tǒng)TS算法在優(yōu)化PFSOAS模型下的算法性能，分析EHTS算法的優(yōu)勢(shì)；并且通過(guò)EHTS優(yōu)化隨機(jī)實(shí)例，分析節(jié)能調(diào)整與交貨期配置策略的有效性。

由于元啟發(fā)式算法的性能對(duì)參數(shù)敏感，因此使用Taguchi正交實(shí)驗(yàn)設(shè)計(jì)法對(duì)EHTS、ITS-OAR、TS進(jìn)行算法調(diào)參。調(diào)整后參數(shù)如表3所示，其中n為訂單總數(shù)量，max{}為取最大值函數(shù)，round{}為取整函數(shù)，sqrt{}為開(kāi)平方函數(shù)。

表3 算法調(diào)整后的參數(shù)

表4給出了15種規(guī)模實(shí)例問(wèn)題在傳統(tǒng)TS、ITS-OAR、EHTS的優(yōu)化性能對(duì)比，指標(biāo)分別為總凈利潤(rùn)平均值、拒絕訂單數(shù)、能耗成本平均值以及相應(yīng)的總凈利潤(rùn)增長(zhǎng)率、能耗成本降低率。TNRbest為EHTS優(yōu)化后的訂單總凈利潤(rùn)值，TECbest為加工EHTS優(yōu)化解決方案所耗費(fèi)的電費(fèi)成本?？們衾麧?rùn)增長(zhǎng)率(IRTNR)與能耗成本降低率(DRTEC)分別如式(21)和式(22)。其中，TNR與TEC分別為TS、ITS-OAR優(yōu)化后的總凈利潤(rùn)值與能耗成本值?？紤]到算例總數(shù)和規(guī)模總數(shù)較大，對(duì)150個(gè)算例運(yùn)行30次后的優(yōu)化結(jié)果取平均值進(jìn)行統(tǒng)計(jì)實(shí)驗(yàn)。根據(jù)表4所繪制的不同工序下三種算法性能對(duì)比如圖5所示。

(21)

(22)

從圖5可以看出，在優(yōu)化PFSOAS問(wèn)題方面，EHTS算法的優(yōu)化性能更優(yōu)于傳統(tǒng)TS算法和ITS-OAR算法。根據(jù)表4，從訂單總利潤(rùn)的角度來(lái)看，EHTS算法對(duì)比傳統(tǒng)TS算法，其總凈利潤(rùn)值可以提高5%～11%左右，平均提高大約8%；EHTS算法比ITS-OAR算法優(yōu)化得到的總凈利潤(rùn)值高1%～7%左右，平均提高大約4%；說(shuō)明通過(guò)能耗調(diào)整和交貨期配置策略，可以使得企業(yè)訂單總利潤(rùn)值顯著提高。由于該目標(biāo)中帶有拖期懲罰項(xiàng)，會(huì)與總凈利潤(rùn)增長(zhǎng)相互制約，隨著訂單規(guī)模的增長(zhǎng)，某些訂單的生產(chǎn)仍處于高峰時(shí)段，總凈利潤(rùn)增長(zhǎng)幅度一直保持在5%左右。從能源消耗成本的角度來(lái)看，EHTS算法比前兩種算法具有顯著優(yōu)勢(shì)，能耗成本減少大約9%。拒絕訂單數(shù)也相應(yīng)減少。因此EHTS算法有著較好的有效性和穩(wěn)定性。

圖5 3種算法的性能比較

表4 不同規(guī)模下不同算法的優(yōu)化結(jié)果

4 結(jié)束語(yǔ)

本文在傳統(tǒng)能效優(yōu)化的置換流水車間調(diào)度能耗模型角度上加入了訂單接受與調(diào)度，針對(duì)問(wèn)題的特殊性，提出了一種新型的節(jié)能禁忌搜索算法，提高傳統(tǒng)算法對(duì)企業(yè)總凈利潤(rùn)和能耗成本的優(yōu)化效果，訂單總凈利潤(rùn)平均提高了13%，拒絕訂單數(shù)與能耗成本也相應(yīng)減少。通過(guò)NEH構(gòu)造啟發(fā)式產(chǎn)生初始解、節(jié)能調(diào)整策略的改進(jìn)，可提高算法搜索效率，改善初始解質(zhì)量，通過(guò)多種算法的性能對(duì)比，較單一算法相比，該EHTS算法具有較強(qiáng)全局搜索能力的優(yōu)勢(shì)，具有一定的實(shí)用價(jià)值。本文的研究?jī)?nèi)容和結(jié)論將推動(dòng)綠色制造領(lǐng)域通過(guò)科學(xué)可行的調(diào)度方法，實(shí)現(xiàn)節(jié)能降耗、高效益的生產(chǎn)目標(biāo)，具有一定的實(shí)踐意義。