李冰，黎展滔（廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東廣州510006）

調(diào)整時(shí)間與順序相關(guān)的能耗優(yōu)化調(diào)度問(wèn)題*

李冰，黎展滔
（廣東工業(yè)大學(xué)機(jī)電工程學(xué)院，廣東廣州510006）

以陶瓷行業(yè)車間生產(chǎn)計(jì)劃為背景，將其抽象為調(diào)整時(shí)間與順序相關(guān)的能耗優(yōu)化調(diào)度問(wèn)題進(jìn)行研究。以最少化總能耗為目標(biāo)，建立數(shù)學(xué)模型；提出了基于NEH算法的混合遺傳算法，其中初始化種群中，定義了虛擬工件概念，采用了改進(jìn)NEH規(guī)則對(duì)種群初始化；為了對(duì)上述算法進(jìn)行驗(yàn)證，提出了該問(wèn)題的兩個(gè)下界，設(shè)計(jì)了仿真試驗(yàn)，進(jìn)行下界背離程度分析和CPU運(yùn)行時(shí)間分析。計(jì)算結(jié)果表明：所設(shè)計(jì)的混合遺傳算法能夠在可接受的計(jì)算時(shí)間內(nèi)獲得合理的解。

柔性流水車間；調(diào)整時(shí)間與順序相關(guān)；遺傳算法；能耗優(yōu)化

0　引言

近十幾年來(lái)，我國(guó)陶瓷工業(yè)得到了迅猛發(fā)展，然而，雖然我國(guó)陶瓷產(chǎn)量在世界上遙遙領(lǐng)先，但總體上存在能耗高、資源消耗大、綜合利用率低、生產(chǎn)效率低等問(wèn)題。開(kāi)展以減少能源消耗為目標(biāo)的調(diào)度方法研究，對(duì)提高能源利用率、減少企業(yè)生產(chǎn)成本具有重大意義。

陶瓷的生產(chǎn)過(guò)程中，當(dāng)訂單進(jìn)行切換時(shí)，產(chǎn)生的調(diào)整時(shí)間導(dǎo)致了大量的時(shí)間成本和能耗成本。本文對(duì)陶瓷企業(yè)的調(diào)整時(shí)間分為兩類：一類調(diào)整時(shí)間取決于工件順序；另外一類調(diào)整時(shí)間取決于工件順序和工件所在的機(jī)器。例如，對(duì)于成形工序，當(dāng)需要切換不同的顏色時(shí)，其調(diào)整時(shí)間與訂單的順序相關(guān)；對(duì)于干燥工序，當(dāng)訂單需要切換時(shí)，工人們需要清潔機(jī)器，每臺(tái)機(jī)器的清洗時(shí)間要取決于該機(jī)器在加工上一個(gè)訂單時(shí)殘留量的多少。因此，在干燥工序中，調(diào)整時(shí)間取決于訂單的加工順序和加工訂單所在的機(jī)器。

近幾年來(lái)，關(guān)于與調(diào)整時(shí)間相關(guān)的調(diào)度問(wèn)題已經(jīng)有許多的研究成果。Pinedo[1]指出如果處理不好，調(diào)整時(shí)間可以占用機(jī)器加工時(shí)間的20%。Cheng等人[2]，Potts and Kovalyov[3]等人和Allahverdi等人[4]對(duì)與調(diào)整時(shí)間相關(guān)的調(diào)度問(wèn)題進(jìn)行了綜述。在這些文獻(xiàn)中，把調(diào)整時(shí)間分為兩類：調(diào)整時(shí)間與順序相獨(dú)立，即調(diào)整時(shí)間只與工件自身的相關(guān)；調(diào)整時(shí)間與順序相關(guān)，即調(diào)整時(shí)間與工件之間的順序相關(guān)。

本文以最少化能耗成本為目標(biāo)，對(duì)具有兩類調(diào)整時(shí)間與順序相關(guān)的能耗優(yōu)化調(diào)度問(wèn)題進(jìn)行了研究。針對(duì)該問(wèn)題，提出了基于NEH規(guī)則的改進(jìn)遺傳算法。通過(guò)仿真實(shí)驗(yàn)，分析、驗(yàn)證比較了算法的有效性。

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

1.1問(wèn)題描述

本文針對(duì)調(diào)整時(shí)間與順序相關(guān)能耗優(yōu)化調(diào)度問(wèn)題進(jìn)行了研究。該類問(wèn)題的定義如下。

