張雨晨, 熊福力

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

0 引言

隨著綠色制造的全球化與生產(chǎn)力的提高，能源需求量日益增加，能源消耗造成的環(huán)境問題日益突出[1]。通過節(jié)能與環(huán)境保護的手段可有效地推進可持續(xù)發(fā)展政策，具有顯著的經(jīng)濟效益和社會效益。為了滿足綠色生產(chǎn)和客戶滿意度的要求，企業(yè)必須同時考慮訂單接受和生產(chǎn)計劃。訂單接受與調(diào)度(OAS,order acceptance and scheduling)問題決定接受哪些訂單并決策接受訂單的加工順序，根據(jù)文獻[2-3]的研究，它有著與大多數(shù)車間調(diào)度問題相同的特點。置換流水車間調(diào)度問題(PFSP,permutation flow shop problem)是流水車間調(diào)度問題中一類典型的子問題，也是調(diào)度問題的研究熱點[4]。它通常側(cè)重于優(yōu)化生產(chǎn)效率指標，如總完成時間、拖期、加權(quán)完工時間等[5-6]。而能源效率優(yōu)化是企業(yè)實現(xiàn)可持續(xù)發(fā)展的關(guān)鍵因素之一，因此，進行訂單選擇與生產(chǎn)調(diào)度的統(tǒng)一決策，使企業(yè)能夠獲得更加穩(wěn)定有效的決策方案。車間能效優(yōu)化相關(guān)研究已有杰出成果，文獻[7-8]提出同時優(yōu)化能源消耗與總完工時間的多目標數(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)問題，旨在最大化企業(yè)生產(chǎn)總凈利潤(TNR,total net revenue)。本文于傳統(tǒng)禁忌搜索的基礎(chǔ)上，提出了一種節(jié)能混合禁忌搜索算法(EHTS,energy-saving hybrid tabu search)，它整合了一種能耗調(diào)整策略與交貨期配置策略，實現(xiàn)對能耗的二次降低，加入了一種訂單接受與拒絕(OAR,order acceptance and rejection)的編碼方式，并設(shè)計了NEH構(gòu)造啟發(fā)式算法產(chǎn)生禁忌搜索算法的初始解，以改善算法優(yōu)化質(zhì)量。通過上述改進，提高了算法解決本文所提出的特殊的PFSOASP的尋優(yōu)能力。通過大量實際算例的統(tǒng)計實驗，分析了該算法的優(yōu)異性能，接著描述了所提出的PFSOAS模型，并且通過實驗分析了EHTS算法求解PFSOAS問題的有效性與優(yōu)越性。

1 問題描述

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

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

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

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

1.2 PFSOAS模型

目標函數(shù)：

maxTNR

(1)

(2)

其中:TEC為對接受訂單進行加工的總能源成本，ECi為加工訂單i時所需的機器能耗。

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

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

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

2.1 EHTS算法流程

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

圖1 EHTS算法流程圖

針對相同交貨期下FPFSOAS問題的EHTS算法流程描述如下：

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

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

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

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

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

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

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

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

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

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

2.3 交貨期配置策略

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

圖3 交貨期配置策略

2.4 編碼方式

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

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

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

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

圖4 NEH算法流程

2.6 鄰域移動方式

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

兩點交換：隨機生成兩個位置，直接交換π中兩個位置上的個體以獲得N(π)；

前插/后插：將隨機位置上的個體插入到另一位置上的個體之前或之后。

2.7 禁忌表

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

2.8 藐視準則與終止準則

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

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

3 實驗結(jié)果與分析

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

表1 電鈴故障模式

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

(20)

3.1 算法性能對比

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

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

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

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

(21)

(22)

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

圖5 3種算法的性能比較

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

4 結(jié)束語

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