薛玲玲

(1.中國科學院沈陽自動化研究所 機器人學國家重點實驗室，遼寧 沈陽 110169；2.中國科學院 網(wǎng)絡化控制系統(tǒng)重點實驗室，遼寧 沈陽 110169；3.中國科學院 機器人與智能制造創(chuàng)新研究院，遼寧 沈陽 110169；4.中國科學院大學，北京 100049)

0 引言

作業(yè)車間調度問題(Job-shop Scheduling Problem, JSP)作為生產調度管理系統(tǒng)中的一種重要類型，屬于典型的NP-hard問題[1]。作業(yè)車間調度通過給出合理的生產計劃，保證生產順利而有序地進行，從而實現(xiàn)提高生產效率和滿足用戶需求的價值。因此，JSP一直受到學術界和工業(yè)界的熱切關注。

作為一類典型的組合優(yōu)化問題，當JSP規(guī)模較小時，可以采用線性規(guī)劃法[2]、分支定界法[3]等精確法尋找最優(yōu)解?？紤]到其NP-hard的特性，當生產規(guī)模增加時，會造成解空間的組合爆炸，采用精確法很難在可接受的時間內找到合適的解，而以智能優(yōu)化算法為代表的近似法，以其求解速度快、求解質量高等優(yōu)點，成為了求解JSP更有價值的實用方法。文獻[4-5]從提高機器空閑時間的角度出發(fā)，對文獻[6]提出的鄰域搜索遺傳算法的鄰域結構進行改進，分別提出了基于空閑時間的鄰域結構和新型的鄰域結構;文獻[7]提出一個離散的粒子群優(yōu)化算法求解完工時間最小化的JSP;文獻[8]提出一個基于關鍵路徑指導的Giffler & Thompson(GT)交叉算子，能夠根據(jù)父代個體的關鍵路徑識別重要的遺傳信息;文獻[9]分別采用局部搜索策略和多交叉方法對遺傳算法的變異和交叉操作進行改進，將改進后的遺傳算法用于求解JSP;文獻[10]將遺傳灰狼算法與變鄰域搜索算法相結合，求解總能耗成本與總完工時間最小的低碳JSP;文獻[11]提出一種遺傳算法與基于鄰域結構的鄰域搜索算法相結合的模因算法求解JSP;文獻[12]提出一個基于模因算法的三階多種群混合算法。通過對當前已有方法的研究可知，采用單一的優(yōu)化算法求解JSP時，總存在搜索空間有限導致早熟收斂的問題。將全局搜索能力強的算法與局部搜索算法結合起來，既能加快算法的收斂速度，又能避免陷入局部最優(yōu)。不同算法的結合使用是當前最常使用的改進方向。

本文結合JSP的特點，提出一種基于塊結構鄰域搜索的遺傳算法。該算法為提高群體中個體的適應度，延遲算法早熟，引入子代選擇機制[13]。通過分析遺傳算法中編碼方式可知，采用基于工序的編碼方式生成的個體，在進行隨意位置的交換、移動等操作時都不會生成不可行個體，因此將基于工序的編碼方法引入到鄰域搜索過程中。最后，將本文提出的算法與其他現(xiàn)有算法在基準算例上進行對比，驗證算法的有效性。

1 作業(yè)車間調度問題描述

JSP可以描述為N個工件在M臺機器上加工，工件在不同機器上的加工時間已知，且工件的加工路徑確定。如圖1所示，假設有兩個工件Job1,Job2在4臺機器上加工。其中Job1的加工順序為M1→M3→M2→M4，Job2的加工順序為M2→M1→M4→M3。

下面對作業(yè)車間調度問題進行如下假設：

(1)所有工件在零時刻可得；

(2)同一工件不能同時在不同機器上加工，同一機器同一時間只能加工一個工件；

(3)工件在某一機器上一旦開始加工不能停止；

(4)工件上一步工序加工完成之后才能加工下一步工序；

(5)機器只有加工完當前工序才能加工下一個工序；

(6)本文假設工件在不同機器之間的轉運時間忽略不計，僅考慮工件在機器上的加工時間。

相關概念如表1所示。

表1 作業(yè)車間調度問題相關概念

以最大完工時間最小化為優(yōu)化目標，目標函數(shù)為

Cmax=min max (ctji)。

(1)

2 改進的鄰域搜索遺傳算法

