孟磊磊 張超勇 詹欣隆 洪 輝 羅 敏

1.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，4300742.湖北汽車工業(yè)學(xué)院電氣與信息工程學(xué)院，十堰，442002

0 引言

據(jù)統(tǒng)計(jì)，我國擁有機(jī)床800多萬臺(tái)，每臺(tái)機(jī)床平均功率按10 kW算，總功率超過8 000萬kW，耗電量是總裝容量為2 250萬kW的三峽電站的3倍多[1]。然而，機(jī)床在實(shí)際生產(chǎn)中，大部分時(shí)間處于空載狀態(tài)，據(jù)統(tǒng)計(jì)，機(jī)床大約80%的能量消耗在待機(jī)以及關(guān)機(jī)重啟過程中，真正用于加工的能量占比不足20%[2]，GUTOWSKI等[3]給出的一條汽車自動(dòng)生產(chǎn)線的能量效率只有14.8%。機(jī)床處于空閑等待狀態(tài)所消耗的能量為無效能耗，節(jié)能調(diào)度的主要目的就是減少這部分能耗。

并行機(jī)調(diào)度問題(parallel machine scheduling problem，PMSP)在實(shí)際生產(chǎn)制造過程中比較常見。不相關(guān)并行機(jī)調(diào)度問題(unrelated parallel machine scheduling problem, UPMSP) 是PMSP中最普遍的一類問題, 工件的加工時(shí)間取決于所分配的機(jī)床，UPMSP已經(jīng)被證明為NP-hard問題。目前，對(duì)UPMSP的研究主要集中在最小化最大完工時(shí)間、成本、交貨率等方面[4-6]，而對(duì)車間能耗方面不太重視。

當(dāng)機(jī)床連續(xù)待機(jī)時(shí)間較長時(shí)，對(duì)于允許中途關(guān)機(jī)的機(jī)床可以通過關(guān)機(jī)/重啟策略來減小機(jī)床待機(jī)能耗。關(guān)機(jī)/重啟策略最早由MOUZON等[2]提出，通過對(duì)非瓶頸機(jī)床實(shí)行關(guān)機(jī)/重啟策略，避免機(jī)床長時(shí)間處于空閑狀態(tài)，可以節(jié)約80%的待機(jī)能耗。隨后關(guān)機(jī)/重啟策略逐步被應(yīng)用于單機(jī)[7]、并行機(jī)[8-11]調(diào)度研究。

針對(duì)UPMSP，文獻(xiàn)[12]以加權(quán)拖期成本和能耗成本之和為目標(biāo)，提出了求解該問題的多種啟發(fā)式規(guī)則方法。文獻(xiàn)[13]研究了并行機(jī)批量調(diào)度問題，以最小化能耗和最大完工時(shí)間為目標(biāo)，提出了一種基于Pareto的多目標(biāo)蟻群優(yōu)化算法。針對(duì)加工時(shí)間可控的UPMSP，文獻(xiàn)[14]以最小化能耗和最大完工時(shí)間為目標(biāo)，提出了求解該問題的多目標(biāo)協(xié)同果蠅優(yōu)化算法；文獻(xiàn)[15]同時(shí)以最小化加工能耗和最大完工時(shí)間為目標(biāo)，提出了一種高效的多目標(biāo)memetic差分進(jìn)化算法。

UPMSP可以通過精確方法，如混合整數(shù)規(guī)劃(mixed integer programming ,MIP)模型、分支定界等[16]方法求解，也可通過元啟發(fā)式方法(如遺傳算法[17]、蟻群算法[8]、分布估計(jì)算法[5]等)和啟發(fā)式規(guī)則[12]等方法求解。精確算法求解速度慢，對(duì)于中大規(guī)模問題甚至很難求出問題的可行解，但是針對(duì)小規(guī)模問題，精確算法可以求出調(diào)度問題的最優(yōu)方案，而啟發(fā)式方法和元啟發(fā)式方法為近似求解方法，雖然在較短時(shí)間內(nèi)可以得出問題的可行解，但解的質(zhì)量不能保證為最優(yōu)解。MIP模型是認(rèn)識(shí)調(diào)度問題的基礎(chǔ)，是探索與挖掘調(diào)度分配規(guī)則的關(guān)鍵所在[18]。高效的MIP模型可以在相同的時(shí)間內(nèi)得到更好的計(jì)算結(jié)果，因此構(gòu)建高效MIP模型具有重要意義。

