考慮時差電價機器能耗的非等同并行機調度研究

梁鵬 郝剛 郭建華 吳玉婷 何娃

摘要：利用時差電價減少能耗損失的同時保證最大化生產效率，是高能耗制造企業急需解決的問題之一。將其生產調度過程抽象為一種考慮時差電價機器能耗的非等同并行機調度問題，對此提出一種基于右移局部搜索的蟻群優化方法以實現求解方案。最后根據仿真實驗得到蟻群優化算法的最優參數用于實驗對比，從對比實驗結果的分析表明，算法可以減少生產過程的能耗成本和拖期成本.

關鍵詞：能耗成本;拖期成本;非等同并行機;蟻群算法

中圖分類號：TP301? ? ?文獻標識碼：A

文章編號：1009-3044（2019）20-0272-03

開放科學（資源服務）標識碼（OSID）：

Abstract： Aiming at hugeous machine warm-up energy consumption and serious waste product switching in aluminium extrusion workshop， we abstract it as a class of unrelated parallel machine scheduling problem with energy and tardiness cost，and an ant optimization algorithm based on product switching energy consumption heuristic rule is presented.Optimal parameters of algorithm are defined via a split-plot design for generating test data.A lot of simulation experiments prove the proposed algorithm decrease energy consumption effectively.

Key words： energy consumption; Total tardiness; Unrelated parallel machine

在現實生產制造中，不同效率的機器（非等同并行機）往往同時運行，這給生產計劃制定帶來了極大的困難。因此，在保證企業正常生存條件下，降低非等同并行機生產過程的能源消耗和降低生產成本，是制造業關注的核心問題之一[9].早在2004年，Pfund[3]等人就證明了最大化完工產品數的非等同并行機調度問題屬于NP難問題.Allahverdi等[4]在2008年的帶準備時間的調度綜述文獻對單機、并行機、流水車間調度進行了研究，研究發現以最小化拖期成本的調度方案傾向于將同種類型的產品成批處理.Liaw等[5]和Rocha[6]等使用分支界限法優化帶準備時間的非等同并行機調度問題，然而求解方法計算復雜度過高，難以適用于數量較大的調度問題.Weng等[7]使用7種啟發式規則對帶準備時間的非等同并行機調度進行求解[22]。

綜上所述，上述以非等同并行機能耗調度為研究目標的文獻，通常將機器調度和工件調度分開獨立進行以降低計算復雜度，大大減少了解空間的搜索范圍，然而單純將解空間分割會導致算法性能的下降。為此，本文提出一種右移鄰域搜索策略的蟻群算法，用于求解考慮時差電價機器能耗的非等同并行機調度問題，實驗結果表明，該方法減少了解空間的搜索范圍的同時，提升了算法的精度。

1問題描述與數學模型

對于本文研究的非等同并行機調度問題描述如下：有n個工件由m臺非等同并行機中任一臺完成加工，安排在第j臺機器上加工的工件數量為Hj，每個工件i都有獨立的到達時間ri和交貨時間di，并根據不同的加工機器有不同的加工時間tij，第i個工件的單位時間拖期成本為pi1，第j臺機器的單位時間運行能耗成本和單位時間待機能耗成本分別為pj2和pj3，w1和w2分別表示工件拖期成本系數和機器能耗成本系數，f（t）表示不同時間段的電力價格。給出下面假設條件：機器在開始加工第一個工件時開啟，加工過程不允許搶占或中斷，每臺機器任一時間只能加工一個工件。該問題的數學模型描述如下：

決策標量：

2求解算法

2.1信息素及其初始化

根據螞蟻的兩階段尋徑過程，信息素分為τj和τij兩部分，τj表示機器Mj上的信息素，初始值為[τj=1M];τij表示機器Mj和工件[i]之間的信息素，初始值τij=0。

2.2解的構建

首先選擇最早可以獲取的機器[j*]，然后選擇在機器上工件拖期成本最小的工件[i*]，最后根據工件[i]選擇機器能耗成本最小的機器 ]。通過機器再選擇的過程將拖期成本子目標與機器能耗成本子目標聯系起來，提升算法性能。

1. 選擇機器

