Job Shop調(diào)度問題的Minimax模型及雙空間協(xié)同遺傳算法

楊宏安　席志成　夏常凱　王經(jīng)國

西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造教育部重點(diǎn)實(shí)驗(yàn)室，西安，710072

Job Shop調(diào)度問題的Minimax模型及雙空間協(xié)同遺傳算法

楊宏安席志成夏常凱王經(jīng)國

西北工業(yè)大學(xué)現(xiàn)代設(shè)計(jì)與集成制造教育部重點(diǎn)實(shí)驗(yàn)室，西安，710072

針對(duì)工序加工時(shí)間不確定環(huán)境下的Job Shop調(diào)度問題，為了預(yù)估最差調(diào)度工況及其對(duì)應(yīng)的調(diào)度性能指標(biāo)邊界，采用一類保守、穩(wěn)健的Minimax分析方法，建立了基于提前/拖期懲罰成本的Minimax調(diào)度模型；為了解決傳統(tǒng)基于遍歷或枚舉方法存在的搜索空間巨大的問題，提出并證明了給定調(diào)度順序條件下，關(guān)于內(nèi)層Max優(yōu)化過程的凸函數(shù)定理，并依此定理提出了一種工序加工時(shí)間搜索空間過濾機(jī)制。針對(duì)Minimax調(diào)度問題存在的雙空間尋優(yōu)特性，在分析調(diào)度順序種群和工序加工時(shí)間種群的交替進(jìn)化機(jī)制的基礎(chǔ)上，設(shè)計(jì)了一種高效的雙空間協(xié)同遺傳算法。最后通過仿真算例驗(yàn)證了該過濾機(jī)制和雙空間協(xié)同遺傳算法的有效性。

作業(yè)車間調(diào)度；工序加工時(shí)間不確定；提前/拖期；Minimax；雙空間協(xié)同進(jìn)化

0　引言

傳統(tǒng)作業(yè)車間調(diào)度問題(job shop scheduling problem,JSSP)基本上都是假設(shè)調(diào)度參數(shù)已知且忽略各種擾動(dòng)因素。然而，從辯證的觀點(diǎn)看：在人、機(jī)、料、法、環(huán)組成的復(fù)雜制造系統(tǒng)中，不確定性是絕對(duì)的，而確定性則是相對(duì)的[1]。車間內(nèi)部的機(jī)器故障、刀具損壞、人員缺勤、質(zhì)量問題，以及車間外部的訂單調(diào)整、交貨期變更諸多因素，使得車間調(diào)度具有不確定性、隨機(jī)性和復(fù)雜性等顯著特征，從而導(dǎo)致確定性調(diào)度優(yōu)化方案在不確定性擾動(dòng)沖擊下其性能指標(biāo)急劇劣化[2]。由于操作工人技能差異、刀具磨損、特種工藝、質(zhì)量檢驗(yàn)等諸多因素，使得工件的部分關(guān)鍵工序，甚至所有工序的加工時(shí)間呈現(xiàn)顯著的不確定特征。因此，工序加工時(shí)間是JSSP中最普遍、最有代表性的一類不確定性因素。本文將研究對(duì)象聚焦于工序加工時(shí)間不確定環(huán)境下的作業(yè)車間調(diào)度問題(job shop scheduling problem with processing time variability，JSSP-PTV)。

目前，求解JSSP-PTV問題的方法分三類[3]，即隨機(jī)規(guī)劃方法、模糊規(guī)劃方法、區(qū)間數(shù)方法，相應(yīng)的對(duì)工序加工時(shí)間不確定變量的描述方式分為概率分布函數(shù)描述、模糊數(shù)描述、區(qū)間數(shù)描述。然而隨機(jī)規(guī)劃方法和模糊數(shù)方法都要求知道隨機(jī)變量的準(zhǔn)確概率分布，實(shí)際中由于不確定擾動(dòng)因素眾多、復(fù)雜，根本無法得到工序加工時(shí)間不確定變量的準(zhǔn)確概率分布，但可以根據(jù)大量試驗(yàn)數(shù)據(jù)比較容易地確定其變化范圍，因此本文以區(qū)間數(shù)這類非概率方式描述工序加工時(shí)間不確定變量。針對(duì)工序加工時(shí)間的大幅度擾動(dòng)，Minimax方法是以最小化調(diào)度方案在工序加工時(shí)間所有可能取值條件下的最差性能作為調(diào)度目標(biāo)，這類保守、可靠的主動(dòng)調(diào)度方法可以事先預(yù)估最差情景及其對(duì)應(yīng)的調(diào)度性能指標(biāo)，保證調(diào)度的魯棒性，且能夠有效控制決策風(fēng)險(xiǎn)。

工序加工時(shí)間不確定因素使得調(diào)度搜索空間急劇增大。因此，如何有效縮減搜索空間是求解該類不確定調(diào)度問題的重要內(nèi)容。文獻(xiàn)[4]在單機(jī)調(diào)度問題研究中建立了基于以Flow time偏差為調(diào)度指標(biāo)的Minimax模型，提出并證明了給定調(diào)度順序條件下，該目標(biāo)函數(shù)在工序加工時(shí)間取其值域上界值或下界值時(shí)取得最大值；文獻(xiàn)[5]針對(duì)單機(jī)調(diào)度環(huán)境下的一類提前/拖期調(diào)度指標(biāo)，提出并證明了一種有效預(yù)過濾搜索空間的凸函數(shù)定理。針對(duì)并行機(jī)調(diào)度問題，文獻(xiàn)[6]建立了以makespan絕對(duì)偏差為調(diào)度指標(biāo)的Minimax模型，提出并證明了與文獻(xiàn)[4]和文獻(xiàn)[5]類似的定理和結(jié)論。