本文結(jié)合UPMSP自身的特點(diǎn)，以節(jié)能為目標(biāo)，考慮關(guān)機(jī)/重啟策略，提出5個(gè)解決該問題的MIP模型，并從建模過程、線性化過程、模型尺寸復(fù)雜度以及計(jì)算復(fù)雜度等方面對(duì)5個(gè)MIP模型進(jìn)行對(duì)比分析。

1 問題描述

1.1 參數(shù)定義

參數(shù)定義見表1。其中，為保證每臺(tái)機(jī)床上都安排工件加工，每臺(tái)機(jī)床最多可安排n-m+1個(gè)工件，每臺(tái)機(jī)床最大位置數(shù)為n-m+1。

1.2 UPMSP描述

UPMSP可描述為:n個(gè)工件在m臺(tái)機(jī)床上加工，每個(gè)工件只有一道工序，且同一工件在不同機(jī)床上的加工時(shí)間是不同的。該問題滿足以下基本假設(shè): 不同工件的釋放時(shí)間、交貨期是不同的；所有工件必須在規(guī)定的交貨期內(nèi)完成加工；機(jī)床在0時(shí)刻處于可用狀態(tài)；所有工件在所有機(jī)床上的加工時(shí)間、加工功率等是已知的；同一機(jī)床上不同工件間的轉(zhuǎn)換時(shí)間忽略不計(jì)；任一工件可在任一機(jī)床上加工；工件一旦開始加工則不可中斷；對(duì)于每個(gè)機(jī)床，在同一時(shí)刻最多只能加工一個(gè)工件；對(duì)于每個(gè)工件，在同一時(shí)刻最多只能在一臺(tái)機(jī)床上加工。

表1 參數(shù)定義

UPMSP的目的就是合理地將工件安排在機(jī)床上,且確定工件在機(jī)床上的加工順序以達(dá)到某些調(diào)度目標(biāo)，如最大完工時(shí)間、成本、能耗等的最優(yōu)。本文研究UPMSP節(jié)能調(diào)度問題，目標(biāo)為最小化車間總能耗。

1.3 車間能耗分析與建模

車間能耗主要包括機(jī)床能耗、公共能耗兩部分，機(jī)床能耗進(jìn)一步可分為加工能耗及待機(jī)能耗。

1.3.1加工能耗

(1)

總加工能耗

(2)

因?yàn)槊總€(gè)工件只能選擇在一臺(tái)機(jī)床上加工，故引入0-1變量Yi,k，如果工件i選擇在機(jī)床k上加工，則Yi,k=1，否則，Yi,k=0。

1.3.2待機(jī)能耗

待機(jī)能耗是指由于上一工件已經(jīng)加工完，下一個(gè)工件還沒有到達(dá)，從而使機(jī)床出現(xiàn)閑置狀態(tài)所消耗的能量，機(jī)床k的第t到t+1位置之間的待機(jī)能耗

(3)

式中，F(xiàn)k,t為機(jī)床k上第t個(gè)位置的結(jié)束時(shí)間；Sk,t為機(jī)床k上第t個(gè)位置的開始時(shí)間。

機(jī)床k的總待機(jī)能耗

(4)

所有機(jī)床總待機(jī)能耗

(5)

1.3.3公共能耗

公共能耗是指車間公共設(shè)施的能源消耗，是指為了維持車間正常運(yùn)行所必須消耗的能源，主要包括照明、通風(fēng)、供暖、空調(diào)等耗能，其值為公共功率P0與最大完工時(shí)間Cmax的乘積，可表示為