本文將具有隱形并行、全局搜索能力強的遺傳算法與專注個體局部搜索的鄰域搜索算法相結合，提出一種基于塊結構鄰域搜索的遺傳算法，算法流程如圖2所示。該算法主要采用基于工序的編碼方法和主動解碼方法對個體進行編碼和解碼，利用解碼后工序的開始加工時間對個體進行排序，使同一機器上工序加工順序與實際加工順序一致；采用精英個體保存策略保存每一代最優(yōu)個體；遺傳操作中采用二元錦標賽選擇個體，交叉操作采用改進的基于工序的交叉操作，并將交叉操作嵌入到子代選擇機制中；采用互換變異與逆轉變異兩種變異方式生成變異個體。其中，鄰域搜索算法中的鄰域結構采用改進的基于塊結構的鄰域構建方法生成。

3 鄰域結構生成方法

3.1 鄰域結構

與采用隨機生成鄰域個體的方法相比，采用基于關鍵路徑生成的鄰域結構，對于求解以最小化最大完工時間的JSP能夠更好地提高鄰域搜索質量[14-15]。根據(jù)對基于關鍵工序塊的鄰域結構構建方法的研究可知，交換塊內相鄰工序不會縮短最大完工時間[16]。

本文主要采用工序交換和工序移動兩種方法構建鄰域結構，工序移動又包括工序前移和工序后移。假定關鍵路徑上兩工序u,v，工序u在v之前加工，即滿足ST(u)

工序交換、工序前移和工序后移對應的操作分別為：

EX(u,v):交換工序u和工序v的位置；

moveA(v,u):將工序v移動到工序u的前面；

moveB(u,v):將工序u移動到工序v的后面。

結合工序編碼的特點可知，采用基于工序編碼生成的鄰域不存在不可行解的情況，因此不需要進行可行性分析。但在生成的鄰域個體集中，可能存在鄰域個體之間或鄰域個體與原個體之間生成的調度方案相同的情況，即鄰域個體的冗余。為減少冗余個體的生成，本文提出以塊首工序或塊尾工序為中心，將其與塊內工序的移動和交換作為一個鄰域生成單元，通過工序間位置關系的分析，選擇合適的鄰域生成操作，減少冗余的鄰域個體。圖3給出了一個以塊首工序bk1為中心，該中心通過與塊內工序bkj交換、移動生成的鄰域結構單元。接下來，分別從與塊首/塊尾相鄰工序生成的鄰域單元以及非相鄰兩種情況，對鄰域的生成進行分析。

3.2 與塊首/塊尾相鄰工序的鄰域生成過程

由關鍵工序塊的概念可知，如果存在塊首bk1的工序緊前工序Jp[bk1]和塊尾bke的工序緊后工序Js[bke]，則一定在關鍵路徑上。由此可知，與塊內工序的交換有可能減小最大完工時間[16-19]。相鄰工序用u，v表示，根據(jù)工序u，Js[u]，v，Jp[v]的位置關系對工序交換和移動前后得到的調度方案進行分析。

(1)若Jp[v]，Js[u]均不在u，v之間，即工序的位置信息滿足pos(Jp[v])?[pos(u),pos(v)]，pos(Js[u])?[pos(u),pos(v)]，則工序交換，前移和后移生成的調度方案相同。

證明如果原調度方案S中Jp[v]，Js[u]均不在工序u,v之間，在不考慮其他加工工序時，按照開始加工時間可以將工序加工順序簡化為圖4a所示的加工順序：Jp[v]→u→v→Js[u];

工序u,v交換結果(如圖4b)：

EX(u,v)=Jp[v]→v→u→Js[u];

工序u后移結果(如圖4c)：

moveB(u,v)=Jp[v]→v→u→Js[u];

工序v前移結果(如圖4d)：

moveA(v,u)=Jp[v]→v→u→Js[u]。

由此可知，工序交換、工序前移和工序后移生成相同的調度方案，因此生成鄰域個體時，3個操作只需選擇一個即可。

(2)若Jp[v]不在工序u,v之間，Js[u]在工序u，v之間，即工序的位置信息滿足pos(Jp[v])?[pos(u),pos(v)]，pos(Js[u])∈[pos(u),pos(v)]，則工序交換與工序前移生成的調度方案相同，工序后移與原調度方案相同。

證明根據(jù)條件可知，工序u,v,Jp[v],Js[u]的加工順序為：Jp[v]→u→Js[u]→v;

工序u,v交換結果為：