為了增加搜索隨機性，給定參數[gm0∈[0，1]]和隨機數[gm]，如果[gm

2. 選擇工件

根據工件個數，用禁忌表tabuk （k=1，2，…，n）記錄當前螞蟻所選擇的工件，禁忌表隨著螞蟻尋徑作動態調整。給定參數[gi0∈[0，1]]和隨機數[gi]，如果[gi

（t）]是啟發式函數，反映機器[j*]上加工工件[i]的拖期成本，優先選擇綜合成本最小的工件在該機器上生產;α是信息啟發因子，反映了蟻群運動過程積累信息對當前螞蟻選擇的影響;β是期望啟發因子，表示啟發式信息在螞蟻選擇中的重視程度.

3.選擇機器

對于工件 而言，最早可以獲得的機器[j*]并不一定是加工該工件能耗最小的機器，因此采用迭代的方法，再次根據機器加工能耗最小選擇機器

為螞蟻一次尋徑的結果，即選擇工件[i*]在機器[j**]上進行加工。螞蟻反復進行尋徑，直到所有的工件加工完成，工件的加工序列即是解的序列。

2.3鄰域搜索

研究表明，在蟻群算法中加入鄰域搜索算法，不僅可以提高解的精度，并且可以大大減少蟻群計算的循環次數.對于具有時差電價的并行機調度問題，提出一種右移鄰域搜索策略（Right-Shift Local Search），策略如下所示：

2.4 信息素更新

當螞蟻遍歷完所有的工件后，需要對當前尋徑的結果上的信息量進行調整k，根據下面規則式（11）進行調整：

其中，1-ρ是信息素殘留因子，表示當前迭代的尋徑結果對整個蟻群尋徑的影響程度，Δτij（t）表示本次迭代中信息素增量。Q表示信息素強度，在一定程度上影響算法的收斂速度，E（t）表示螞蟻本次迭代的尋徑結果。

3 數值仿真實驗

3.1算例設計

影響算法性能的影響因子有：機器數量m、工件數量n、工件的加工時間tij、工件的到達時間ri、工件交貨時間di和單位能耗的比率（單位時間機器開關機能耗成本與單位時間機器待機能耗的比值），每個因子的設置如表1所示。

工件的加工時間tij服從均勻分布，記為tij=U[2，30]和tij=U[2，50]兩種，工件的到達時間ri、交貨時間di可根據加工時間計算得到：[ri=j=1mtij/m]，[di=cj=1mtij/m]，其中c表示交貨寬裕系數。本文采用單位時間機器生產能耗成本與單位時間機器待機能耗的比值pj2/pj3來反映機器能耗比例.單位時間拖期成本pi1和單位時間能耗成本pj2取從1到10之間的隨機整數randi（10，1），工件拖期成本系數w1和機器能耗成本系數w2取從0到1之間的隨機數且w1+ w2=1。根據表1的影響因子共組成24種仿真算例。時差電價f（t）用下式表示：

3.2仿真結果及分析

本節實驗所用算法參數為[α=1]，[β=4]，[Q=80]，[ρ=0.75]，[m=100]。為了驗證右移鄰域搜索策略的有效性，將蟻群算法（ACO）、右移鄰域搜索策略（Right-Shift Local Search RSLS）組合進行比較，每個算例進行10次仿真實驗取其平均值來評價算法的有效性.以上所有算法采用Matlab R2012b仿真軟件，并在CPU為Intel Core i5 2.30GHz，內存4G的計算機上進行仿真試驗，能耗結果[Emin]作為結果評價指標。

從表2中可以看出，單純使用蟻群算法的效果不如使用了右移鄰域搜索策略的蟻群算法，右移鄰域搜索策略方法提升了約20%。

4 結束語

針對生產中機器開關能源消耗大、拖期嚴重等問題，建立了以綜合能耗成本和拖期懲罰成本最小化為目標的非同等并行機優化調度模型，提出了基于右移鄰域搜索策略的蟻群優化算法，對算例的仿真及結果分析表明算法的有效性。

參考文獻：

[1] 侯彬. 考慮機器開關的并行機調度研究[J]. 工業工程與管理， 2011， 16（2）：60-64.

[2] Keskinturk T， Yildirim M B， Barut M。An Ant Colony Optimization Algorithm for Load Balancing in Parallel Machines with Sequence-Dependent Setup Times [J]。Computers & Operations Research， 2012， 39（6）： 1225-1235.

[3] Pfunda M， Fowler J W， Guptac J N D。A Survey of Algorithms for Single and Multi-Objective Unrelated Parallel Machine Deterministic Scheduling Problems [J]。Journal of the Chinese Institute of Industrial Engineers， 2004， 21（3）：230-241.

[4]Allahverdi A， Ng C， Cheng T， Kovalyov MY。A survey of scheduling problems with setup times or costs。European Journal of Operational Research 2008;187：985–1032.

[5]Liaw C， Lin Y， Cheng C， Chen M。Scheduling unrelated parallel machines to minimize total weighted tardiness。Computers&Operations Research 2003;30：1777–89.

[6]Rocha PL， Ravetti MG， Mateus GR， Pardalos PM。Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setuptimes。Computers&Operations Research 2008; 35：1250–1264.

[7]Weng MX， Lu J， Ren H。Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective。International Journal of Production Economics 2001; 70：215–26.

【通聯編輯：梁書】