EC=P0Cmax

(6)

1.3.4車間總能耗

車間總能耗ETC為總加工能耗、待機(jī)能耗以及公共能耗之和:

(7)

當(dāng)機(jī)床的一個(gè)連續(xù)待機(jī)時(shí)間段Sk,t+1-Fk,t比較長時(shí)，可以實(shí)施關(guān)機(jī)/重啟策略，節(jié)約無用待機(jī)能耗，實(shí)現(xiàn)關(guān)機(jī)/重啟策略的最短待機(jī)時(shí)間，即空載平衡時(shí)間

(8)

空載平衡時(shí)間Tk，B表示機(jī)床在空載的過程中，當(dāng)空載的時(shí)間不小于一次關(guān)機(jī)/重啟策略所需要的時(shí)間Tk，且機(jī)床空載所消耗的能耗不小于機(jī)床一次關(guān)機(jī)/重啟所需要的能耗Ek,min時(shí)才可實(shí)施關(guān)機(jī)/重啟策略。

當(dāng)引入關(guān)機(jī)/重啟策略后，待機(jī)段能耗Ek,t可表示為

(9)

當(dāng)引入關(guān)機(jī)/重啟策略后，車間總能耗

(10)

其中，Zk,t為0-1變量，用來控制是否實(shí)行關(guān)機(jī)/重啟策略，當(dāng)Zk,t=1時(shí)，表示在機(jī)床k的第t到t+1位置之間實(shí)行關(guān)機(jī)/重啟策略，此時(shí)Ek,t為一次關(guān)機(jī)/重啟所需要的能耗Ek,min；否則,Zk,t=0，Ek,t根據(jù)具體待機(jī)時(shí)間而定。

2 混合整數(shù)規(guī)劃模型構(gòu)建

目前關(guān)于UPMSP的MIP模型較多, 但是大部分是針對(duì)時(shí)間目標(biāo)的[16-17,19]。本文針對(duì)UPMSP自身的特點(diǎn)，以節(jié)能為目標(biāo)，同時(shí)考慮關(guān)機(jī)/重啟策略，基于機(jī)床位置的Wagner建模思想[20]，建立5個(gè)考慮關(guān)機(jī)/重啟策略的MIP模型，其中2個(gè)為基于空閑時(shí)間的非線性模型，3個(gè)為線性模型(2個(gè)線性模型通過將2個(gè)非線性模型引入中間決策變量進(jìn)行線性化處理得到，第3個(gè)線性模型基于空閑能耗的建模思想直接構(gòu)建)。

基于機(jī)床位置的Wagner建模方法建立在“機(jī)床位置”概念上，即將一個(gè)機(jī)床按照時(shí)間先后分成若干個(gè)段，每一段即成為一個(gè)位置，一個(gè)位置最多只能安排一個(gè)工件，因此，只要確定了工件與機(jī)床位置的對(duì)應(yīng)關(guān)系，工件在機(jī)床上的排序即可得到。

5個(gè)MIP模型按照建模思路可進(jìn)一步細(xì)分為兩類：第一類是基于空閑時(shí)間的建模方法，包括非線性模型1、線性模型1與非線性模型2、線性模型2；第二類是基于空閑能耗的建模方法，包括線性模型3?；诳臻e時(shí)間的建模方法是指機(jī)床待機(jī)能耗通過待機(jī)段時(shí)間與待機(jī)功率來計(jì)算，而基于空閑能耗的建模方法直接定義空閑段能耗決策變量。

因?yàn)榛赪agner建模方法的MIP模型必須引入機(jī)床位置占用變量Xi,k,t，Xi,k,t與機(jī)床選擇變量Yi,k存在對(duì)應(yīng)關(guān)系，因此本文5個(gè)模型將不再使用Yi,k，以減少0-1決策變量數(shù)，降低模型復(fù)雜度。對(duì)應(yīng)關(guān)系如下：

(11)

2.1 模型1