EX(u,v)=Jp[v]→v→Js[u]→u=>

Jp[v]→v→u→Js[u];

工序v前移結果為：

moveA(v,u)=Jp[v]→v→u→Js[u];

工序u后移結果為：

moveB(u,v)=Jp[v]→Js[u]→v→u=>

Jp[v]→u→v→Js[u]

=Jp[v]→u→Js[u]→v。

由此可知，工序交換與工序前移生成的調度方案相同，工序后移生成的調度方案與原調度方案相同；生成鄰域時選擇工序交換或工序前移即可。

(3)若Jp[v]在工序u,v之間，Js[u]不在工序u，v之間，即工序的位置信息滿足pos(Jp[v])∈[pos(u),pos(v)]，pos(Js[u])?[pos(u),pos(v)]，則工序交換與工序后移生成的調度方案相同，工序前移與原調度方案相同。

證明根據(jù)條件可知，工序u,v,Jp[v],Js[u]的加工順序為：u→Jp[v]→v→Js[u];

工序u,v交換結果為：

EX(u,v)=v→Jp[v]→u→Js[u]=>

Jp[v]→v→u→Js[u];

工序v前移結果為：

moveA(v,u)=v→u→Jp[v]→Js[u]=>

Jp[v]→u→v→Js[u]

=u→Jp[v]→v→Js[u];

工序u后移結果為：

moveB(u,v)=Jp[v]→v→u→Js[u]。

由此可知，工序交換與工序后移生成的調度方案相同，工序前移生成的調度方案與原調度方案相同；生成鄰域時選擇工序交換或工序后移即可。

(4)若Jp[v],Js[u]均在工序u,v之間，即工序的位置信息滿足pos(Jp[v])∈[pos(u),pos(v)]，pos(Js[u])∈[pos(u),pos(v)]，則工序交換與工序前移生成的調度方案相同，工序后移生成的調度方案與原調度方案相同。

證明根據(jù)條件可知，如果工序Jp[v],Js[u]均在工序u,v之間，則可知stJs[u]=stv,且pos(Js[u])

工序u,v交換結果為：

EX(u,v)=v→Jp[v]→Js[u]→u=>

Jp[v]→v→u→Js[u];

工序v前移結果為：

moveA(v,u)=v→u→Jp[v]→Js[u]=>

Jp[v]→u→v→Js[u]

=u→Jp[v]→Js[u]→v;

工序u后移結果為：

moveB(u,v)=Jp[v]→Js[u]→v→u=>

Jp[v]→u→v→Js[u]

=u→Jp[v]→Js[u]→v。

由此可知，工序前移與工序后移生成的調度方案與原調度方案相同；生成鄰域時僅進行工序交換即可。

3.3 與塊首/塊尾非相鄰工序的鄰域生成過程

由于塊首工序與塊內工序交互生成鄰域過程和塊尾工序與塊內工序交換生成鄰域過程相似，選擇分析塊首工序與塊內工序交互過程。通過分析3.2節(jié)的結果可知，工序移動存在與原調度方案相重合或與交換生成鄰域方案相重合的情況。因此，首先對工序的有效移動條件進行分析。

3.3.1 塊首/塊尾工序有效移動條件分析

以塊首工序為例，對工序的有效移動條件進行分析。假定調度方案中，存在如圖5a所示的關鍵工序塊COB=[bk1,bk2,bk3,bk4,bke]，且塊首bk1的工序緊后工序Js[bk1]位于bk3與bk4之間，則可知塊首工序bk1有3個后移位置1、2、3。第1和第2種工序后移結果分別如圖5b和圖5c所示；第3種工序后移生成的調度方案如圖5d所示，與第2種移動結果相同。

因此可以得出一般化結論：塊首bk1移動到塊內工序bkj之后的條件為pos(Js[bk1])>pos(bkj);同理可得，塊尾bke移動到塊內工序bkj之前的條件為pos(Jp[bke])

3.3.2 塊內工序有效移動條件分析

以圖6a所示的調度方案為例，對塊內工序有效移動條件進行分析。進行前移的塊內工序有bk2,bk3,bk4，其中bk2為塊首相鄰工序，由工序序列可知其工序緊前工序Jp[bk2]與塊首工序的位置關系滿足pos(Jp[bk2])>pos(bk1)，移動結果如圖6b所示，生成新個體的調度方案與原個體相同；工序bk3的緊前工序Jp[bk3]與塊首工序的位置關系滿足pos(Jp[bk3])pos(bk1)，移動結果如圖6d所示，生成的新方案中實現(xiàn)了塊內工序bk3與bk4的交換，由文獻[16]中定理“交換塊內相鄰工序不會減小最大完工時間”可知，工序bk4的前移不能生成有效個體。