由于Minimax問題中存在兩個(gè)尋優(yōu)空間，因此在調(diào)度算法設(shè)計(jì)時(shí)一般采用內(nèi)外層嵌套或協(xié)同方法進(jìn)行雙空間優(yōu)化求解。針對(duì)經(jīng)典的Minimax優(yōu)化問題，文獻(xiàn)[7-8]提出了一種較為通用的雙空間協(xié)同遺傳算法，文獻(xiàn)[9]分析了Minimax問題的雙優(yōu)化方向、欺騙性、內(nèi)層Max尋優(yōu)精度對(duì)整個(gè)算法性能影響較大等特征，并針對(duì)常規(guī)迭代法求解Minimax問題的缺陷，對(duì)算法提出了一種改進(jìn)措施。針對(duì)Minimax調(diào)度問題的雙空間優(yōu)化，文獻(xiàn)[5]針對(duì)單機(jī)調(diào)度問題采用雙層嵌套遺傳算法進(jìn)行求解，文獻(xiàn)[10]采用最為保守的絕對(duì)魯棒調(diào)度策略，建立了以makespan為調(diào)度指標(biāo)Minimax調(diào)度模型，并通過雙空間協(xié)同算法優(yōu)化求解。

現(xiàn)有研究基本都是基于正規(guī)調(diào)度指標(biāo)的Minimax問題，或是簡單的單機(jī)調(diào)度問題，而文獻(xiàn)[5]所采用的雙空間嵌套遺傳算法雖然結(jié)構(gòu)層次清晰易懂，直觀地反應(yīng)了內(nèi)外空間的嵌套關(guān)系，但是這類傳統(tǒng)優(yōu)化求解機(jī)制由于效率低下，只適用于小規(guī)模的調(diào)度問題。本文則在文獻(xiàn)[5]的基礎(chǔ)上，提出并證明了凸函數(shù)定理也適用于JSSP-PTV這類復(fù)雜的多機(jī)調(diào)度問題；針對(duì)Minimax調(diào)度問題的雙空間優(yōu)化特性，分析并提出了一種調(diào)度順序種群和工序加工時(shí)間種群的交替進(jìn)化機(jī)制，并依此為基礎(chǔ)，形成了一個(gè)完整的求解Minimax調(diào)度模型的雙空間協(xié)同遺傳算法(two space co-evolutionary genetic algorithm，TSC-GA)，以期在工序加工時(shí)間有較大波動(dòng)范圍的調(diào)度環(huán)境下，為調(diào)度決策者提供一種可靠、穩(wěn)健的調(diào)度指標(biāo)性能界。

1　Job Shop調(diào)度的Minimax模型及其特征分析

1.1Minimax調(diào)度模型

表1　Minimax調(diào)度模型的符號(hào)說明

JSSP-PTV問題的Minimax調(diào)度模型如下：

(1)

s.t.

fi(Ci(x,s))=eiEi+tiTi

(2)

Ei=max(0,di-Ci(x,s))i=1,2,…,n

(3)

Ti=max(0,Ci(x,s)-di)i=1,2,…,n

(5)

(6)

(7)

1.2工序加工時(shí)間不確定條件下的Minimax問題特征分析

Minimax調(diào)度模型包括Min優(yōu)化和Max優(yōu)化兩個(gè)截然相反的優(yōu)化過程，這使得Minimax問題與單純的Min或者M(jìn)ax問題有著顯著差異。

(1)雙空間尋優(yōu)。由式(1)可知，Minimax問題需要優(yōu)化兩個(gè)空間：調(diào)度順序空間和工序加工時(shí)間空間。當(dāng)調(diào)度順序給定后，在加工時(shí)間空間內(nèi)搜索對(duì)應(yīng)的最差性能，這是一個(gè)最大化尋優(yōu)過程；在最小化尋優(yōu)過程中，搜索使最差性能最好的調(diào)度順序。因此，雙空間尋優(yōu)的Minimax問題比單一空間內(nèi)的傳統(tǒng)Min或Max優(yōu)化問題更為復(fù)雜。

(2)收斂過程震蕩。Minimax優(yōu)化過程包括最小化和最大化兩個(gè)優(yōu)化進(jìn)程，且二者對(duì)同一個(gè)目標(biāo)函數(shù)值的尋優(yōu)方向相反，因此，當(dāng)兩個(gè)優(yōu)化進(jìn)程的進(jìn)化速度存在差異時(shí)，對(duì)于整個(gè)調(diào)度算法而言，調(diào)度目標(biāo)函數(shù)值可能會(huì)出現(xiàn)顯著的震蕩現(xiàn)象，從而使得整個(gè)算法的收斂速度較慢，且呈現(xiàn)震蕩收斂趨勢。