有n個(gè)工件或任務(wù)，每個(gè)工件都要先后經(jīng)過(guò)k個(gè)階段的加工。每個(gè)階段由ms（s=1，2，…，k）臺(tái)非同等并行組成。每臺(tái)機(jī)器有三種模式：運(yùn)行，待機(jī)和停止。對(duì)應(yīng)著每臺(tái)機(jī)器的三種模式，每臺(tái)機(jī)器的能耗由三部分組成：運(yùn)行能耗，空閑能耗和預(yù)熱能耗。每個(gè)工件需要在每階段中的一臺(tái)機(jī)器上經(jīng)過(guò)。工件不是同一時(shí)間到達(dá)，每個(gè)工件具有一個(gè)到達(dá)時(shí)間rj。在同一機(jī)器上連續(xù)加工的兩個(gè)工件存在著調(diào)整時(shí)間。

1.2數(shù)學(xué)模型

n為工件數(shù)量；

k為階段數(shù)；

rj為工件的投放時(shí)間，j=1，2，…，n；

ms為階段s的機(jī)器數(shù)量，s=1，2，…，s；

pjhs為工件j在第s階段的機(jī)器h上的加工時(shí)間，h=1，2，…，m；

Bjs為工件j在第s階段開(kāi)加工時(shí)間；

Cjs為工件j在第s階段完工工時(shí)間；

ST1為調(diào)整時(shí)間與順序相關(guān)的階段集；

ST2為調(diào)整時(shí)間與工件順序和工件所安排到機(jī)器相關(guān)的階段集；

Qhs為安排在階段s的機(jī)器h上加工的工件集；

ths為在階段s機(jī)器h從停止?fàn)顟B(tài)到可以開(kāi)始加工狀態(tài)需要的時(shí)間；

Δths為在階段s機(jī)器h上存在著空閑時(shí)間段的集合；

Δtwhs為在階段s機(jī)器h上第w個(gè)空閑時(shí)間段，w∈Δtwhs；

M為一個(gè)足夠大的整數(shù)；

決策變量：

數(shù)學(xué)模型如下：

上述的表達(dá)式中：式（1）表示問(wèn)題的目標(biāo)函數(shù)，最少化總能源成本，總能耗Emin由三部分組成：運(yùn)行能耗成本（即式（1）的第一部分），待機(jī)能耗（即式（1）的第二部分）和預(yù)熱能耗（即式（1）的第三部分）；式（2）表示每個(gè)工件需要先后經(jīng)過(guò)s階段的加工，即每個(gè)工件在它上一階段未加工完成前，不能開(kāi)始在當(dāng)前階段的加工；式（3）表示工件在當(dāng)期階段的開(kāi)始加工時(shí)間不能早于該工件在該階段的投放時(shí)間；式（4）表示每個(gè)工件在同一時(shí)間只能安排在一臺(tái)機(jī)器上加工；式（5）表示機(jī)器在同一時(shí)間只能加工一個(gè)工件。如果Yijhs=1，表示在階段s機(jī)器h上工件j的開(kāi)始加工時(shí)間大于工件i的完工時(shí)間，這意味工件i、j連續(xù)安排在階段s的機(jī)器h上加工。如果Yijhs=0，則式（5）恒成立，其中M表示一個(gè)足夠大的數(shù)目；式（6）計(jì)算工件在每階段的完工時(shí)間，其完工時(shí)間等于工件在該階段的開(kāi)始加工時(shí)間加上工件在該階段機(jī)器上的加工時(shí)間和調(diào)整時(shí)間。由于本文考慮了兩類與順序相關(guān)的調(diào)整時(shí)間，因此當(dāng)當(dāng)前階段屬于第一類調(diào)整時(shí)間時(shí)，工件在每階段的完工有式（6）第一個(gè)表達(dá)式計(jì)算，否則，工件在每階段的完工時(shí)間由式（6）第二個(gè)表達(dá)式計(jì)算；式（7）定義了工件在每階段的開(kāi)加工時(shí)間，其值等于工件在上一階段的完工時(shí)間和工件安排在機(jī)器的可開(kāi)始加工時(shí)間之間的較大值。當(dāng)s= 1，Cjh(s-1)=rj和j=1，C0hs=0；式（8）確定在空閑時(shí)間段內(nèi)機(jī)器的狀態(tài)（待機(jī)狀態(tài)或機(jī)器從停機(jī)到開(kāi)機(jī)的預(yù)熱狀態(tài)）。式（8）第一表達(dá)式定義了機(jī)器存在空閑時(shí)間段的數(shù)量。如果滿足式（8）第二和第三個(gè)表達(dá)式，則機(jī)器在該空閑時(shí)間段處于預(yù)熱狀態(tài)，否則機(jī)器處于待機(jī)狀態(tài)。式（9）和（10）表示決策變量的取值范圍。

