一種用于PFSP節能優化的混合禁忌搜索算法

張雨晨, 熊福力

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

0 引言

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

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

1 問題描述

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

1.1 相關假設與參數說明

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

表1 模型參數說明

1.2 PFSOAS模型

目標函數：

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

2 節能混合禁忌搜索算法

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

2.1 EHTS算法流程

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

圖1 EHTS算法流程圖

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

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

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

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

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

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

6)在交貨期有效區間內進行交貨期配置。

2.2 節能調整

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

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

圖2 節能調整流程圖

2.3 交貨期配置策略

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

圖3 交貨期配置策略

2.4 編碼方式

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

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

2.5 初始解的產生

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

圖4 NEH算法流程

2.6 鄰域移動方式

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

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

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

2.7 禁忌表

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

2.8 藐視準則與終止準則

在本文中，當禁忌搜索算法中出現候選解全部被禁忌，或者某個禁忌候選解的適應度值優于當前最好解的適應度值，則解禁某個禁忌候選解作為新的當前最好解。

本文將最大迭代次數設置為終止準則。

3 實驗結果與分析

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

表1 電鈴故障模式

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

(20)

3.1 算法性能對比

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

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

表3 算法調整后的參數

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

(21)

(22)

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

圖5 3種算法的性能比較

表4 不同規模下不同算法的優化結果

4 結束語

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