模型1包括非線性模型1以及線性模型1。其中線性模型1通過引入中間決策變量將非線性模型1的目標(biāo)函數(shù)進(jìn)行線性化處理之后得到。

非線性模型1有Xi,k,t、Zk,t、Sk,t及Cmax4個(gè)決策變量，其中，Xi,k,t用于確定工件的機(jī)床位置選擇，Zk,t用于確定在機(jī)床相應(yīng)位置是否實(shí)行關(guān)機(jī)/重啟操作，Sk,t和Cmax為連續(xù)決策變量。Xi,k,t和Zk,t的表達(dá)式分別如下：

為了將非線性目標(biāo)函數(shù)進(jìn)行線性化處理，引入中間決策變量Ai,k,t、Uk,t和Wk,t，其中Uk,t、Wk,t為連續(xù)決策變量，Ai,k,t為0-1中間決策變量，因此線性模型1共有Xi,k,t、Zk,t、Sk,t、Cmax、Ai,k,t、Uk,t和Wk,t7個(gè)決策變量。

非線性模型1的目標(biāo)函數(shù)為

(12)

式(12)中，等號(hào)右邊第一項(xiàng)表示機(jī)床總空閑能耗(待機(jī)或關(guān)機(jī)/重啟)，第二項(xiàng)為機(jī)床總加工能耗，第三項(xiàng)為公共能耗。由式(12)可以看出，目標(biāo)函數(shù)是非線性的，存在決策變量相乘的情況，如(1-Zk,t)Sk,t+1、(1-Zk,t)Sk,t以及(1-Zk,t)Xi,k,t，非線性模型求解非常復(fù)雜。本文引入中間決策變量Uk,t、Wk,t、Ai,k,t,用Uk,t+1代替(1-Zk,t)Sk,t+1、Wk,t代替(1-Zk,t)Sk,t、Ai,k,t代替(1-Zk,t)Xi,k,t，通過添加相應(yīng)的約束，實(shí)現(xiàn)非線性模型到線性模型的轉(zhuǎn)換。

線性模型1的目標(biāo)函數(shù)為

(13)

約束條件為

(14)

(15)

(16)

ri≤Sk,t+M(1-Xi,k,t) ?t∈T

(17)

(18)

Sk,t≥0 ?t∈T

(19)

(20)

(21)

(22)

(23)

Uk,t+1≥Sk,t+1-MZk,t?t∈T1

(24)

Uk,t+1≤Sk,t+1+MZk,t?t∈T1

(25)

Uk,t+1≤M(1-Zk,t) ?t∈T1

(26)

Uk,t≥0 ?t∈T

(27)

Wk,t≥Sk,t-MZk,t?t∈T1

(28)

Wk,t≤Sk,t+MZk,t?t∈T1

(29)

Wk,t≤M(1-Zk,t) ?t∈T1

(30)

Wk,t≥0 ?t∈T1

(31)

Ai,k,t≤Xi,k,t?t∈T1

(32)

Ai,k,t≤1-Zk,t?t∈T1

(33)

Ai,k,t≥Xi,k,t-Zk,t?t∈T1

(34)