2　基于NEH規(guī)則的混合遺傳算法

2.1染色體表達(dá)

為了減少搜索空間中的冗余解，提高遺傳算法搜索效率，可行解的染色體表達(dá)如下：編碼的長(zhǎng)度為n，等于被加工工件的數(shù)目，是工件集合的一個(gè)全排列，構(gòu)成了各臺(tái)機(jī)器的加工序列；各基因值代表相應(yīng)工件所在的機(jī)器編號(hào)。編碼分別表達(dá)了工件間加工順序信息和工件與機(jī)器間分派信息[5]。

2.2種群的初始化

Nawaz等人[6]提出了一種NEH啟發(fā)式算法。該算法被認(rèn)為求解流水車間調(diào)度問(wèn)題的最好啟發(fā)式算法。NEH算法的核心思想是，工件的總加工時(shí)間越長(zhǎng)，則該工件得到更高的加工優(yōu)先級(jí)。NEH的算法步驟如下：

步驟1：根據(jù)工件總加工的減序進(jìn)行排序，得到工件加工隊(duì)列S；

步驟2：根據(jù)加工隊(duì)列S，取其前兩個(gè)工件進(jìn)行調(diào)度得到最優(yōu)調(diào)度；

步驟3：根據(jù)加工隊(duì)列S讀取下一個(gè)工件，把該工件插入到已經(jīng)調(diào)度的工件排列中的某個(gè)位置，使得調(diào)度指標(biāo)最少；

步驟4：重復(fù)上述過(guò)程，直到加工隊(duì)列里的所有工件都調(diào)度完畢。

本文為同時(shí)考慮工件間的調(diào)整時(shí)間和加工時(shí)間提出一種基于NEH算法的基于調(diào)整時(shí)間和加工時(shí)間的能耗排序策略ESPRA。ESPRA算法的一個(gè)重要特征是引入了虛擬工件的概念。虛擬工件是由一對(duì)基于調(diào)整時(shí)間的最少能耗的工件組成，即每個(gè)虛擬工件由兩個(gè)基于調(diào)整時(shí)間最少能耗的工件組成。虛擬工件的構(gòu)建使得具有最少調(diào)整時(shí)間能耗工件組合在一起加工，減少工件在加工過(guò)程的調(diào)整時(shí)間。定義完虛擬工件后，本文還需要定義每個(gè)虛擬工件在每階段的加工時(shí)間FJis，F(xiàn)Jis的計(jì)算如式（11）所示。即，F(xiàn)Jis等于虛擬工件中兩個(gè)工件的基于工件加工時(shí)間的平均運(yùn)行能耗成本。

其中，p(n+1)hs=0。

假設(shè)J1，J2，…，J8為相互獨(dú)立的工件，并且根據(jù)工件基于調(diào)整時(shí)間的總空閑能耗成本進(jìn)行升序排列。FJ1s，F(xiàn)J2s，F(xiàn)J3s和FJ4s是虛擬的工件。例如，虛擬的工件FJ1s，由工件J1和J2，組成。根據(jù)公式（11）計(jì)算虛擬工件在階段S上的加工時(shí)間。然后根據(jù)虛擬工件的加工時(shí)間減序?qū)μ摂M工件進(jìn)行排序得到虛擬工件的加工隊(duì)列。讀取虛擬工件隊(duì)列前兩個(gè)工件進(jìn)行最優(yōu)調(diào)度，進(jìn)而依次將剩余的工件逐個(gè)插入到已經(jīng)調(diào)度的工件排列中的某個(gè)位置，使得總能耗成本最少，直到所有工件調(diào)度完畢，從而得到一個(gè)調(diào)度結(jié)果。例如，虛擬工件FJ1s和FJ2s具有兩種可能的調(diào)度方案，即先加工FJ1s后加工FJ2s，或者先加工FJ2s后加工FJ1s。假設(shè)后者調(diào)度方案更優(yōu)，那么得到工件局部調(diào)度方案，重復(fù)上述步驟直到所有虛擬工件調(diào)度完畢。得到初始化工件集合的全排列，各基因值取值randi(1，ms)，重復(fù)上述步驟，形成初始化種群。