綜合以上分析，滿足塊內工序bkj前移條件為pos(Jp[bkj])

同理，塊內工序bkj后移條件為pos(Js[bkj])>pos(bke)。

3.3.3 與塊首非相鄰工序鄰域的生成過程

根據(jù)塊首工序后移條件與塊內工序前移的條件，給出滿足塊首bk1與塊內工序bkj的鄰域生成的條件：

(1)若pos(Js[bk1])pos(bk1)，即不滿足塊首后移和塊內工序bkj前移的條件，則不需要生成新鄰域個體。

證明由于pos(Js[bk1])

由于pos(Jp[bkj])>pos(bk1)，即移動結果如圖6b所示，不滿足塊內工序bkj有效前移條件；

因此僅需對工序交換進行判斷，假定滿足給定條件的加工順序為：

bk1→Js[bk1]→bk2→…→Jp[bkj]→bki→…→

bkj→…→bke，

則工序交換結果為：

EX(bk1,bkj)=bkj→Js[bk1]→bk2→…→

Jp[bkj]→bki→…→bk1→…→bke

=Jp[bkj]→bk1→bk2→…→bkj→bki→…→

Js[bk1]→…→bke。

可知，關鍵工序塊內工序加工順序不變，與原調度方案相同。因此，該條件下不需要生成新鄰域個體。

(2)若pos(Js[bk1])

證明由于pos(Js[bk1])

由于pos(Jp[bkj])

假定滿足給定條件的加工順序為：

Jp[bkj]→bk1→Js[bk1]→bk2→…→bki→…→

bkj→…→bke，

則工序交換結果為：

EX(bk1,bkj)=Jp[bkj]→bkj→Js[bk1]→bk2

→…→bki→…→bk1→…→bke

=Jp[bkj]→bkj→bk1→bk2→…→bki→…

→Js[bk1]→…→bke；

工序前移結果為：

moveA(bkj,bk1)=Jp[bkj]→bkj→bk1→

Js[bk1]→bk2→…→bki→…→bke。

可知，工序交換和塊內工序前移生成的調度方案相同。

因此，該條件下僅需選擇工序交換或塊內工序前移即可。

(3)若pos(Js[bk1])>pos(bkj)，pos(Jp[bkj])>pos(bk1)，即滿足塊首工序有效后移，不滿足塊內工序有效前移的條件，則選擇工序交換或塊首工序后移之一即可。

證明由條件pos(Js[bk1])>pos(bkj)，即移動結果如圖5c所示，滿足塊首有效后移條件；

由于pos(Jp[bkj])>pos(bk1)，即移動結果如圖6b所示，不滿足塊內工序bkj有效前移條件；

假定滿足給定條件的加工順序為：

bk1→bk2→…Jp[bkj]→bkj→bki→

Js[bk1]→…→bke，

則可知工序交換結果為：

EX(bk1,bkj)=bkj→bk2→…Jp[bkj]→bk1→

bki→Js[bk1]→…→bke

=Jp[bkj]→bk2→…→bkj→bk1→

bki→Js[bk1]→…→bke；

塊首工序后移結果為：

moveB(bk1,bkj)=bk2→…Jp[bkj]→bkj

→bk1→bki→Js[bk1]→…→bke。

可知，工序交換和塊首工序后移生成的調度方案相同。

因此，該條件下選擇工序交換與塊首工序后移之一即可。

(4)若pos(Js[bk1])>pos(bkj)，pos(Jp[bkj])

證明由條件pos(Js[bk1])>pos(bkj)，即移動結果如圖5c所示，滿足塊首有效后移條件；

由條件pos(Jp[bkj])

假定滿足給定條件的加工順序為：

Jp[bkj]→bk1→bk2→…→bkj→bki

→Js[bk1]→…→bke，

則工序交換結果為：

EX(bk1,bkj)=Jp[bkj]→bkj→bk2→…→

bk1→bki→Js[bk1]→…→bke；

塊首工序后移結果為：

moveB(bk1,bkj)=Jp[bkj]→bk2→…→bkj→

bk1→bki→Js[bk1]→…→bke；