式(14)～式(34)中，?i∈I，?k∈K。式(14)表示任一工件只能選擇在一個(gè)機(jī)床上加工，且只占用該機(jī)床的一個(gè)位置；式(15)表示任一機(jī)床的任一位置最多只能安排一個(gè)工件加工；式(16)表示任一機(jī)床的位置按照先后順序安排工件加工；式(17)表示工件只能在到達(dá)之后才可以開始加工；式(18)表示工件必須在交貨期內(nèi)完成加工；式(19)約束決策變量范圍；式(20)表示最大完工時(shí)間約束；式(21)、式(22)表示關(guān)機(jī)/重啟策略約束，約束當(dāng)機(jī)床k的t到t+1位置間存在關(guān)機(jī)/重啟策略時(shí)，即Zk,t=1, 第t+1位置的開始時(shí)間與第t位置的開始時(shí)間加上該位置的加工時(shí)間之差必不小于機(jī)床k的空載平衡時(shí)間Tk,B,否則，不存在關(guān)機(jī)/重啟策略；由于平時(shí)加工過程中，機(jī)床是不允許頻繁關(guān)機(jī)重啟的(頻繁關(guān)機(jī)重啟對(duì)機(jī)床電器元器件壽命影響很大)，因此引入式(23)來限制關(guān)機(jī)重啟次數(shù); 式(24)～式(27)約束Uk,t+1=(1-Zk,t)Sk,t+1恒成立，其中，成對(duì)約束(式(24)與式(25))保證了當(dāng)機(jī)床k的t到t+1位置間不存在關(guān)機(jī)/重啟策略時(shí)，即Zk,t=0時(shí)，保證Uk,t+1=(1-Zk,t)Sk,t+1成立；式(26)、式(27)保證了Zk,t=1時(shí)，Uk,t+1=(1-Zk,t)Sk,t+1成立，同理，式(28)～式(31)保證了Wk,t=(1-Zk,t)Sk,t恒成立，式(32)～式(34)保證了Ai,k,t=(1-Zk,t)Xi,k,t恒成立。

2.2 模型2

模型2包括非線性模型2和線性模型2。與模型1相比，模型2引入連續(xù)決策變量Fk,t，從而減少目標(biāo)函數(shù)中的非線性項(xiàng)、中間決策變量以及相應(yīng)約束的數(shù)量。

非線性模型2的目標(biāo)函數(shù)中含有非線性項(xiàng)(1-Zk,t)(Sk,t+1-Fk,t)，通過引入中間決策變量線性化后即為線性化模型2的目標(biāo)函數(shù)。線性化過程與模型1相似，引入中間決策變量Uk,t、Vk,t，分別代替非線性項(xiàng)(1-Zk,t)Sk,t+1、(1-Zk,t)Fk,t，實(shí)現(xiàn)非線性目標(biāo)函數(shù)到線性目標(biāo)函數(shù)的轉(zhuǎn)換。

模型2中的決策變量為：Xi,k,t、Zk,t、Sk,t、Cmax、Uk,t(含義與模型1中的相同)；機(jī)床k上第t個(gè)位置的結(jié)束時(shí)間Fk,t；用來代替非線性項(xiàng)(1-Zk,t)Fk,t的中間決策變量Vk,t。

非線性模型2的目標(biāo)函數(shù)為

(35)

線性模型2的目標(biāo)函數(shù)為

(36)

約束條件為

(37)

Fk,t-M(1-Xi,k,t)≤di?t∈T

(38)

Fk,n-m+1≤Cmax

(39)

Sk,t+1-Fk,t≤Tk,B+MZk,t?t∈T1

(40)

Sk,t+1-Fk,t≥Tk,BZk,t?t∈T1

(41)

Vk,t≥Sk,t-MZk,t?t∈T1

(42)

Vk,t≤Sk,t+MZk,t?t∈T1

(43)

Vk,t≤M(1-Zk,t) ?t∈T1

(44)

Vk,t≥0 ?t∈T1

(45)

其中，?i∈I，?k∈K。式(37)表示機(jī)床位置結(jié)束時(shí)間等于其開始時(shí)間加上安排在該位置工件的加工時(shí)間；式(38)～式(41)的含義分別與式(18)、式(20)～式(22)約束含義相同；式(42)、式(45)用來約束Vk,t=(1-Zk,t)Fk,t恒成立，其中式(42)～式(43)用來約束當(dāng)Zk,t=0時(shí)，Vk,t=Fk,t=(1-Zk,t)Fk,t成立，式(44)、式(45)用來保證當(dāng)Zk,t=1時(shí)，Vk,t=0=(1-Zk,t)Fk,t成立。

2.3 模型3

模型3的目標(biāo)函數(shù)為

(46)

約束條件為

(47)

(48)

?k∈K,t∈T1

3 模型對(duì)比