2.3適應(yīng)度函數(shù)和選擇

由于優(yōu)化目標(biāo)為能耗最小，因此令目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度值函數(shù)：f（i）=1/Emin。采用輪盤(pán)賭方法進(jìn)行選擇，在進(jìn)化過(guò)程中個(gè)體的適應(yīng)值越高，其被選擇的概率就越大。

2.4交叉操作與變異操作

交叉在遺傳操作中起核心作用，本文對(duì)染色體實(shí)行分段兩點(diǎn)交叉操作，使得經(jīng)過(guò)交叉后的染色體不破壞編碼規(guī)則。本文對(duì)染色體實(shí)行分段變異操作，選擇合適的變異概率，隨機(jī)交換分段染色體中兩個(gè)不同基因的位置。

3仿真試驗(yàn)

為了驗(yàn)證所提出的遺傳算法的有效性，用MATLABr2012a仿真軟件，并在CPU為Intel(R) Corei5-24502.5GHz，內(nèi)存4G的計(jì)算機(jī)上進(jìn)行仿真試驗(yàn)。

加工參數(shù)設(shè)置：柔性度m∈{1/3，2/3，1}；工件數(shù)目n∈{20，30，40，50，60，70，80，90}；調(diào)整時(shí)間與加工時(shí)間給出8個(gè)水平的比值：5%，10%，25%，50%，75%，100%，125%和150%。對(duì)應(yīng)于這些比例，調(diào)整時(shí)間由以下均勻分布產(chǎn)生：U[1，5]，U[1，10]，U[1，25]，U[1，50]，U[1，75]，U[1，100]，U[1，125]和U[1，150]。單位時(shí)間運(yùn)行能耗成本和單位時(shí)間空閑能耗成本由一個(gè)從1到10的隨機(jī)數(shù)產(chǎn)生（即/=randi(1，10)）；每臺(tái)機(jī)器單位時(shí)間的預(yù)熱能耗成本由Ths3=randi(3，4)·Ths2產(chǎn)生，其中randi（3，4）表示一個(gè)從3到4的隨機(jī)數(shù)。機(jī)器從停止?fàn)顟B(tài)到可加工狀態(tài)的預(yù)熱時(shí)間由產(chǎn)生，其中randi（0.1，0.5）表示一個(gè)由0.1到0.5的隨機(jī)數(shù)。

遺傳算法參數(shù)設(shè)置：種群規(guī)模100，交叉概率0.65，交換變異概率0.35，最大進(jìn)化代數(shù)300。機(jī)器數(shù)目與工件數(shù)目的不同組合構(gòu)成不同的問(wèn)題規(guī)模；為消除隨機(jī)因素對(duì)計(jì)算結(jié)果的影響，每種問(wèn)題規(guī)模下產(chǎn)生50個(gè)計(jì)算實(shí)例，并報(bào)告平均計(jì)算結(jié)果，如表1所示，其中以背離程度來(lái)表達(dá)遺傳算法計(jì)算目標(biāo)值同最優(yōu)解的差異，背離程度定義為（遺傳算法計(jì)算目標(biāo)值-下界）/下界。

證明：

LB1：這是一個(gè)基于工件的定界。每個(gè)工件必須在每階段上加工，并且需要調(diào)整時(shí)間。假設(shè)工件i在加工過(guò)程和調(diào)整時(shí)間時(shí)都是最少能耗成本，那么所有工件所得的總能耗成本為該問(wèn)題的下界。基于這個(gè)思路，LB1的三個(gè)部分分別表示工件的最少運(yùn)行能耗成本，最少待機(jī)能耗成本和最少預(yù)熱能耗成本。

LB2：這是一個(gè)基于機(jī)器的定界。每臺(tái)機(jī)器在每階段的能源成本一共由三部分組成。LB2第一項(xiàng)表示機(jī)器的運(yùn)行能耗成本，當(dāng)調(diào)度方案確定時(shí)該部分能耗成本恒定不變。LB2第二項(xiàng)表示機(jī)器在調(diào)整時(shí)間為第一類調(diào)整時(shí)間的最少空閑能耗成本，其中，對(duì)于階段g的機(jī)器h，至少存在(Qhg-1)段空閑調(diào)整時(shí)間段。如果每一段都取最少調(diào)整時(shí)間，則機(jī)器在該階段的空閑能耗成本最少化。同理，LB2第三項(xiàng)表示當(dāng)機(jī)器屬于第二類調(diào)整時(shí)間時(shí)，機(jī)器空閑能耗成本的下界。