(3)內(nèi)層Max尋優(yōu)精度對(duì)整個(gè)調(diào)度算法影響較大。Minimax問題存在內(nèi)層Max優(yōu)化和外層Min優(yōu)化兩個(gè)尋優(yōu)方向相反的過程，所以與傳統(tǒng)Min優(yōu)化問題的最大不同之處在于，其最終輸出的目標(biāo)函數(shù)值不是越小越好，一個(gè)看似最終目標(biāo)函數(shù)值更小的結(jié)果，可能是外層調(diào)度順序種群Min尋優(yōu)徹底帶來的結(jié)果，也可能是因?yàn)閮?nèi)層工序加工時(shí)間種群Max優(yōu)化不徹底導(dǎo)致的欺騙性結(jié)果?？梢?，內(nèi)層工序加工時(shí)間種群的尋優(yōu)精度不僅指導(dǎo)本身的進(jìn)化方向，還影響著外層調(diào)度順序種群的進(jìn)化方向。因此，內(nèi)層工序加工時(shí)間種群的尋優(yōu)精度對(duì)存在兩空間優(yōu)化的Minimax優(yōu)化問題的整體結(jié)果影響較大。

2　內(nèi)層Max優(yōu)化的凸函數(shù)定理及工序加工時(shí)間可行域的過濾機(jī)制

由于JSSP-PTV問題中的工序加工時(shí)間為不確定變量，將使得整個(gè)調(diào)度搜索空間龐大。以簡單的6×6 JSSP-PTV為例：假設(shè)各工序的加工時(shí)間服從均勻分布，且每道工序各有10個(gè)離散可能取值，對(duì)于任一給定的調(diào)度順序，其對(duì)應(yīng)的整個(gè)工序加工時(shí)間搜索空間規(guī)模將達(dá)到1036。因此，如何預(yù)先縮減工序加工時(shí)間的取值范圍，并依此來有效過濾部分搜索空間，成為求解JSSP-PTV這類復(fù)雜不確定調(diào)度問題的首要問題之一。

設(shè)s1、s2為工序加工時(shí)間可行域S中的任意兩個(gè)不同的一維數(shù)組，且0<λ<1，由上述Ci(s)與s中各元素的非負(fù)線性組合性質(zhì)得出

Ci(λ s1+(1-λ)s2)=λ Ci(s1)+(1-λ)Ci(s2)

(8)

由式(2)和式(8)得

fi(Ci(λ s1+(1-λ)s2))=fi(λ Ci(s1)+

(1-λ)Ci(s2))=max{ei(di-Ci(λ s1+(1-λ)s2)),

ti(Ci(λ s1+(1-λ)s2)-di)}

(9)

再由式(8)和式(9)推導(dǎo)出

λ fi(Ci(s1))+(1-λ)fi(Ci(s2))=

λmax{ei(di-Ci(s1)),ti(Ci(s1)-di)}+

(1-λ)max{ei(di-Ci(s2)),ti(Ci(s2)-di)}≥

max{λ ei(di-Ci(s1))+(1-λ)ei(di-Ci(s2)),

λ ti(Ci(s1)-di)+(1-λ)ti(Ci(s2)-di)}=

max{ei(di-Ci(λ s1+(1-λ)s2)),

ti(Ci(λ s1+(1-λ)s2)-di)}

即

λ fi(Ci(s1))+(1-λ)fi(Ci(s2))≥

fi(λ Ci(s1)+(1-λ)Ci(s2))

(10)

依據(jù)凸函數(shù)判定定理[11]和式(10)可知：fi(Ci(x,s))是s的凸函數(shù)。

根據(jù)凸函數(shù)性質(zhì)[11]“有限個(gè)凸函數(shù)的非負(fù)線性組合仍然是凸函數(shù)”，則由上述關(guān)于任一工件的提前/拖期懲罰成本是s的凸函數(shù)(性質(zhì)1)，對(duì)于Minimax模型中的調(diào)度目標(biāo)函數(shù)(式(1))，有以下推論：

在定理1中，工序加工時(shí)間可行域S的頂點(diǎn)是指每道工序加工時(shí)間只取其取值范圍的上界或下界的自由組合所形成的一維數(shù)組s。因此，在給定調(diào)度順序x的條件下，內(nèi)層Max優(yōu)化過程中的工序加工時(shí)間可行域S由

(11)

縮減為

(12)

式(11)表示s內(nèi)的任一元素在其加工時(shí)間取值區(qū)間內(nèi)隨機(jī)取值，而式(12)表示s內(nèi)的任意元素的加工時(shí)間只能有兩個(gè)可能取值，即取值區(qū)間的上界值或下界值。由此，通過定理1可以大幅度縮減整個(gè)工序加工時(shí)間可行域。

3　調(diào)度順序種群和工序加工時(shí)間種群的交替進(jìn)化機(jī)制

由上述Minimax問題特征分析可知：對(duì)于JSSP-PTV調(diào)度問題而言，其存在調(diào)度順序和工序加工時(shí)間兩個(gè)搜索空間，由此，在遺傳算法設(shè)計(jì)時(shí)，必然存在對(duì)應(yīng)的兩個(gè)種群。本文采用雙空間協(xié)同遺傳算法，算法中的兩個(gè)種群：一個(gè)表示調(diào)度順序種群Px，一個(gè)表示工序加工時(shí)間種群Ps。在進(jìn)化過程中，各種群分別利用另一個(gè)種群的當(dāng)前狀態(tài)來評(píng)價(jià)自身種群個(gè)體的適應(yīng)度值，兩種群以一種交替的方式梯度進(jìn)化尋優(yōu)，其交替進(jìn)化過程參見圖1。