模型對(duì)比從尺寸復(fù)雜度與計(jì)算復(fù)雜度進(jìn)行，尺寸復(fù)雜度主要包括0-1決策變量數(shù)、約束數(shù)以及連續(xù)決策變量數(shù)3個(gè)方面。計(jì)算復(fù)雜度通過規(guī)定時(shí)間內(nèi)可求最優(yōu)解總數(shù)Q來判定，包括目標(biāo)函數(shù)值的容差Gap=0最優(yōu)解個(gè)數(shù)Q0與Gap≠0最優(yōu)解個(gè)數(shù)Q1。當(dāng)Q相同時(shí)，對(duì)比Q0；當(dāng)Q與Q0都相同時(shí)，對(duì)比Q1；Q、Q0與Q1越大，模型越好。當(dāng)Q、Q0與Q1都相同時(shí)，對(duì)比求解時(shí)間ttotal，ttotal也是一個(gè)重要評(píng)價(jià)指標(biāo)，越小越好。Gap可定義為|SC-SB|/|SC|，其中SC表示目前為止可以找到的最優(yōu)解，SB表示可能的最優(yōu)解，是當(dāng)前所有解的下限?？梢?，Gap值越小越好，當(dāng)Gap=0時(shí)，則得到問題的最優(yōu)解，程序會(huì)自動(dòng)停止。由此，Gap值也常作為評(píng)價(jià)MIP模型求解效果的一個(gè)指標(biāo)。

本文所有混合整數(shù)線性模型都由商業(yè)軟件IBM ILOG CPLEX12.7.1求解，編程語言采用CPLEX Studio自帶OPL語言編寫。CPLEX可以求解線性模型以及非線性模型。模型運(yùn)行最長時(shí)間設(shè)置為3 600 s，所有實(shí)例獨(dú)立運(yùn)行3次，最終結(jié)果取平均值。所有實(shí)例在Dell Vostro 3900臺(tái)式機(jī)上運(yùn)行，該電腦配置為：Win7系統(tǒng)、i5-4460 3.20GHz四核處理器、8G內(nèi)存。

如果模型在3 600 s之內(nèi)自行停止，則可得到最優(yōu)解且可證明所得到的解為最優(yōu)解，即Gap=0，如果到截止時(shí)間3 600 s，程序強(qiáng)制停止，此時(shí)有可能得到Gap≠0最優(yōu)解，但是Gap≠0，是因?yàn)殡m然求出了最優(yōu)解，但是在規(guī)定時(shí)間內(nèi)不能證明該解為最優(yōu)的。本文總共測試10組規(guī)模不同的實(shí)例。因?yàn)槟壳皼]有關(guān)于UPMSP能耗相關(guān)的對(duì)比實(shí)例，因此本文隨機(jī)生成10組規(guī)模不同的實(shí)例。

3.1 模型尺寸復(fù)雜度對(duì)比

表2 每個(gè)約束方程的約束數(shù)目

表2給出了上文所列每個(gè)約束方程的約束數(shù)量，結(jié)合每個(gè)模型所含約束方程，進(jìn)而可以得每個(gè)模型的約束數(shù)(表3)。由各個(gè)MIP模型的建模過程可得出每個(gè)模型的尺寸復(fù)雜度，見表3。模型針對(duì)具體實(shí)例的尺寸復(fù)雜度見表4。其中10*2表示工件數(shù)*機(jī)床數(shù)，其他類推。

表3 所有模型尺寸復(fù)雜度

表4 所有模型針對(duì)10組實(shí)例的尺寸復(fù)雜度

通過表3和表4可知，在0-1決策變量數(shù)方面，非線性模型1最多，其他模型相同。這是因?yàn)槠渌Ｐ椭缓蠿i,k,t、Zk,t兩個(gè)0-1決策變量，而模型1除含有Xi,k,t、Zk,t兩個(gè)0-1決策變量外，還含有Ai,k,t。