表1　數(shù)值計(jì)算結(jié)果

從表1中可看出，遺傳算法計(jì)算目標(biāo)值同下界的最大和最小平均背離程度分別為1.852%和0.2395%。隨著問(wèn)題規(guī)模的增長(zhǎng)，遺傳算法平均運(yùn)行時(shí)間、計(jì)算目標(biāo)值同下界平均背離程度的變化趨勢(shì)分別如圖1、圖2所示，其中算法運(yùn)行時(shí)間基本呈現(xiàn)線性增長(zhǎng)的趨勢(shì)，而背離程度的增長(zhǎng)趨勢(shì)趨于平緩。

圖1　計(jì)算目標(biāo)值同下屆背離程度變化曲線

圖2　遺傳算法運(yùn)行時(shí)間變化曲線

4　結(jié)論

（1）以能耗為目標(biāo)，對(duì)調(diào)整時(shí)間與順序相關(guān)的柔性流水車間調(diào)度中的工件分配與排序進(jìn)行決策，提出了該問(wèn)題的數(shù)學(xué)規(guī)劃模型，并解析證明了該問(wèn)題的一個(gè)下界。

（2）同時(shí)考慮工件間的調(diào)整時(shí)間和加工時(shí)間提出一種基于NEH算法的基于調(diào)整時(shí)間和加工時(shí)間的能耗排序策略，并提出了基于NEH算法的混合遺傳算法。

（3）進(jìn)行試驗(yàn)分析，通過(guò)與引入的下界進(jìn)行比較，表明了設(shè)計(jì)的遺傳算法具有較好的求解性能，能夠在較短的時(shí)間內(nèi)獲得滿意解。

參考文獻(xiàn)：

［1］Pinedo M.L..Scheduling theory，algorithms and sys?tems［M］.Upper Saddle River，New Jersey：Pren?tice-Hall.2008.

［2］Cheng T.C.E.，Gupta J.N.D.，Wang G.Q.A review of flowshop scheduling research with setup times［J］. Production and Operations Management，2000，9（3）：262-282.

［3］Potts C.N.，Kovalyov M.Y.，Scheduling with batch?ing：a review［J］.European Journal of Operational Research，2000，120（2）：228-249.

［4］Allahverdi A.A survey of scheduling problemswith setup timesor costs［J］.European JournalofOperationalRe?search，2008，187（3）：985-1032.

［5］廖珊，翟所霞，魯玉軍.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度方法研究［J］.機(jī)電工程，2014（6）：729-733.

［6］Nawaz，M.，Enscore，E.，Ham，I.，A heuristic algorithm for them-machine n-job flow shop sequencing problem［J］.Omega，1983，11（1）：11-95.

(編輯：阮毅)

Energy Consumption Optimization Scheduling Problem with Sequence-Dependent Setup Times

LI Bing，LI Zhan-tao
（Guangdong University of Technology，CollegeofMechanicaland Electronic Engineering，Guangzhou 510006，China）

This paper considers ceramic industry workshop production plan as the background，abstract that to energy consumption optimization scheduling problem with two types of sequence-dependent setup times to study.Tominimize the total energy consumption as the goal，establishmentofmathematicalmodel.The hybrid genetic algorithm is proposed based on NEH algorithm，in the initialization of population，defines the concept of virtual work，using the improved NEH rules for population initialization.Two lower bounds are proposed to evaluate the algorithms.A computational experiment is developed to lower bounds degree of deviation analysis and CPU running times analysis.The analysis reveals that designed by hybrid genetic algorithm can be acquired within an acceptable computation time reasonable solution.

flexible flow shop；sequence-dependentsetup time；Genetic algorithm；energy consumption

TH165 TP301

A

1009－9492(2015)06－0012－05

10.3969/j.issn.1009-9492.2015.06.003

*廣東省自然科學(xué)基金資助項(xiàng)目（編號(hào)：501130093）；粵港澳領(lǐng)域重點(diǎn)突破項(xiàng)目（編號(hào)：2012A080107017）

2015－03－18

李冰，男，1990年生，江西吉安人，碩士研究生。研究領(lǐng)域：智能制造、綠色制造、制造物聯(lián)網(wǎng)。