圖1　調(diào)度順序和工序加工時(shí)間雙種群的交替進(jìn)化示意圖

表2為兩個(gè)種群尋優(yōu)的示例。在調(diào)度順序種群{x1,x2,x3}中，h(x1)的目標(biāo)函數(shù)值8最小，因此，依據(jù)該種群的Min優(yōu)化方向，則個(gè)體x1在進(jìn)化過程中更容易保留下來；在工序加工時(shí)間種群{s1,s2,s3}中，g(s3)的目標(biāo)函數(shù)值8最大，依據(jù)該種群的Max優(yōu)化方向，則個(gè)體s3在進(jìn)化的過程中更容易保留下來。因此，該Minimax問題在進(jìn)化過程中能找到最優(yōu)解為(x1,s3)。

表2　Minimax問題尋優(yōu)示例

4　雙空間協(xié)同遺傳算法(TSC-GA)

根據(jù)Minimax問題具有的“雙空間尋優(yōu)”特性、內(nèi)層Max優(yōu)化過程的凸函數(shù)定理(定理1)，以及上述調(diào)度順序和工序加工時(shí)間兩個(gè)種群的交替進(jìn)化機(jī)制的分析，提出了如圖2所示的包括調(diào)度順序和工序加工時(shí)間兩個(gè)尋優(yōu)空間的雙空間協(xié)同遺傳算法框架。

圖2　雙空間協(xié)同遺傳算法邏輯框圖

圖2的處理邏輯如下：

(1)初始化。隨機(jī)產(chǎn)生調(diào)度順序種群Px(0)和加工時(shí)間種群Ps(0)，令k=0,kmax=100。

(3)調(diào)度順序種群進(jìn)化操作。以1/h(x)為適應(yīng)度函數(shù)，對(duì)Px(k)進(jìn)行復(fù)制、交叉和變異操作，產(chǎn)生新種群Px(k+1)。

(5)加工時(shí)間種群進(jìn)化操作。以g(s)為適應(yīng)度函數(shù)，對(duì)Ps(k)進(jìn)行復(fù)制、交叉和變異操作，產(chǎn)生新種群Ps(k+1)。

(6)循環(huán)條件判斷。k←k+1，如果k

(7)算法結(jié)束。

4.1內(nèi)層Max優(yōu)化過程中的遺傳算法設(shè)計(jì)

在外層給定調(diào)度順序的條件下，內(nèi)層Max優(yōu)化過程的主要任務(wù)是在工序加工時(shí)間可行域內(nèi)尋找該調(diào)度順序?qū)?yīng)的最大提前/拖期懲罰成本(即E/T)懲罰值。內(nèi)層遺傳算法的關(guān)鍵操作如下：

(1)編碼方法。工序加工時(shí)間種群采用實(shí)數(shù)編碼方法[12]，即工序加工時(shí)間個(gè)體中的基因值表示對(duì)應(yīng)工序加工時(shí)間的某一樣本值，這種編碼可以直接在解的表現(xiàn)上進(jìn)行遺傳操作。由于工序加工時(shí)間為不確定性變量，若各工序加工時(shí)間在其對(duì)應(yīng)的取值之間隨機(jī)取值，將導(dǎo)致整個(gè)搜索空間龐大。依據(jù)上述定理1的結(jié)論可知：工序加工時(shí)間個(gè)體中的基因值可只取其對(duì)應(yīng)取值區(qū)間的上界值或下界值，從而大幅度壓縮調(diào)度搜索空間。

(2)交叉操作。工序加工時(shí)間種群的交叉操作采用單點(diǎn)交叉法[12]，即隨機(jī)確定一個(gè)交叉位置，然后對(duì)換交叉點(diǎn)之后的基因片段。

(3)變異操作。對(duì)工序加工時(shí)間種群采用單點(diǎn)變異方式[12]，即隨機(jī)確定一個(gè)變異位置，當(dāng)該位置上的基因值為對(duì)應(yīng)取值區(qū)間的上界值時(shí)，則變異為下界值；否則，變異為上界值。

(4)選擇操作。為提高遺傳算法的收斂速度，選擇操作采用保優(yōu)策略，即經(jīng)過交叉、變異后得到的新種群，和交叉、變異前的種群組合成一個(gè)大種群，計(jì)算大種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值，選取適應(yīng)度值大的個(gè)體組成遺傳算法進(jìn)化后的新種群。

4.2外層Min優(yōu)化過程的遺傳算法設(shè)計(jì)

在當(dāng)前工序加工時(shí)間種群取得最差性能的條件下，外層Min優(yōu)化過程的主要任務(wù)是在調(diào)度順序種群內(nèi)尋找最差性能值最小的調(diào)度順序方案。外層遺傳算法的主要操作如下：

(1)編碼方法。調(diào)度順序個(gè)體采用基于操作的編碼方式[12]，即將每個(gè)染色體用n×m個(gè)代表操作的基因組成，其中各工件號(hào)均出現(xiàn)m次。這種編碼方式的個(gè)體不僅保證了工藝約束條件，而且其任意基因串的置換排序均能表示可行調(diào)度，遺傳操作過程中不會(huì)產(chǎn)生非法解。對(duì)應(yīng)的解碼過程參見文獻(xiàn)[12]。