在約束數(shù)方面，由表3和表4 可以看出，從多到少依次為線性模型1、線性模型2、非線性模型2、非線性模型1、模型3。這是由于線性模型3基于待機(jī)能耗的建模思想，不需要線性化處理目標(biāo)函數(shù)以及相關(guān)的約束方程，約束最少。線性模型1需要引入3個(gè)中間決策變量(Ai,k,t、Uk,t以及Wk,t)以及相關(guān)的約束，而線性模型2只需要引入2個(gè)中間決策變量(Uk,t與Vk,t)及相關(guān)約束，因此，線性模型1約束數(shù)多于線性模型2。非線性模型1與非線性模型2因?yàn)闆]有引入中間決策變量及相關(guān)約束，故約束數(shù)分別少于線性模型1與線性模型2。

在連續(xù)決策變量數(shù)方面，由表3和表4可以看出，連續(xù)決策變量數(shù)從多到少依次為線性模型2、線性模型1、非線性模型2、模型3、非線性模型1。

3.2 模型計(jì)算復(fù)雜度對(duì)比

決策變量數(shù)以及約束數(shù)嚴(yán)重影響MIP模型的求解效率。對(duì)MIP模型影響程度從大到小依次為0-1決策變量數(shù)、約束數(shù)以及連續(xù)決策變量數(shù)[21]。除此之外，非線性特征對(duì)MIP模型的求解效率影響也很大。

表5 所有模型針對(duì)10組實(shí)例的求解結(jié)果

5種模型針對(duì)10組實(shí)例的求解結(jié)果見表5。其中，SO表示最優(yōu)解(可通過模型3長時(shí)間求解得到)，SC表示當(dāng)前解(如果在3 600 s內(nèi)程序自動(dòng)停止，則為最優(yōu)解，否則對(duì)應(yīng)3 600 s所能得到的最好解)，帶“*”的解表示此解為可行解但非最優(yōu)解。

由表5可知，在10個(gè)實(shí)例中，在規(guī)定時(shí)間3 600 s內(nèi)，非線性模型1及線性模型1求解效果最差，只可求出10個(gè)實(shí)例中的5個(gè)，包括3個(gè)Gap=0最優(yōu)解以及2個(gè)Gap≠0最優(yōu)解；線性模型1由于引入3個(gè)中間決策變量(Ai,k,t、Uk,t、Wk,t)及相關(guān)的約束，決策變量數(shù)以及約束數(shù)遠(yuǎn)多于非線性模型1，這嚴(yán)重影響了線性模型1的求解效率，因此求解時(shí)間長于非線性模型1。

非線性模型2可以求得10個(gè)實(shí)例中的7個(gè)最優(yōu)解，其中6個(gè)Gap=0 最優(yōu)解以及1個(gè)Gap≠0最優(yōu)解，效果差于線性模型2(其可求得8個(gè)Gap=0 最優(yōu)解)，且求解時(shí)間長于線性模型2，這是由非線性模型2的非線性特征影響的。

非線性模型2和線性模型2由于添加了機(jī)床位置結(jié)束時(shí)間決策變量Fk,t，非線性模型2的非線性項(xiàng)少于非線性模型1，線性模型2的0-1決策變量以及約束數(shù)遠(yuǎn)少于線性模型1，因此求解效果好于非線性模型1和線性模型1。

模型3基于空閑能耗的建模思想，目標(biāo)函數(shù)是線性的，不需要對(duì)其進(jìn)行線性化處理以及相應(yīng)的中間決策變量、約束等，從而使模型3具有最少的0-1決策變量、連續(xù)決策變量以及較少的約束數(shù)，從而模型3求解效果最好。

除此之外，模型的求解效果還依賴具體實(shí)例的加工數(shù)據(jù)，如針對(duì)實(shí)例20*5，非線性模型2求解時(shí)間為224.25 s，線性模型2求解時(shí)間為320.00 s，線性模型3求解時(shí)間為451.23 s，非線性模型2的求解效果好于線性模型2以及線性模型3，線性模型2效果好于線性模型3。

