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

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

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

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

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

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

0　引言

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

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

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

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

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

1.1問題描述

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

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

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

n為工件數(shù)量；

k為階段數(shù)；

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

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

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

Bjs為工件j在第s階段開加工時間；

Cjs為工件j在第s階段完工工時間；

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

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

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

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

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

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

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

決策變量：

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

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

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

2.1染色體表達(dá)

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

2.2種群的初始化

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

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

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

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

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

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

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

假設(shè)J1，J2，…，J8為相互獨立的工件，并且根據(jù)工件基于調(diào)整時間的總空閑能耗成本進(jìn)行升序排列。FJ1s，F(xiàn)J2s，F(xiàn)J3s和FJ4s是虛擬的工件。例如，虛擬的工件FJ1s，由工件J1和J2，組成。根據(jù)公式（11）計算虛擬工件在階段S上的加工時間。然后根據(jù)虛擬工件的加工時間減序?qū)μ摂M工件進(jìn)行排序得到虛擬工件的加工隊列。讀取虛擬工件隊列前兩個工件進(jìn)行最優(yōu)調(diào)度，進(jìn)而依次將剩余的工件逐個插入到已經(jīng)調(diào)度的工件排列中的某個位置，使得總能耗成本最少，直到所有工件調(diào)度完畢，從而得到一個調(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。采用輪盤賭方法進(jìn)行選擇，在進(jìn)化過程中個體的適應(yīng)值越高，其被選擇的概率就越大。

2.4交叉操作與變異操作

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

3仿真試驗

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

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

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

證明：

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

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

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

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

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

圖2　遺傳算法運行時間變化曲線

4　結(jié)論

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

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

（3）進(jìn)行試驗分析，通過與引入的下界進(jìn)行比較，表明了設(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é)基金資助項目（編號：501130093）；粵港澳領(lǐng)域重點突破項目（編號：2012A080107017）

2015－03－18

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