(2)交叉操作。調(diào)度順序種群采用基于POX的交叉算子操作[13]；這種交叉方式得到的子代能很好的繼承父代優(yōu)良特征，且子代總是可行的。

(3)變異操作。變異采用兩點(diǎn)互換變異操作[12]，即隨機(jī)交換兩不同位置上的不同基因。

(4)選擇操作。同上。

5　仿真試驗(yàn)及分析

5.1JSSP-PTV仿真算例

每一工件的提前和拖期懲罰系數(shù)從離散均勻分布[1,3]中隨機(jī)取值。

TSC-GA算法的相關(guān)試驗(yàn)參數(shù)為：兩個(gè)種群規(guī)模均為40，交叉概率均為0.8，變異概率均為0.2，整個(gè)算法的最大迭代次數(shù)kmax=100。仿真環(huán)境為：Windows XP Professional操作系統(tǒng)，CPU2.8 GHz，內(nèi)存2.0 GB，仿真工具采用MATLAB2010。

為詳細(xì)分析TSC-GA算法優(yōu)化JSSP-PTV問題時(shí)的有效性，取β1=0.2、β2=0.4中一個(gè)具體的5×3(n×m)問題進(jìn)行詳細(xì)仿真分析，具體參數(shù)如表3所示。

表3　JSSP-PTV問題的5×3(n×m)算例數(shù)據(jù)

5.2TSC-GA算法求解Minimax調(diào)度模型的震蕩收斂性分析

由前述的Minimax問題特征分析可知，Minimax優(yōu)化過程包括最小化和最大化兩個(gè)相反的優(yōu)化進(jìn)程，因此，其收斂過程必然具有震蕩收斂趨勢。以上述5×3的JSSP-PTV問題為例，TSC-GA算法求解Minimax調(diào)度模型的收斂曲線如圖3所示。

圖3　調(diào)度順序種群和工序加工時(shí)間種群的協(xié)同進(jìn)化曲線

首先進(jìn)行震蕩收斂性驗(yàn)證。從圖3可以看出，TSC-GA算法的進(jìn)化過程為一個(gè)震蕩收斂曲線，有下降過程和上升過程，但最終趨于收斂。在下降過程中：外層調(diào)度順序種群進(jìn)化速度快于內(nèi)層工序加工時(shí)間種群的進(jìn)化速度，此時(shí)外層Min優(yōu)化過程起主導(dǎo)作用；在上升過程中：內(nèi)層工序加工時(shí)間種群進(jìn)化速度快于外層調(diào)度順序種群的進(jìn)化速度，此時(shí)內(nèi)層Max優(yōu)化過程起主導(dǎo)作用。因此，由于遺傳算法固有的隨機(jī)性特征，使得外層和內(nèi)層兩個(gè)優(yōu)化空間的進(jìn)化速度不一致，從而使得Minimax調(diào)度問題具有顯著的震蕩收斂特性。

然后，對(duì)雙空間協(xié)同遺傳算法收斂性進(jìn)行分析：雙空間協(xié)同遺傳算法基于一種交替進(jìn)化的思想，內(nèi)層Max優(yōu)化和外層Min優(yōu)化過程是交替并列進(jìn)行尋優(yōu)的，內(nèi)層Max優(yōu)化過程利用外層的調(diào)度順序種群評(píng)價(jià)自身個(gè)體適應(yīng)度，指導(dǎo)自身種群進(jìn)化方向；外層Min優(yōu)化過程利用內(nèi)層的工序加工時(shí)間種群評(píng)價(jià)自身個(gè)體適應(yīng)度，指導(dǎo)自身種群進(jìn)化方向。因此，內(nèi)層Max優(yōu)化過程和外層Min優(yōu)化過程都有自身單獨(dú)進(jìn)化時(shí)種群的最優(yōu)值，雖然兩條曲線有各自的進(jìn)化軌跡，但當(dāng)算法整體收斂時(shí)，即找到最優(yōu)調(diào)度順序及對(duì)應(yīng)取到最差性能值的工序加工時(shí)間時(shí)，兩曲線必然收斂到一起。

5.3工序加工時(shí)間過濾機(jī)制及算法有效性驗(yàn)證

為了驗(yàn)證基于凸函數(shù)定理(定理1)的工序加工時(shí)間可行域過濾機(jī)制對(duì)內(nèi)層Max優(yōu)化過程的有效性，采用與5.2節(jié)相同的調(diào)度算例進(jìn)行仿真試驗(yàn)。當(dāng)外層遺傳算法給定一個(gè)調(diào)度順序后，Minimax調(diào)度模型中的式(1)將轉(zhuǎn)化為單一的Max優(yōu)化問題。為保證算例的連續(xù)性及方便相關(guān)結(jié)果的分析，取5.2節(jié)中尋優(yōu)結(jié)果得到的調(diào)度順序[5 3 2 2 2 3 5 1 5 1 4 3 4 1 4]進(jìn)行分析。圖4所示為在該調(diào)度順序條件下，內(nèi)層遺傳算法在運(yùn)用工序加工時(shí)間可行域過濾機(jī)制(即工序加工時(shí)間隨機(jī)變量僅取區(qū)間的上下界)和未運(yùn)用過濾機(jī)制(即工序加工時(shí)間變量隨機(jī)取值)兩種情況下的進(jìn)化曲線圖。

