調整時間與順序相關的能耗優化調度問題*

李冰，黎展滔（廣東工業大學機電工程學院，廣東廣州510006）

調整時間與順序相關的能耗優化調度問題*

李冰，黎展滔
（廣東工業大學機電工程學院，廣東廣州510006）

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

柔性流水車間；調整時間與順序相關；遺傳算法；能耗優化

0　引言

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

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

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

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

1　問題描述與數學模型

1.1問題描述

本文針對調整時間與順序相關能耗優化調度問題進行了研究。該類問題的定義如下。

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

1.2數學模型

n為工件數量；

k為階段數；

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

ms為階段s的機器數量，s=1，2，…，s；

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

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

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

ST1為調整時間與順序相關的階段集；

ST2為調整時間與工件順序和工件所安排到機器相關的階段集；

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

ths為在階段s機器h從停止狀態到可以開始加工狀態需要的時間；

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

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

M為一個足夠大的整數；

決策變量：

數學模型如下：

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

2　基于NEH規則的混合遺傳算法

2.1染色體表達

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

2.2種群的初始化

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

步驟1：根據工件總加工的減序進行排序，得到工件加工隊列S；

步驟2：根據加工隊列S，取其前兩個工件進行調度得到最優調度；

步驟3：根據加工隊列S讀取下一個工件，把該工件插入到已經調度的工件排列中的某個位置，使得調度指標最少；

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

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

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

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

2.3適應度函數和選擇

由于優化目標為能耗最小，因此令目標函數的倒數為適應度值函數：f（i）=1/Emin。采用輪盤賭方法進行選擇，在進化過程中個體的適應值越高，其被選擇的概率就越大。

2.4交叉操作與變異操作

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

3仿真試驗

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

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

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

證明：

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

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

表1　數值計算結果

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

圖1　計算目標值同下屆背離程度變化曲線

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

4　結論

（1）以能耗為目標，對調整時間與順序相關的柔性流水車間調度中的工件分配與排序進行決策，提出了該問題的數學規劃模型，并解析證明了該問題的一個下界。

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

（3）進行試驗分析，通過與引入的下界進行比較，表明了設計的遺傳算法具有較好的求解性能，能夠在較短的時間內獲得滿意解。

參考文獻：

［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］.機電工程，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

*廣東省自然科學基金資助項目（編號：501130093）；粵港澳領域重點突破項目（編號：2012A080107017）

2015－03－18

李冰，男，1990年生，江西吉安人，碩士研究生。研究領域：智能制造、綠色制造、制造物聯網。