塊內工序bkj前移結果為：

moveA(bkj,1)=Jp[bkj]→bkj→bk1→bk2

→…→bki→Js[bk1]→…→bke。

3種情況下生成的調度方案均不相同且與原調度方案不同，由此可知，可以進行工序交換、塊首工序后移和塊內工序前移3種不同操作。

3.3.4 與塊尾非相鄰工序鄰域的生成過程

同理，根據(jù)塊尾工序前移與塊內工序后移的條件，給出4種不同條件下塊尾工序與塊內工序交互生成鄰域結構的條件：

(1)若pos(Jp[bke])>pos(bke)，且pos(Js[bkj])

(2)若pos(Jp[bke])>pos(bke)，pos(Js[bkj])>pos(bke)，即不滿足塊尾bke前移條件，但滿足塊內工序bkj后移的條件，則選擇工序交換或塊內工序后移之一即可。

(3)若pos(Jp[bke])

(4)若pos(Jp[bke])pos(bke)，即滿足塊尾bke前移條件，也滿足塊內工序bkj有效后移的條件，則進行工序交換、塊內工序后移和塊尾工序前移3個操作。

4 實驗與分析

為驗證算法的有效性，采用國際上通用的作業(yè)車間調度問題數(shù)據(jù)集作為測試數(shù)據(jù)集。實驗平臺為計算機處理器主頻為1.80 GHz,內存為8 GB,采用MATLAB編程實現(xiàn)。

4.1 局部搜索個體規(guī)模對車間調度性能的影響

為分析進入局部搜索個體占比λ的影響，取λ∈{0,0.05,0.1,0.2,0.5,0.8,1}，以通用的LA數(shù)據(jù)集中的LA01～LA20等20個數(shù)據(jù)集和FT的3個數(shù)據(jù)集為基準算例，以遺傳算法為基本框架，結合禁忌局部搜索算法對所選取的數(shù)據(jù)集進行測試，從而確定合適的占比λ。其中，每個數(shù)據(jù)集獨立運行10次。

參數(shù)設置如下：

(1)初始種群隨機生成，種群規(guī)模

其中：N為待加工工件個數(shù);M為數(shù)據(jù)集中機器個數(shù);Npop表示數(shù)據(jù)集的種群規(guī)模;Npop1表示進入局部搜索的種群規(guī)模。

(2)優(yōu)秀個體占種群規(guī)模的前2%；

(3)交叉概率Pc=0.8，變異概率Pm=0.45，

(4)終止條件：總迭代次數(shù)T=500，最優(yōu)適應度值連續(xù)L=30代不變或找到最優(yōu)目標值。

算法的測試結果如圖7所示。由圖7可知，λ占比越大，即進入局部搜索的個體越多，得到最優(yōu)解的概率越大。當λ=0時，即僅采用基本的遺傳算法，23個數(shù)據(jù)集中有12個算例完全沒有找到最優(yōu)解；當λ=1時，即種群中所有個體均進行局部搜索時，有22個算例找到最優(yōu)解(僅算例LA20未找到最優(yōu)解)。且由圖7可以看出，隨著λ值的增加，數(shù)據(jù)中能夠找到最優(yōu)解的概率會隨之增加，但算法運行時間也會隨之增加。因此，為均衡算法的尋優(yōu)效果與運算時間，λ值取0.1～0.2之間某一值即為合適，本文取λ=0.15。

不同λ值下數(shù)據(jù)集運行結果如表2所示。表2中：NBE表示N次運行得到最優(yōu)解的次數(shù)，NBF表示所有數(shù)據(jù)集N次運行均找到最優(yōu)解的數(shù)據(jù)集個數(shù);NNF表示所有數(shù)據(jù)集N次運行均未找到最優(yōu)解的數(shù)據(jù)集個數(shù);PNBF表示所有數(shù)據(jù)集N次運行找到最優(yōu)解的概率;avgK表示不同λ值算法的平均迭代次數(shù)。實驗中數(shù)據(jù)集共有23個，運行次數(shù)N=10。

表2 不同λ下數(shù)據(jù)集運行結果分析

4.2 算法有效性驗證實驗