圖4　給定調(diào)度順序條件下內(nèi)層Max進(jìn)化曲線

下面對(duì)工序加工時(shí)間過濾機(jī)制有效性進(jìn)行驗(yàn)證分析。從圖4可以看出，在相同迭代次數(shù)情況下，曲線1的E/T值大于曲線2的值；另外，曲線1在第5代就收斂至最大值387，而曲線2在內(nèi)層遺傳算法超過最大迭代次數(shù)時(shí)仍未收斂到最大值。因此，曲線1在求解質(zhì)量和求解效率兩方面明顯優(yōu)于曲線2。分析其原因如下：由于在給定調(diào)度順序條件下，內(nèi)層Max優(yōu)化方向是E/T指標(biāo)值越大越好；而凸函數(shù)定理1將工序加工時(shí)間的取值限定在其取值區(qū)間的上界或下界，因此內(nèi)層遺傳算法只需在各工序加工時(shí)間取上下界所形成的可行域內(nèi)尋優(yōu)，從而避免了遍歷或枚舉工序加工時(shí)間取值區(qū)間所消耗的大量計(jì)算時(shí)間。因此，基于凸函數(shù)定理1的工序加工時(shí)間過濾機(jī)制顯著改善了內(nèi)層Max過程的優(yōu)化效率和解的質(zhì)量。

接著，對(duì)雙空間協(xié)同遺傳算法有效性進(jìn)行驗(yàn)證。圖4中調(diào)度解的最大化進(jìn)化過程收斂到最大值387，與5.2節(jié)中圖3的結(jié)果一致，說明雙空間協(xié)同進(jìn)化遺傳算法能夠得到調(diào)度解的真實(shí)最差性能值(387)；圖5中的曲線1為同上的調(diào)度解[5 3 2 2 2 3 5 1 5 1 4 3 4 1 4]對(duì)應(yīng)的內(nèi)層Max尋優(yōu)進(jìn)化曲線，其他曲線為隨機(jī)選取的100個(gè)調(diào)度順序所對(duì)應(yīng)的內(nèi)層Max尋優(yōu)進(jìn)化曲線，從圖中可以看出，曲線1收斂的最大E/T指標(biāo)值(387)最小，其他曲線收斂值都在曲線1之上，所以，通過本文所設(shè)計(jì)雙空間協(xié)同遺傳算法求解Minimax調(diào)度問題，能夠得到最差性能最優(yōu)的調(diào)度順序。即雙空間協(xié)同遺傳算法能夠準(zhǔn)確求得Minimax模型的調(diào)度解。

圖5　調(diào)度順序的內(nèi)層max進(jìn)化曲線對(duì)比圖

5.4Minimax調(diào)度解的魯棒性及算法高效性驗(yàn)證

5.4.1Minimax調(diào)度解魯棒性驗(yàn)證

在工序時(shí)間不確定條件下，調(diào)度最終方案是一個(gè)調(diào)度順序。為了驗(yàn)證Minimax調(diào)度模型的魯棒性，即已得到的調(diào)度順序的E/T性能指標(biāo)在工序加工時(shí)間實(shí)際隨機(jī)取值情況下仍保持較優(yōu)的性能值，針對(duì)與5.2節(jié)相同的JSSP-PTV調(diào)度算例和參數(shù)，選擇兩個(gè)調(diào)度順序結(jié)果，一個(gè)是利用本文提出的TSC-GA算法求解Minimax調(diào)度模型所獲得的調(diào)度順序方案(Minimax調(diào)度解)，另一個(gè)是對(duì)各個(gè)工序加工時(shí)間隨機(jī)變量分別取其期望值，形成一個(gè)確定性調(diào)度問題，并利用本文的遺傳算法對(duì)其進(jìn)行求解而獲得一個(gè)調(diào)度順序方案(期望模型調(diào)度解)；然后，針對(duì)已知的兩個(gè)調(diào)度順序，在工序加工時(shí)間值域內(nèi)隨機(jī)取值，共進(jìn)行5000次試驗(yàn)，二者的E/T指標(biāo)值的分布參見圖6、圖7。

圖6　Minimax調(diào)度解在工序加工時(shí)間隨機(jī)取值條件下的E/T性能分布

圖7　期望模型調(diào)度解在工序加工時(shí)間隨機(jī)取值條件下的E/T性能分布

