楊宏安　席志成　夏常凱　王經國

西北工業(yè)大學現代設計與集成制造教育部重點實驗室，西安，710072

Job Shop調度問題的Minimax模型及雙空間協同遺傳算法

楊宏安席志成夏常凱王經國

西北工業(yè)大學現代設計與集成制造教育部重點實驗室，西安，710072

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

作業(yè)車間調度；工序加工時間不確定；提前/拖期；Minimax；雙空間協同進化

0　引言

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

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

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

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

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

1　Job Shop調度的Minimax模型及其特征分析

1.1Minimax調度模型

表1　Minimax調度模型的符號說明

JSSP-PTV問題的Minimax調度模型如下：

(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工序加工時間不確定條件下的Minimax問題特征分析

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

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

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

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

2　內層Max優(yōu)化的凸函數定理及工序加工時間可行域的過濾機制

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

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

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)推導出

λ 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)

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

根據凸函數性質[11]“有限個凸函數的非負線性組合仍然是凸函數”，則由上述關于任一工件的提前/拖期懲罰成本是s的凸函數(性質1)，對于Minimax模型中的調度目標函數(式(1))，有以下推論：

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

(11)

縮減為

(12)

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

3　調度順序種群和工序加工時間種群的交替進化機制

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

圖1　調度順序和工序加工時間雙種群的交替進化示意圖

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

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

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

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

圖2　雙空間協同遺傳算法邏輯框圖

圖2的處理邏輯如下：

(1)初始化。隨機產生調度順序種群Px(0)和加工時間種群Ps(0)，令k=0,kmax=100。

(3)調度順序種群進化操作。以1/h(x)為適應度函數，對Px(k)進行復制、交叉和變異操作，產生新種群Px(k+1)。

(5)加工時間種群進化操作。以g(s)為適應度函數，對Ps(k)進行復制、交叉和變異操作，產生新種群Ps(k+1)。

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

(7)算法結束。

4.1內層Max優(yōu)化過程中的遺傳算法設計

在外層給定調度順序的條件下，內層Max優(yōu)化過程的主要任務是在工序加工時間可行域內尋找該調度順序對應的最大提前/拖期懲罰成本(即E/T)懲罰值。內層遺傳算法的關鍵操作如下：

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

(2)交叉操作。工序加工時間種群的交叉操作采用單點交叉法[12]，即隨機確定一個交叉位置，然后對換交叉點之后的基因片段。

(3)變異操作。對工序加工時間種群采用單點變異方式[12]，即隨機確定一個變異位置，當該位置上的基因值為對應取值區(qū)間的上界值時，則變異為下界值；否則，變異為上界值。

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

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

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

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

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

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

(4)選擇操作。同上。

5　仿真試驗及分析

5.1JSSP-PTV仿真算例

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

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

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

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

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

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

圖3　調度順序種群和工序加工時間種群的協同進化曲線

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

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

5.3工序加工時間過濾機制及算法有效性驗證

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

圖4　給定調度順序條件下內層Max進化曲線

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

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

圖5　調度順序的內層max進化曲線對比圖

5.4Minimax調度解的魯棒性及算法高效性驗證

5.4.1Minimax調度解魯棒性驗證

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

圖6　Minimax調度解在工序加工時間隨機取值條件下的E/T性能分布

圖7　期望模型調度解在工序加工時間隨機取值條件下的E/T性能分布

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

5.4.2雙空間協同遺傳算法高效性驗證

表4　最差性能偏移率AWI試驗結果

由表4的仿真數據可知：

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

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

6　結論

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

(2)針對Minimax問題存在的雙空間尋優(yōu)特性，提出了一種調度順序種群和工序加工時間種群的交替進化機制，即在外層給定調度順序的條件下，內層Max優(yōu)化過程的主要任務是在工序加工時間可行域內尋找該調度順序對應的最大E/T指標值；而在當前工序加工時間種群取得最差性能的條件下，外層Min優(yōu)化過程的主要任務是在調度順序種群內尋找最差性能值最小的調度順序方案。

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

[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]劉琳，古寒雨，席裕庚. 加工時間不確定的Just-in-time單機魯棒調度[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)工程理論與實踐，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]同濟大學數學系.高等數學(第六冊)[M].北京：高等教育出版社，2007.

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

[13]張超勇，饒運清，劉向軍，等. 基于POX交叉的遺傳算法求解Job-Shop調度問題[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

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

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

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