3.3 節(jié)能策略挖掘

實(shí)例25*3的具體數(shù)據(jù)如表6和表7所示。圖1為實(shí)例25*3的最優(yōu)甘特圖。對(duì)圖1進(jìn)行分析，由于考慮了不同工件釋放時(shí)間以及交貨期，因此每個(gè)工件必須在自身釋放時(shí)間-交貨期時(shí)間窗內(nèi)進(jìn)行加工。工件1～8被分配到機(jī)床2上進(jìn)行加工，機(jī)床2在0時(shí)刻開機(jī)，在212時(shí)刻關(guān)機(jī)。工件10、12、17、18、21、22、25被分配到機(jī)床1上進(jìn)行加工，機(jī)床1在230時(shí)刻才開機(jī)而不是在0時(shí)刻開機(jī)，從而可以減少待機(jī)能耗。工件12在291時(shí)刻加工完后，此時(shí)下一工件17還沒有到達(dá)(其釋放時(shí)間為320)，此時(shí)機(jī)床將處于長時(shí)間待機(jī)狀態(tài)。工件17在363時(shí)刻開始加工，在388時(shí)刻完成加工，完工時(shí)間小于交貨期400。時(shí)刻291～363長達(dá)72的待機(jī)時(shí)間將導(dǎo)致機(jī)床浪費(fèi)大量待機(jī)能耗，在該待機(jī)段內(nèi)對(duì)機(jī)床1實(shí)行關(guān)機(jī)/重啟節(jié)能策略，可以節(jié)約能耗。機(jī)床3同樣不是在0時(shí)刻開機(jī)，而是在199時(shí)刻開機(jī)以節(jié)約能耗，所加工工件依次為9、11、13、14、15、16、19、20、23以及24。由于本文將公共功率設(shè)置為20，公共能耗占總能耗比重較大，從而所求能耗最優(yōu)解中的Cmax也達(dá)到了最優(yōu)(最小)。

表6 實(shí)例25*3加工時(shí)間數(shù)據(jù)

表7 實(shí)例25*3加工功率、能耗數(shù)據(jù)

圖1 實(shí)例25*3甘特圖Fig.1 Gantt chart of instance 25*3

可見，在保證最大完工時(shí)間不變以及滿足交貨期的情況下，通過延遲開機(jī)以及關(guān)機(jī)/重啟策略可以減少機(jī)床待機(jī)能耗，達(dá)到節(jié)能的目的。對(duì)節(jié)能措施的挖掘有利于以后指導(dǎo)元啟發(fā)式方法的設(shè)計(jì)，從而可以有效求解大規(guī)模問題。

4 結(jié)論

本文以能耗最小為目標(biāo)，提出了5個(gè)考慮關(guān)機(jī)/重啟策略的不相關(guān)并行機(jī)MIP模型。試驗(yàn)結(jié)果表明：基于不同建模思路的MIP模型尺寸復(fù)雜度、計(jì)算復(fù)雜度差別很大，基于空閑能耗的線性化MIP模型求解效果最好，在今后的應(yīng)用過程中應(yīng)優(yōu)先選用。

雖然元啟發(fā)式方法、啟發(fā)式規(guī)則等在短時(shí)間內(nèi)可以得到問題較好的解，但是即使是對(duì)于小規(guī)模問題，也不一定能夠找到最優(yōu)解，也無法證明所得到的解是最優(yōu)的，而通過MIP模型求解則可得到并證明最優(yōu)解。MIP的求解結(jié)果可以作為啟發(fā)式以及元啟發(fā)式等近似方法的參照標(biāo)準(zhǔn)。由于本文直接使用CPLEX對(duì)問題進(jìn)行求解，沒有加入針對(duì)問題特性的求解算法等，因此求解效率較低，下一步研究工作將針對(duì)本文問題特性，設(shè)計(jì)相應(yīng)的求解規(guī)則以嵌入到CPLEX，提高求解效率。