由4.1節(jié)中的實驗結果可知，進入局部搜索的個體占比λ=0.15比較合適，即N1=0.15×N。同時，在給出的LA和FT數(shù)據(jù)集中存在一些易于找到最優(yōu)解的實例集，無法充分驗證算法的尋優(yōu)能力。因此，本文采用文獻[20]中所用9個較難找到最優(yōu)解的數(shù)據(jù)集作為測試數(shù)據(jù)集，算法參數(shù)設置與4.1節(jié)相同，算法的運算結果如表3所示。表3中：C*表示當前已知最優(yōu)解;Cbest表示算法獨立運行10次得到的最優(yōu)解;e表示算法找到的最優(yōu)解Cbest與當前已知最優(yōu)解C*之間的相對偏差，

表3 不同算法運行結果統(tǒng)計

續(xù)表3

(2)

首先，采用平均相對偏差MRE從整體的角度比較算法的性能。本文所提算法的MRE值為0.451，其他6篇文獻所提算法的MRE分別為0.456，0.384，0.518，3.842，1.565和3.075。由此可知，本文算法在整體性能上優(yōu)于其中5種算法，略遜于文獻[5]提出的算法。主要原因在于算法的求解質量不僅受迭代次數(shù)和終止條件的影響，還受到種群規(guī)模的影響。為保證算法的運行效率，本文將種群規(guī)模選取為數(shù)據(jù)集的工件數(shù)和機器數(shù)的常數(shù)倍。如果增加迭代次數(shù)或增加種群規(guī)模，能夠進一步提高終解質量。

另外，以本文所提算法找到的最優(yōu)解作為基準，與其他算法找到的最優(yōu)解進行對比，結果如表4所示，表中：NB表示本文算法找到的最優(yōu)解優(yōu)于對比算法的數(shù)目；NW表示本文算法找到的最優(yōu)解差于對比算法的數(shù)目；NE表示本文算法找到的最優(yōu)解與對比算法相同的數(shù)目。比較本文算法與基于鄰域結構改進相關文獻[4-5]的優(yōu)劣解。與文獻[4]相比，優(yōu)于文獻[4]的最優(yōu)解NB=2，差于文獻[4]的最優(yōu)解NW=3，文獻[4]算法性能略優(yōu)于本文提出的算法；與文獻[5]相比，兩者優(yōu)于解與差于解數(shù)目相當，因此性能相當。

表4 本文算法與其他算法最優(yōu)解優(yōu)劣對比分析

與文獻[7]提出的離散粒子群算法以及文獻[10]所提出的混合灰狼算法相比，本文找到的最優(yōu)解略優(yōu)于文獻[7]，且明顯優(yōu)于文獻[10]，可知本文算法的求解性能優(yōu)于文獻[7]與文獻[10]所提算法。與兩個改進的遺傳算法[8-9]相比，本文所提算法找到的最優(yōu)解個數(shù)明顯更多。

綜上分析可知，將遺傳算法與局部搜索算法相結合能夠顯著提高算法的局部搜索能力，實驗結果也表明了本文所提算法的有效性。

最后以數(shù)據(jù)集FT10和FT20為研究對象，分別給出算法找到的最優(yōu)解對應的工件加工甘特圖，如圖8所示。對于FT10數(shù)據(jù)集，算法在第37代開始收斂；對于FT20數(shù)據(jù)集，算法在第73代開始收斂。

5 結束語

本文提出一種基于塊結構的鄰域搜索遺傳算法，該算法結合了鄰域搜索算法的局部搜索和遺傳算法的全局搜索的優(yōu)勢，能夠有效地解決傳統(tǒng)遺傳算法在求解車間調度問題中種群多樣性差、易早熟等問題。

本文在基于工序編碼的工序序列上，采用基于關鍵工序塊的鄰域生成方法構建鄰域結構，有效地避免了不可行解的產生。為了解決鄰域構建中鄰域的冗余問題，本文提出了以關鍵工序塊中塊首工序或塊尾工序為中心，將中心工序與塊內工序的交換和移動作為鄰域單元。通過分析工序在工序序列中的位置信息，判斷鄰域生成前后是否存在相同的調度方案，提出了鄰域單元的冗余性判據(jù)條件。同時，針對傳統(tǒng)遺傳算法在算法進化過程中由于種群進化過程中個體相似度的增加，采用子代選擇機制對遺傳操作生成的子代個體進行尋優(yōu)，提高子代質量。

通過將該算法在不同規(guī)模的JSP上進行測試，對算法的有效性進行了驗證。當前的工作主要是算法的改進及對基準問題的測試，初步驗證了算法的可行性和有效性，下一步工作將主要集中在算法在實際場景的應用，以及對異常事件的處理。