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

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

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

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

中圖分類號：TP301? ? ?文獻標(biāo)識碼：A

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

開放科學(xué)（資源服務(wù)）標(biāo)識碼（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

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

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

1問題描述與數(shù)學(xué)模型

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

決策標(biāo)量：

2求解算法

2.1信息素及其初始化

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

2.2解的構(gòu)建

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

1. 選擇機器

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

2. 選擇工件

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

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

3.選擇機器

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

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

2.3鄰域搜索

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

2.4 信息素更新

當(dāng)螞蟻遍歷完所有的工件后，需要對當(dāng)前尋徑的結(jié)果上的信息量進行調(diào)整k，根據(jù)下面規(guī)則式（11）進行調(diào)整：

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

3 數(shù)值仿真實驗

3.1算例設(shè)計

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

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

3.2仿真結(jié)果及分析

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

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

4 結(jié)束語

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

參考文獻：

[1] 侯彬. 考慮機器開關(guān)的并行機調(diào)度研究[J]. 工業(yè)工程與管理， 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.

【通聯(lián)編輯：梁書】