圖6和圖7中的黑點(diǎn)表示5000次試驗(yàn)中，各調(diào)度方案對(duì)應(yīng)的最差性能點(diǎn)(即E/T指標(biāo)的最大值)。從圖6可以看出：5000個(gè)樣本的所有指標(biāo)都在TSC-GA算法求解Minimax調(diào)度模型獲得的性能界(387)以內(nèi)，由此證明了在工序加工時(shí)間不確定環(huán)境下，應(yīng)用凸函數(shù)定理(定理1)顯著壓縮調(diào)度搜索空間后，能保證樣本的性能指標(biāo)始終在Minimax調(diào)度解對(duì)應(yīng)的最差性能邊界內(nèi)。另外，對(duì)比圖6和圖7中的最差性能點(diǎn)可以發(fā)現(xiàn)：在工序加工時(shí)間隨機(jī)取值條件下，Minimax調(diào)度解對(duì)應(yīng)的最差性能(E/T為362)小于期望模型調(diào)度解在相同試驗(yàn)下所得到的最差性能(392)，因此，對(duì)于Minimax調(diào)度解和期望模型調(diào)度解對(duì)應(yīng)的兩個(gè)調(diào)度順序而言，前者的E/T性能在工序加工時(shí)間隨機(jī)取值情況下仍保持了相對(duì)較優(yōu)的性能，即Minimax調(diào)度解的魯棒性能較好。

5.4.2雙空間協(xié)同遺傳算法高效性驗(yàn)證

表4　最差性能偏移率AWI試驗(yàn)結(jié)果

由表4的仿真數(shù)據(jù)可知：

(1)AWI指標(biāo)始終為負(fù)值，說明工序加工時(shí)間在其取值區(qū)間內(nèi)隨機(jī)取值時(shí)，Minimax調(diào)度解對(duì)應(yīng)的最大E/T指標(biāo)值均優(yōu)于期望模型調(diào)度解對(duì)應(yīng)的最大E/T指標(biāo)，這說明Minimax調(diào)度解在不同調(diào)度規(guī)模、不同工序加工時(shí)間取值范圍條件下，其E/T指標(biāo)值仍保持相對(duì)較優(yōu)水平，因此，Minimax模型調(diào)度解的魯棒性始終要優(yōu)于期望模型調(diào)度解，采用Minimax模型能更好的應(yīng)對(duì)不確定性因素的隨機(jī)擾動(dòng)。

(2)所有算例中，T1的值都小于T2，說明TSC-GA的求解效率顯著高于TGAI，這是由兩種算法的求解機(jī)制所決定的：首先，TGAI算法中，對(duì)于外層調(diào)度順序種群中的每個(gè)調(diào)度順序個(gè)體，尋優(yōu)其對(duì)應(yīng)的最差性能值都需要調(diào)度一個(gè)完整的內(nèi)層Max遺傳算法，即內(nèi)層工序加工時(shí)間種群進(jìn)行連續(xù)多次迭代尋優(yōu)，因此外層調(diào)度順序種群進(jìn)化一代都會(huì)導(dǎo)致內(nèi)層Max過程耗費(fèi)大量時(shí)間，所以兩層嵌套機(jī)制尋優(yōu)效率低；其次，很多調(diào)度順序個(gè)體在遺傳算法的選擇操作時(shí)由于適應(yīng)度函數(shù)值差會(huì)被舍棄，對(duì)于這些被舍棄的個(gè)體，前期通過完整內(nèi)層遺傳算法求其目標(biāo)函數(shù)值所花費(fèi)的計(jì)算時(shí)間都是無用功，故TGAI尋優(yōu)效率進(jìn)一步降低。而TSC-GA算法進(jìn)化過程中每次都是單次迭代，兩種群個(gè)體的目標(biāo)函數(shù)值都逐步向各自的最優(yōu)解靠攏，在交替進(jìn)化的過程中如果已經(jīng)出現(xiàn)了適應(yīng)度函數(shù)值很差的個(gè)體，通過選擇機(jī)制會(huì)將其舍去，不需要再花費(fèi)多余的計(jì)算時(shí)間對(duì)其尋優(yōu)，因此相對(duì)于TGAI，TSC-GA算法的求解效率顯著提高。

6　結(jié)論

(1)針對(duì)帶有E/T非正規(guī)指標(biāo)的不確定作業(yè)車間調(diào)度問題，提出并證明了有效過濾調(diào)度搜索空間的凸函數(shù)定理，即在給定調(diào)度順序的條件下，所有工件E/T指標(biāo)的最大值在工序加工時(shí)間可行域的頂點(diǎn)處取得；并依據(jù)此定理將工序加工時(shí)間種群中的個(gè)體取值限定在其取值區(qū)間的上界或下界，有效避免了因遍歷或枚舉各工序加工時(shí)間的全部值域所耗費(fèi)的大量計(jì)算代價(jià)，從而顯著提升了調(diào)度算法的搜索效率。

(2)針對(duì)Minimax問題存在的雙空間尋優(yōu)特性，提出了一種調(diào)度順序種群和工序加工時(shí)間種群的交替進(jìn)化機(jī)制，即在外層給定調(diào)度順序的條件下，內(nèi)層Max優(yōu)化過程的主要任務(wù)是在工序加工時(shí)間可行域內(nèi)尋找該調(diào)度順序?qū)?yīng)的最大E/T指標(biāo)值；而在當(dāng)前工序加工時(shí)間種群取得最差性能的條件下，外層Min優(yōu)化過程的主要任務(wù)是在調(diào)度順序種群內(nèi)尋找最差性能值最小的調(diào)度順序方案。

(3)不確定調(diào)度問題必然與調(diào)度決策者的喜好、決策風(fēng)格密切相關(guān)，而Minimax方法屬于一類保守、穩(wěn)健的決策分析方法，它可以在已知信息量少、擾動(dòng)因素復(fù)雜等工況下定量得到調(diào)度指標(biāo)的性能界，從而為調(diào)度決策者預(yù)估最差工況及其性能指標(biāo)值、采取主動(dòng)穩(wěn)健的調(diào)度措施等提供支持。

[1]Pindo M L. Scheduling: Theory, Algorithms, and Systems[M]. 4ed.Berlin:Springer, 2012.

[2]Goren S, SabuncuoluI. Optimization of Schedule Robustness and Stability under Random Machine Breakdowns and Processing Time Variability[J]. IIE Transactions, 2009, 42(3):203-220.

[3]Lei D. IntervalJob Shop Scheduling Problems[J]. The International Journal of Advanced Manufacturing Technology, 2012, 60(1/4): 291-301.

[4]Daniels R L, Kouvelis P. Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-stage Production[J]. Institute for Operations Research and the Management Sciences, 1995,41(2):363-376.

[5]劉琳，古寒雨，席裕庚. 加工時(shí)間不確定的Just-in-time單機(jī)魯棒調(diào)度[J]. 控制與決策，2007,22(10)：1151-1156.

Liu Lin, Gu Hanyu, Xi Yugeng. Robust Scheduling in a Just-in-time Single Machine System with Processing Time Uncertainty[J]. Control and Decision, 2007,22(10):1151-1156.

[6]Xu X Q, Cui W T, Lin J, et al. Robust Makespan Minimization in Identical Parallel Machine Scheduling Problem with Interval Data[J]. International Journal of Production Research, 2013，51(12):1-17.

[7]Herrmann J W. A Genetic Algorithm for a Minimax Network Design Problem[J]. Technical Research Report, 1999,99(12).

[8]Jensen M T. A New Look at Solving Minimax Problems with Coevolution[C]//MIC’2001-4th Metaheuristics International Conference. Porto, Portugal ,2001:103-107.

[9]鄭泳凌，馬龍華，錢積新. SGA(Simplex-Genetic Algorithm):一類求解Minimax問題的通用算法[J].系統(tǒng)工程理論與實(shí)踐，2002,22(12):33-38.

Zheng Yongling, Ma Longhua, Qian Jixin. SGA(Simplex-Genetic Algorithm)：a Universal Algorithm for Solving Minimax Problem[J]. Systems Engineering-theory & Practice, 2002, 22(12):33-38.

[10]Jensen M. Finding Worst-Case Flexible Schedules Using Coevolution[C]//GECCO 2001-In Genetic and Evolutionary Computation Conference. San Francisco,USA, 2001:1144-1151.

[11]同濟(jì)大學(xué)數(shù)學(xué)系.高等數(shù)學(xué)(第六冊(cè))[M].北京：高等教育出版社，2007.

[12]王凌.車間調(diào)度及其遺傳算法[M].北京：清華大學(xué)出版社，2003.

[13]張超勇，饒運(yùn)清，劉向軍，等. 基于POX交叉的遺傳算法求解Job-Shop調(diào)度問題[J].中國機(jī)械工程，2004，15(23)：2149-2153.

Zhang Chaoyong, RaoYunqing, Liu Xiangjun, et al. An Improved Genetic Algorithm for the Job Shop Scheduling Problem[J]. China Mechanical Engineering,2004,15(23)：2149-2153.

(編輯郭偉)

Minimax model and Two Space Co-evolutionary Genetic Algorithm for Job Shop Scheduling Problem

Yang HonganXi ZhichengXia ChangkaiWang Jinguo

Key Laboratory of Contemporary Design and Integrated Manufacturing Technology,Northwestern Polytechnical University,Xi’an,710072

For the job shop scheduling problem with processing time variability, a conservative and robust Minimax analysis method was proposed to estimate the worst scenario and its corresponding bound of scheduling performance indicator. A Minimax model was formulated based on the earli E/T penalty cost of each job. To solve the huge search space problem of traditional traversal or enumeration methods, a convex function theorem was proposed and proved, which can constrict and filter the processing time ranges effectively for a given scheduling sequence, and a kind of job processing times filtering mechanism was proposed based on this convex function theorem. Based on the feature of two space optimization in solving Minimax problem, a two space co-evolutionary genetic algorithm was designed with the consideration of the alternate evolutions between scheduling sequence population and processing time population. Finally, the test results demonstrate that both of the proposed filtering mechanism and two space co-evolutionary algorithm perform effectively.

job shop scheduling; processing time variability; earliness/tardiness(E/T); Minimax; two space co-evolution

2013-11-04

國家自然科學(xué)基金資助項(xiàng)目(50705076)；西北工業(yè)大學(xué)研究生創(chuàng)業(yè)種子基金資助項(xiàng)目(Z2013047)

TP301DOI：10.3969/j.issn.1004-132X.2015.03.009

楊宏安，男，1972年生。西北工業(yè)大學(xué)機(jī)電學(xué)院副教授、博士。主要研究方向?yàn)檐囬g調(diào)度優(yōu)化、智能優(yōu)化算法、制造執(zhí)行系統(tǒng)等。席志成，男，1988年生。西北工業(yè)大學(xué)機(jī)電學(xué)院碩士研究生。夏常凱，男，1988年生。西北工業(yè)大學(xué)機(jī)電學(xué)院碩士研究生。王經(jīng)國，男，1989年生。西北工業(yè)大學(xué)機(jī)電學(xué)院碩士研究生。