基于逆序虛擬零部件的緊密銜接綜合調(diào)度算法

郭偉飛，宋豫川+，周 璠，雷 琦，呂向飛

(1.重慶大學(xué) 機械傳動國家重點實驗室，重慶 400030；2.重慶江增船舶重工有限公司，重慶 402263)

0 引言

生產(chǎn)調(diào)度是對一定時間段內(nèi)的企業(yè)資源進行優(yōu)化配置，以達到優(yōu)化某個或某些特定生產(chǎn)指標的目的。有效的調(diào)度優(yōu)化算法能縮短生產(chǎn)周期、降低生產(chǎn)成本、增加企業(yè)利潤和提高客戶滿意度[1]。傳統(tǒng)的生產(chǎn)調(diào)度研究一直習(xí)慣于將加工與裝配調(diào)度割裂開進行研究，主要針對的是加工調(diào)度，而對裝配調(diào)度研究較少，且多集中在大批量流水線作業(yè)產(chǎn)品上，普遍認為不存在物料短缺，沒有真正意義上考慮裝配約束。裝配線平衡和產(chǎn)品排序是目前裝配調(diào)度研究的主流方向，如魯建廈等[2]針對混流汽車裝配線排序問題，提出一種融入禁忌搜素算法的混合人工蜂群算法。李大雙等[3]提出一種將殖民競爭算法與延遲接受爬山算法相結(jié)合的混合算法，用于解決多約束雙邊裝配線平衡問題。在考慮裝配線節(jié)拍和日可用工時的約束下，鄭諧等[4]對飛機脈動式裝配線平衡問題進行了研究，并提出一種基于可行序列編碼方式的遺傳算法。因此，將加工與裝配一同處理的綜合調(diào)度問題被提出，并逐漸引起學(xué)者們的關(guān)注。經(jīng)過多年來的不斷發(fā)展，綜合調(diào)度問題已經(jīng)發(fā)展成為區(qū)別于作業(yè)車間調(diào)度問題和流水車間調(diào)度問題的第三類調(diào)度問題[5]。

目前，一些學(xué)者們已在綜合調(diào)度領(lǐng)域做了大量研究，并取得了一定的成果。以謝志強教授最為突出，他提出了一系列基于產(chǎn)品加工工藝樹的綜合調(diào)度算法，如基于擬關(guān)鍵路徑法(Allied Critical Path Method ,ACPM)和最佳適應(yīng)調(diào)度方法(Best Fit Scheduling Method, BFSM)的動態(tài)作業(yè)車間調(diào)度算法[6]、基于工序集的動態(tài)關(guān)鍵路徑多產(chǎn)品制造調(diào)度算法[7]、非緊密銜接工序動態(tài)車間調(diào)度算法[8]、基于交貨期緊迫度的綜合調(diào)度算法[9]、考慮后續(xù)工序的擇時綜合調(diào)度算法[10]和考慮串行工序緊密度的擇時綜合調(diào)度算法[11]等。綜合調(diào)度問題主要存在于單件小批量且對裝配組件具有較高精度要求的復(fù)雜產(chǎn)品，如模具。然而，事實上，在復(fù)雜產(chǎn)品實際加工生產(chǎn)中，由于生產(chǎn)工藝、存儲能力或者生產(chǎn)管理方式等原因，導(dǎo)致了緊密銜接約束限制的出現(xiàn)，它要求緊后工序的開始時間必須等于緊前工序的完成時間。目前，緊密銜接綜合問題大致可分為單一緊前工序緊密銜接的情形和非單一緊前工序緊密銜接的情形。李志敏[12]首先對第一種情形進行了研究，他在ACPM和BFSM調(diào)度策略的基礎(chǔ)上，提出一種移動交換法來滿足工序間的單一緊前工序緊密銜接約束，實現(xiàn)了對非柔性的復(fù)雜產(chǎn)品綜合調(diào)度問題的求解。然而，由于采用的ACPM調(diào)度策略造成緊后工序的開始時間往往不是其緊前工序的結(jié)束時間，需要額外的調(diào)整操作，增加了算法的復(fù)雜度。為了克服上述的不足，謝志強等[13]提出一種將具有單一緊前工序緊密銜接約束條件的工序組進行統(tǒng)一聯(lián)動的綜合調(diào)度算法，避免了額外的調(diào)整操作，降低了算法的復(fù)雜度，但仍存在忽略了長路徑上工序?qū)φ{(diào)度結(jié)果的影響因素。針對第二種情形，在上述研究成果的基礎(chǔ)上，謝志強等[14]綜合利用信號驅(qū)動、逆序調(diào)度和鎖定緊密銜接工序組的前沿貪心策略，提出一種基于逆序信號驅(qū)動的緊密銜接綜合調(diào)度算法，同時它具有復(fù)雜度低和能實現(xiàn)對緊密銜接緊前工序數(shù)無限制問題求解的優(yōu)勢。然而，上述這些分析方法或構(gòu)造性的方法比較適合小規(guī)模的復(fù)雜產(chǎn)品綜合調(diào)度問題，隨著問題規(guī)模的不斷增大，加之綜合調(diào)度問題中更為復(fù)雜的裝配約束關(guān)系，該類方法在計算求解時間方面受到一定的制約[15]。此外，以上算法屬于啟發(fā)式算法，它們雖然能夠?qū)μ囟ǖ膯栴}求得較好的解，但是算法通用性較差。

目前，已證明絕大多數(shù)生產(chǎn)調(diào)度問題都是NP-hard問題，不存在有效的多項式時間求解方法。因此，研究人員將研究目光投向了各種近似方法。尤其自20世紀80年代以來，受自然現(xiàn)象或物理規(guī)律啟發(fā)而發(fā)展起來的元啟發(fā)式算法，為解決復(fù)雜組合優(yōu)化的調(diào)度問題提供了新的手段并已發(fā)展成為主流方法。鑒于復(fù)雜產(chǎn)品綜合調(diào)度問題也屬于比較復(fù)雜的NP-hard問題，元啟發(fā)式算法與啟發(fā)式算法相比，更適應(yīng)于實際大規(guī)模的復(fù)雜產(chǎn)品綜合調(diào)度問題，可以較好地滿足實際問題的需求。目前，關(guān)于復(fù)雜產(chǎn)品綜合調(diào)度問題的元啟發(fā)式算法報道還不是很多，只有少數(shù)學(xué)者進行了研究。如王林平等[16-17]采用一種基于選擇解碼字符串(Selective Decoding String, SDS)解碼的遺傳算法來對綜合調(diào)度問題進行求解，它能保證經(jīng)SDS解碼方法轉(zhuǎn)化后生成符合問題約束的可行解。趙詩奎等[15]在提出虛擬零部件概念的基礎(chǔ)上設(shè)計出了一種基于遺傳算法的產(chǎn)品綜合調(diào)度算法，該算法通過一種基于虛擬零部件級別的分區(qū)編碼方式來保證初始種群的可行性，此外，它的遺傳操作方法也能保證生成的子代個體的可行性，同時實驗也表明該算法具有良好的求解速度和質(zhì)量。石飛等[18]進一步研究并提出一種基于工序約束鏈編碼的遺傳算法來求解綜合調(diào)度問題，該算法的最大優(yōu)勢在于設(shè)計的編碼方法能保證初始解空間的可行性和完備性。以上求解綜合調(diào)度問題的遺傳算法雖然具有各自的優(yōu)點，但也都存在一些明顯的不足，如SDS解碼方法無法保證遺傳操作過程中個體的可行性，導(dǎo)致在解的全域中進行搜索，極大地降低了算法的求解效率。基于虛擬零部件級別分區(qū)編碼的產(chǎn)品綜合調(diào)度算法中的分區(qū)編碼方式會在原本不存在順序約束關(guān)系的零部件之間強加上一層或多層約束關(guān)系，導(dǎo)致該編碼不具備完備性，限制了遺傳操作搜索的空間范圍，必然對算法的求解效率造成影響?；诠ば蚣s束鏈編碼的遺傳算法無法保證產(chǎn)生子代個體的可行性，需要進行額外的檢測和修復(fù)操作，這無疑增加了算法的計算量。綜上所述，不難看出目前求解復(fù)雜產(chǎn)品綜合調(diào)度問題的元啟發(fā)式算法普遍存在明顯的缺陷和不足。這也必然會制約求解更加復(fù)雜的緊密銜接綜合調(diào)度問題的元啟發(fā)式算法的發(fā)展，更令人遺憾的是，關(guān)于求解緊密銜接綜合調(diào)度問題的元啟發(fā)式算法的研究報道目前還尚未發(fā)現(xiàn)。

在眾多的元啟發(fā)式算法中，遺傳算法經(jīng)40多年的研究已進入一個比較成熟的階段，具有深厚的研究基礎(chǔ)。為了借鑒遺傳算法在綜合調(diào)度問題上已有的研究成果，本文將其應(yīng)用于求解緊密銜接綜合調(diào)度問題，建立了問題的數(shù)學(xué)模型，提出一種基于逆序虛擬零部件雙親孩子表示法的編碼方法，設(shè)計了能確保滿足復(fù)雜產(chǎn)品逆序虛擬零部件順序約束的遺傳算子以及兩種各具特色且能保證生成原問題的可行解的解碼方法，并通過多個實例驗證了算法的有效性和優(yōu)越性。

1 問題描述

綜合調(diào)度問題研究的是在邊加工邊裝配生產(chǎn)模式下如何優(yōu)化調(diào)度復(fù)雜產(chǎn)品工序，使其總用時最小。而緊密銜接綜合調(diào)度問題又增添了緊密銜接約束，屬于一種特殊的綜合調(diào)度問題。為了便于問題的分析，一般將加工和裝配工序統(tǒng)一為加工，加工和裝配設(shè)備統(tǒng)一為設(shè)備[19]。該問題可描述為：設(shè)有n道工序的復(fù)雜產(chǎn)品需要在m臺設(shè)備上進行加工，一道工序在某一時刻只能被一臺設(shè)備加工，一臺設(shè)備在某一時刻也只能加工一道工序；設(shè)備一旦加工某道工序，則中途不能中斷，直至加工完畢后方能加工其他工序；每道工序只能在其所有緊前工序加工完畢后，才能開始加工；存在緊密銜接約束的工序的開始加工時間必須是其緊密銜接的緊前工序的完工時間。若工序oi在設(shè)備Mk上加工，則Xik=1，否則Xik=0；Si、Tik和Ci分別為工序oi在其相應(yīng)加工設(shè)備上的開始時間、加工時間和完工時間；Fk為設(shè)備Mk的總空閑時間；Pi和Ni分別為工序oi的緊前工序集合和緊密銜接的緊前工序集合，顯然Ni?Pi，此外，在Pi和Ni分別存在的情況下，工序oj和ol分別為Pi和Ni中的任意一個工序。因此，該問題的數(shù)學(xué)模型為：

minCmax=min{max(Ci)}。

(1)

s.t.

min{Si}&min{Fk}；

(2)

Si≥max(Sj+Tjk′),Xik=1,Xjk′=1,oj∈Pi；

(3)

Si≥Sh+Thk,Xik=1,Xhk=1；

(4)

Cl=Si,ol∈Ni。

(5)

其中：式(1)中的max(Ci)表示復(fù)雜產(chǎn)品最后一道工序的結(jié)束時間，minCmax是綜合調(diào)度優(yōu)化目標，即復(fù)雜產(chǎn)品的總加工時間盡可能??；式(2)表示復(fù)雜產(chǎn)品各道工序應(yīng)盡早開始加工，且盡可能地縮短加工設(shè)備上的總空閑時間；式(3)中工序oj是工序oi的一個緊前工序，表示各個工序必須在其所有緊前工序之后加工；式(4)中工序oh是與工序oi同一臺加工設(shè)備的前一工序，表示同一加工設(shè)備上的工序只能依次進行加工；式(5)中工序ol是工序oi的一個緊密銜接的緊前工序，表示緊密銜接的緊前工序的完工時間是其緊密銜接的緊后工序的開始時間。

復(fù)雜產(chǎn)品的加工和裝配完全工藝圖是樹狀結(jié)構(gòu)，對應(yīng)的工藝圖被稱為產(chǎn)品的加工工藝樹，樹中節(jié)點代表工序，邊代表工藝約束的偏序關(guān)系[15]。針對部分工序間存在緊密銜接約束關(guān)系的復(fù)雜產(chǎn)品，則采用擴展加工工藝樹[20]來表示，它使用虛線框標出存在緊密銜接約束關(guān)系的工序。此外，由于在樹狀結(jié)構(gòu)的擴展加工工藝樹中存在一個父節(jié)點與多個子節(jié)點的偏序關(guān)系，因此，在擴展加工工藝樹中既可能存在單一緊前工序緊密銜接約束關(guān)系的情況，也可能存在非單一緊前工序緊密銜接約束關(guān)系的情況，如圖1所示。由于單一緊前工序緊密銜接約束關(guān)系也可視為非單一緊前工序緊密銜接約束關(guān)系的特例，因此，在本文中二者不作嚴格的區(qū)分，統(tǒng)一視為非單一緊前工序緊密銜接約束關(guān)系的情況。從圖1中的復(fù)雜產(chǎn)品擴展加工工藝樹不難看出，緊密銜接綜合調(diào)度問題不僅需要考慮工序間的先后順序約束關(guān)系，還需要考慮工序間特殊的緊密銜接約束關(guān)系，導(dǎo)致工序之間必須遵循更加嚴格的順序約束關(guān)系，加大了問題求解的復(fù)雜度，從而成為解決該問題的主要難點。

2 算法設(shè)計

基于上述對緊密銜接綜合調(diào)度問題的描述以及對難點的分析，本文采用基于逆序虛擬零部件的遺傳算法對問題進行求解，研究了算法相關(guān)的實現(xiàn)技術(shù)。在深入分析復(fù)雜產(chǎn)品擴展加工工藝樹結(jié)構(gòu)特點的基礎(chǔ)上，實現(xiàn)了逆序虛擬零部件的剪枝查找，并提出了緊密銜接逆序虛擬零部件、非緊密銜接逆序虛擬零部件、叉點逆序虛擬零部件以及子孫逆序虛擬零部件等相關(guān)概念。在此基礎(chǔ)上，設(shè)計了滿足逆序虛擬零部件順序約束關(guān)系的編碼方法以及交叉和變異算子，此外，又提出了兩種能保證生成滿足緊密銜接逆序虛擬零部件內(nèi)的緊密銜接約束關(guān)系的解碼方法，進而實現(xiàn)對問題的求解。

2.1 基于逆序虛擬零部件雙親孩子表示法的編碼

編碼是解的遺傳基因的表示，實現(xiàn)將求解問題的解表達成遺傳空間的染色體或個體。它會影響遺傳算法后續(xù)的各個階段，是遺傳算法設(shè)計的關(guān)鍵，其設(shè)計必須考慮染色體的合法性、可行性和有效性，以及對問題空間解表達的完全性[21]。不好的編碼方法會產(chǎn)生不可行的問題解，需要增加額外的修補操作，從而降低算法的執(zhí)行效率。在經(jīng)典的作業(yè)車間調(diào)度問題研究中，基于工序的編碼是應(yīng)用最為廣泛的編碼方式，它能保證生成問題的可行解[22]，其根本原因是該調(diào)度問題中各工件是相互獨立的。然而，由于復(fù)雜產(chǎn)品綜合調(diào)度問題中工件間存在約束，造成基于工序的編碼方法無法直接使用，更無法直接應(yīng)用于存在緊密銜接約束的特殊綜合調(diào)度問題中，因此，本文基于文獻[15]中的虛擬零部件剪枝查找方法，提出了針對緊密銜接綜合調(diào)度問題的逆序虛擬零部件剪枝查找方法，以及基于逆序虛擬零部件雙親孩子表示法的編碼方法。

2.1.1 逆序虛擬零部件的剪枝查找方法

將包含非單一緊前工序緊密銜接約束關(guān)系的復(fù)雜產(chǎn)品所對應(yīng)的擴展加工工藝樹用有向圖來表示。由于在樹狀結(jié)構(gòu)的擴展加工工藝樹中存在一個父節(jié)點與多個子節(jié)點的偏序關(guān)系，若采用正序處理的思路，要想保證多個子節(jié)點的結(jié)束時間相同，會使調(diào)度過程變得復(fù)雜，因此，本文采用逆序處理的思路對問題進行分析與求解。圖2所示為上述復(fù)雜產(chǎn)品P的逆序擴展加工工藝樹以及其有向圖，圖中帶陰影的節(jié)點表示存在緊密銜接約束的工序。逆序虛擬零部件剪枝查找方法與文獻[15]中的剪枝查找方法略有不同，它需要結(jié)合復(fù)雜產(chǎn)品緊密銜接約束信息對有向圖進行剪枝，依次查找出各個逆序虛擬零部件，具體實現(xiàn)步驟如下：

步驟1計算逆序擴展加工工藝樹所對應(yīng)的有向圖中各節(jié)點的入度數(shù)。

步驟2從一個入度數(shù)為0的節(jié)點開始(稱為起始節(jié)點)，沿著有向邊查找下一節(jié)點，若起始節(jié)點對應(yīng)的為緊密銜接工序(即帶陰影的節(jié)點)，則采用樹的廣度優(yōu)先遍歷進行查找，直至遇到非緊密銜接工序?qū)?yīng)的節(jié)點(稱為終止節(jié)點)；若起始節(jié)點對應(yīng)的為非緊密銜接工序，則采用樹的深度優(yōu)先遍歷進行查找，直至遇到入度數(shù)大于0或緊密銜接工序?qū)?yīng)的節(jié)點(也稱為終止節(jié)點)，將起始節(jié)點到終止節(jié)點的所有節(jié)點(不含終止節(jié)點)從有向圖中剪枝，它們所對應(yīng)的工序集構(gòu)成一個逆序虛擬零部件。

步驟3重復(fù)步驟2，直至所有的入度數(shù)為0的節(jié)點剪枝完畢。

步驟4將剪枝完畢后剩余的節(jié)點構(gòu)成的子圖作為新的有向圖，并重復(fù)步驟2和步驟3。

步驟5重復(fù)步驟4，直至不能再剪枝為止。

最終，通過上述剪枝方法可得到一系列逆序虛擬零部件。以圖2所示為例，經(jīng)上述操作后的結(jié)果如圖3所示，不難發(fā)現(xiàn)，存在緊密銜接約束關(guān)系的工序共同構(gòu)成一個逆序虛擬零部件，如緊密銜接工序P2、P3、P4以及P7共同構(gòu)成了逆序虛擬零部件RVC2，同時也令它們具備必屬于同一個逆序虛擬零部件的特性。這種特性為后續(xù)編碼和遺傳算子解決逆序虛擬零部件間的順序約束關(guān)系奠定基礎(chǔ)。

2.1.2 基于改進的雙親孩子表示法表示樹狀結(jié)構(gòu)逆序虛擬零部件

從圖3b中可以看出，逆序虛擬零部件之間呈現(xiàn)的關(guān)系并非一一對應(yīng)，而是一多對應(yīng)，對應(yīng)關(guān)系復(fù)雜化之后，則線性結(jié)構(gòu)不便于描述這種復(fù)雜情形，需要用符合樹形結(jié)構(gòu)特點的其他存儲方式來存儲這種非線性結(jié)構(gòu)。按照“存數(shù)值、存聯(lián)系”的原則并結(jié)合后續(xù)所提出算法的特點，本文基于樹的雙親孩子表示法[23]，提出了改進的雙親孩子表示法來存儲經(jīng)過剪枝查找操作后所產(chǎn)生的樹狀結(jié)構(gòu)逆序虛擬零部件信息。

改進的雙親孩子表示法仍采用數(shù)組存儲樹狀結(jié)構(gòu)逆序虛擬零部件中的節(jié)點信息，共有6列，分別為下標、逆序虛擬零部件、對應(yīng)的原工序集、雙親位置、孩子位置和工序數(shù)目。下標即為逆序虛擬零部件的編號，同時每個逆序虛擬零部件節(jié)點的雙親和孩子都是通過這個編號標示出來的。需要注意的是：工序數(shù)目并不總是表示逆序虛擬零部件中包含的原工序的數(shù)量，相關(guān)定義如下。

定義1緊密銜接逆序虛擬零部件。它包含的多道工序間存在著緊密銜接約束關(guān)系。如圖3b中的逆序虛擬零部件RVC2和RVC3。

定義2非緊密銜接逆序虛擬零部件。它包含一道或多道具有線性次序約束的工序且它們之間都不存在緊密銜接約束關(guān)系。如圖3b中的逆序虛擬零部件RVC1、RVC4和RVC5。

定義3叉點逆序虛擬零部件。它是指在逆序虛擬零部件有向圖中直接與多個逆序虛擬零部件節(jié)點存在順序約束關(guān)系的節(jié)點所對應(yīng)的逆序虛擬零部件，即出度大于1的節(jié)點所對應(yīng)的逆序虛擬零部件。如圖3b中的逆序虛擬零部件RVC1和RVC2。

定義4根節(jié)點逆序虛擬零部件。它是指在逆序虛擬零部件有向圖中只有直接后繼的節(jié)點所對應(yīng)的逆序虛擬零部件，即入度等于0的節(jié)點所對應(yīng)的逆序虛擬零部件。如圖3b中的逆序虛擬零部件RVC1。

定義5逆序虛擬零部件RVCi的子孫逆序虛擬零部件。它是指在逆序虛擬零部件有向圖中以逆序虛擬零部件RVCi節(jié)點為根的子樹中的所有節(jié)點所對應(yīng)的逆序虛擬零部件。如圖3b中逆序虛擬零部件RVC4和RVC5都是逆序虛擬零部件RVC2的子孫逆序虛擬零部件。本文規(guī)定逆序虛擬零部件RVCi的子孫逆序虛擬零部件不包含其本身。

定義6逆序虛擬零部件RVCi的工序數(shù)目No。

式中ni是非緊密銜接逆序虛擬零部件RVCi中包含的原工序數(shù)量。

基于上述定義，用改進的雙親孩子表示法表示圖3b中的樹狀結(jié)構(gòu)逆序虛擬零部件具體如表1所示。

表1 逆序虛擬零部件雙親孩子表示法示例

2.1.3 基于逆序虛擬零部件雙親孩子表示法的編碼

目前，采用元啟發(fā)式算法求解綜合調(diào)度問題的研究較少，這是因為相比傳統(tǒng)的車間調(diào)度問題，綜合調(diào)度問題存在更加復(fù)雜的裝配順序約束關(guān)系，導(dǎo)致已有的各種編碼方式失效[15]。本文在樹狀結(jié)構(gòu)逆序虛擬零部件可視為由根節(jié)點不斷延伸結(jié)果的思想指導(dǎo)下，提出一種基于逆序虛擬零部件雙親孩子表示法的編碼方法，它能滿足樹狀結(jié)構(gòu)逆序虛擬零部件順序約束關(guān)系，具體步驟如下：

步驟1基于逆序虛擬零部件雙親孩子表示法，通過雙親位置查找根節(jié)點(即雙親位置為0的逆序虛擬零部件所對應(yīng)的節(jié)點)，將查找到根節(jié)點對應(yīng)的逆序虛擬零部件對應(yīng)的下標構(gòu)成初始可調(diào)度逆序虛擬零部件集S。

步驟2從起始可調(diào)度逆序虛擬零部件集S中隨機地選擇一個下標號作為此時染色體的編碼基因，同時更新對應(yīng)的逆序虛擬零部件工序數(shù)目。更新工序數(shù)目的具體方法為：首先令對應(yīng)的工序數(shù)目值減去1；然后判斷此時其工序數(shù)目值是否變?yōu)?，若為0，則令該逆序虛擬零部件的雙親位置為其自身的下標值，同時對應(yīng)的孩子逆序虛擬零部件的雙親位置值變?yōu)?。

步驟3轉(zhuǎn)步驟1，再對新得到的可調(diào)度逆序零部件集S進行判斷，若為空集，則終止；否則繼續(xù)步驟2操作。

通過上述操作可得到一條完全滿足樹狀結(jié)構(gòu)逆序虛擬零部件順序約束關(guān)系的染色體，圖4為上述圖3b中所示的樹狀結(jié)構(gòu)逆序虛擬零部件有向圖的染色體編碼示意圖。其中非緊密銜接逆序虛擬零部件下標號出現(xiàn)的次數(shù)等于其包含的原工序的數(shù)量，如其中只出現(xiàn)一次的下標1代表著非緊密銜接虛擬零部件RVC1所對應(yīng)的唯一原工序P1；而每個緊密銜接逆序虛擬零部件下標號都只會出現(xiàn)一次，分別代表著對應(yīng)緊密銜接虛擬零部件包含的所有工序，如下標3代表著緊密銜接逆序零部件RVC3所對應(yīng)的原工序集P5和P9。

2.2 選擇操作

常見的選擇操作方法有錦標賽選擇法、最佳個體保存法和輪盤賭選擇法等。本文算法采用錦標賽選擇法，同時輔以精英保留策略。

2.3 交叉操作

常見的交叉操作有單點交叉、多點交叉、均勻交叉和基于工件優(yōu)先順序的交叉等。為保證交叉后所生成的新的子代個體仍滿足樹狀結(jié)構(gòu)逆序虛擬零部件順序約束關(guān)系，本文借鑒基于工件優(yōu)先順序的交叉的思想，提出一種基于叉點逆序虛擬零部件優(yōu)先順序的交叉方法。

設(shè)有兩個父代染色體P1和P2，交叉產(chǎn)生的子代染色體分別為C1和C2，基于叉點逆序虛擬零部件的優(yōu)先順序交叉的具體操作步驟如下：

步驟1隨機選擇一個叉點逆序虛擬零部件并確定其所有子孫逆序虛擬零部件，進而將逆序虛擬零部件集分為兩個非空的子集RVCS1和RVCS2，其中RVCS1包含所有子孫逆序虛擬零部件。特殊地，若不存在叉點虛擬零部件，則隨機選擇一個根節(jié)點逆序虛擬零部件代替叉點逆序虛擬零部件。

步驟2復(fù)制P1包含RVCS2中的逆序虛擬零部件下標基因到C1，P2包含RVCS2中的逆序虛擬零部件下標基因到C2，保留它們的位置。

步驟3復(fù)制P2包含RVCS1中的逆序虛擬零部件下標基因到C1，P1包含RVCS1中的逆序虛擬零部件下標基因到C2，保留它們的順序。

以圖3b所示的樹狀結(jié)構(gòu)逆序虛擬零部件有向圖為例，如圖5所示為上述基于叉點逆序虛擬零部件的POX交叉算子的操作過程，其中選取的叉點逆序虛擬零部件為RVC2。

2.4 變異操作

常見的變異操作有互換變異、逆序變異、插入變異等。為保證變異后所生成的新的子代個體仍滿足樹狀結(jié)構(gòu)逆序虛擬零部件順序約束關(guān)系，本文借鑒插入變異的思想，提出一種新的適應(yīng)于緊密銜接綜合調(diào)度問題的插入變異方法。

設(shè)有父代染色體P，變異產(chǎn)生的子代染色體為C，新的插入變異的具體操作步驟如下：

步驟1隨機選擇一個逆序虛擬零部件作為變異逆序虛擬零部件。

步驟2在變異的父代染色體P中確定變異虛擬零部件所有子孫逆序虛擬零部件下標基因的首位位置first和緊前逆序虛擬零部件基因的最末位位置last。特殊地，若不存在子孫逆序虛擬零部件，則first=length(Chromosome)+1，其中l(wèi)ength(Chromosome)表示染色體的長度；若不存在緊前逆序虛擬零部件，則last=0。

步驟3在區(qū)間[last+1,first-1]隨機確定所有變異虛擬零部件下標基因的位置，其他虛擬零部件下標基因順序保持不變，同時判斷能否得到一條新的不同于父代染色體P的染色體。

步驟4若能夠得到一條新的不同于父代染色體P的染色體，則新得到的染色體即為變異產(chǎn)生的子代染色體C，否則，重復(fù)步驟1～步驟3，直至得到一條不同于父代染色體P的染色體C。

以圖3b中所示的樹狀結(jié)構(gòu)逆序虛擬零部件有向圖為例，如圖6所示為上述插入變異算子的操作過程。圖中所示隨機選取的變異逆序虛擬零部件為RVCS3，在區(qū)間[2,5]隨機確定的變異逆序虛擬零部件基因位置為2。

2.5 考慮緊密銜接約束關(guān)系的解碼

為了獲得原緊密銜接綜合調(diào)度問題的調(diào)度方案，同時結(jié)合本文編碼的特點，本文分別從間接和直接兩個角度設(shè)計了兩種不同的基于插入式貪婪解碼[24]的解碼方法。它們的主體思路都是通過按照特定的染色體基因順序進行解碼來滿足對應(yīng)問題中工序間的先后順序約束關(guān)系，同時又對緊密銜接逆序虛擬零部件對應(yīng)的染色體基因進行特殊解碼來滿足對應(yīng)問題中工序間的緊密銜接約束關(guān)系，進而保證它們所生成的調(diào)度方案的可行性。

2.5.1 基于主動逆序調(diào)度方案轉(zhuǎn)化的解碼

基于主動逆序調(diào)度方案轉(zhuǎn)化的解碼方法主要分為兩步：首先，采用一種基于插入式貪婪解碼的主動逆序調(diào)度解碼方法，得到原問題的逆序緊密銜接綜合調(diào)度問題的主動逆序調(diào)度方案；然后，通過一種轉(zhuǎn)化方法，實現(xiàn)將主動逆序調(diào)度方案轉(zhuǎn)化成原問題所對應(yīng)的調(diào)度方案。該解碼方法雖然無法保證生成原問題的主動調(diào)度方案，但是能保證生成不大于主動逆序調(diào)度方案最大完工時間的調(diào)度方案。

本文設(shè)計的基于插入式貪婪解碼的主動逆序調(diào)度解碼方法的具體步驟如下：

步驟1設(shè)定復(fù)雜產(chǎn)品各道工序的初始化預(yù)定最早開工時間值，若無特殊說明，則均為0。

步驟2按照從左到右的順序，依次讀取染色體上的逆序虛擬零部件RVCi的下標號。

步驟3判斷RVCi是否為緊密銜接逆序虛擬零部件，若不是，則轉(zhuǎn)步驟4，否則，轉(zhuǎn)步驟5。

步驟4若RVCi為非緊密銜接逆序虛擬零部件，計算相應(yīng)工序的實際開工時間和實際完工時間，同時更新相關(guān)信息。

設(shè)對應(yīng)的工序為oi，oi的預(yù)定最早開工時間為si，oi的加工設(shè)備為Mk，加工時間為tik，實際開工時間為Si，實際完工時間為Ci。相關(guān)計算步驟如下：

(1)從前向后依次計算并檢查設(shè)備Mk上的空閑時間區(qū)域[ts,tc](在后續(xù)中如無特殊說明，默認為[ts,+)屬于[ts,tc]的特殊情況)，如果max(si,ts)+tik≤tc，則令Si=max(si,ts)。

(2)計算工序oi實際完工時間Ci=Si+tik。

(3)更新設(shè)備Mk的空閑區(qū)域，同時，用Ci與oi緊后工序or的預(yù)定最早開工時間進行比較，選擇較大的作為工序or新的預(yù)定最早開工時間。

步驟5若RVCi為緊密銜接逆序虛擬零部件，計算相應(yīng)一系列工序的實際開工時間和實際完工時間，同時更新相關(guān)信息。

設(shè)對應(yīng)的一系列工序為oi1,…,oii′，且它們的先后順序滿足它們之間的順序約束關(guān)系，對應(yīng)的加工設(shè)備為Mk1,…,Mki′，對應(yīng)的預(yù)定最早開工時間為si1,…,sii′，對應(yīng)的加工時間為ti1,…,tii′，對應(yīng)的實際開工時間為Si1,…,Sii′，對應(yīng)的實際完工時間為Ci1,…,Cii′。相關(guān)計算步驟如下：

(1)確定在不考慮加工設(shè)備狀況的情況下該系列工序oi1,…,oii′可行的預(yù)定最早開工時間ssi1,…,ssii′和預(yù)定最早完工時間cci1,…,ccii′。具體操作如下：

1)由于工序oi1,…,oii′在逆序擴展加工工藝樹中所對應(yīng)的部分仍為樹狀結(jié)構(gòu)，因此，可視為一個獨立的加工工藝樹，且根節(jié)點對應(yīng)的工序為oi1。分別將工序oi1,…,oii′視為葉節(jié)點，計算它們在相應(yīng)的加工工藝樹中的路徑長度[25]，且分別記為pi1,…,pii′。

2)通過公式f(j)=max(si1+pip,sij)+tij，其中pip表示工序oij的緊前工序oip路徑長度，得到f(1),…,f(i′)，實際上f(j)表示在滿足工序oij預(yù)定最早開工時間的條件下工序oij的完工時間。

3)令ccij′=max(f(j))，ssij′=ccij′-tij′，同時結(jié)合工序oi1,…,oii′之間的緊密銜接約束關(guān)系的特點，依次計算出其他剩余工序可行的預(yù)定最早開工時間和預(yù)定最早完工時間。

1)按照由前向后的順序，依次計算并檢查設(shè)備Mk1上的空閑時間區(qū)域[ts,tc]，如果max(ssi1,ts)+ti1≤tc，則表示在不考慮其他工序的情況下工序oi1可安排在該空閑時間區(qū)域加工；否則，檢查下一個區(qū)域，直至尋找到一個可安排工序oi1加工的空閑時間區(qū)域。

3)在當(dāng)前尋找到可安排工序oi1加工的空閑時間區(qū)域的條件下，在工序oi2,…,oii′的加工設(shè)備Mk2,…,Mki′上從前向后依次計算并檢查相應(yīng)設(shè)備上的空閑時間區(qū)域，判斷相應(yīng)的工序是否可安排在該空閑時間區(qū)域。假設(shè)空閑時間區(qū)域為[tsj,tcj]，工序oij可安排在空閑時間區(qū)域[tsj,tcj]需滿足的條件為：max(ssij,tsj)+tij≤tcj&tsj≤lsij&tcj≥ecij。

(3)確定工序oi1,…,oii′的實際開工時間為Si1,…,Sii′和實際完工時間為Ci1,…,Cii′，同時更新相關(guān)設(shè)備和工序的預(yù)定最早開工時間。具體操作如下：

2)通過公式Sij=esij+d,Cij=ecij+d，確定工序oi1,…,oii′的實際開工時間Si1,…,Sii′和實際完工時間Ci1,…,Cii′。

3)更新相應(yīng)設(shè)備Mk1,…,Mki′的空閑區(qū)域，同時，依次通過Ci1,…,Cii′與其對應(yīng)緊后工序的預(yù)定最早開工時間的比較來更新它們預(yù)定最早開工時間。

步驟6判斷是否讀取完畢，若讀取完畢，則結(jié)束，否則轉(zhuǎn)步驟2。

通過上述主動逆序調(diào)度解碼方法能將一條基于逆序虛擬零部件雙親孩子表示法編碼的染色體解碼成一個原問題所對應(yīng)的逆序緊密銜接綜合調(diào)度問題的主動逆序調(diào)度方案。為得到原緊密銜接綜合調(diào)度問題的調(diào)度方案，本文在上述主動逆序解碼結(jié)果的基礎(chǔ)上，又提出一種相應(yīng)的轉(zhuǎn)化方法。為便于描述，本文將主動逆序調(diào)度方案進行逆序調(diào)整[14]后所對應(yīng)的調(diào)度方案稱為“反轉(zhuǎn)調(diào)度方案”。轉(zhuǎn)化方法的具體步驟如下：

步驟1計算存在緊密銜接約束關(guān)系的工序在正序調(diào)度方案中的實際開工時間和實際完工時間。通過公式PSij=RMakespan-Cij,PCij=PSij+tij,?oij∈OSi，其中：PSij和PCij是指工序oij在正序調(diào)度方案中的實際開工時間和實際完工時間；RMakespan是指主動逆序調(diào)度方案的最大完工時間；OSi是指所有存在緊密銜接約束關(guān)系的工序集，計算出它們在正序調(diào)度方案中的實際開工時間和實際完工時間。

步驟2分別更新相關(guān)加工設(shè)備的空閑區(qū)域和工序的預(yù)定最早開工時間。相關(guān)計算步驟如下：

(1)根據(jù)步驟1得到的工序?qū)嶋H開工時間和實際完工時間，更新它們相應(yīng)加工設(shè)備的空閑區(qū)域。

(2)根據(jù)步驟1得到的工序?qū)嶋H完工時間，更新在原問題的擴展加工工藝樹中它們各自緊后工序的預(yù)定最早開工時間。具體為：用工序的實際完工時間與它的唯一緊后工序的預(yù)定最早開工時間進行比較，選擇較大的值作為它的緊后工序新的預(yù)定最早開工時間。

步驟3對不存在緊密銜接約束關(guān)系的工序執(zhí)行貪婪解碼操作，確定它們在正序調(diào)度方案中的實際開工時間和實際完工時間。相關(guān)計算步驟如下：

(1)設(shè)定不存在緊密銜接約束關(guān)系的工序的初始化預(yù)定最早開工時間值，若無特殊說明，則均為0。

(2)正向標準化主動逆序調(diào)度解碼獲得的工序染色體。采用文獻[26]中的正向標準化方法，按照工序的完工時間進行正向標準化。

(3)按照從右到左的順序，依次讀取正向標準化后的工序染色體上的基因genei，設(shè)對應(yīng)的工序為oi，同時判斷oi是否為緊密銜接工序，若是，則跳過，否則，轉(zhuǎn)步驟(4)。

(4)若oi是非緊密銜接工序，計算該工序的實際開工時間和實際完工時間，同時更新相關(guān)信息。

設(shè)oi的預(yù)定最早開工時間為si，oi的加工設(shè)備為Mk，加工時間為tik，實際開工時間為Si，實際完工時間為Ci。具體操作如下：

1)按照由前向后的順序，依次計算并檢查設(shè)備Mk上的空閑時間區(qū)域[ts,tc]，如果max(si,ts)+tik≤tc，則令Si=max(si,ts)；否則，檢查下一個區(qū)域，直至尋找到一個可安排工序oi1加工的空閑時間區(qū)域。

2)計算工序oi實際完工時間Ci=Si+tik。

3)更新設(shè)備Mk的空閑區(qū)域，同時，用Ci與oi正序緊后工序op的預(yù)定最早開工時間進行比較，選擇較大的作為工序op新的預(yù)定開工時間。

(5)判斷讀取是否完畢，若讀取完畢，則結(jié)束，否則轉(zhuǎn)步驟(3)。

需要說明的是：通過上述轉(zhuǎn)化方法雖然無法保證生成原問題的主動調(diào)度解，但是所得到的調(diào)度方案的最大完工時間值不大于轉(zhuǎn)化前主動逆序調(diào)度方案的最大完工時間值，甚至有可能進一步減少。原因在于：①“反轉(zhuǎn)調(diào)度方案”與主動逆序調(diào)度方案在每臺加工設(shè)備上的工序加工順序相反，并且擁有相同的關(guān)鍵路徑和完工時間；②一方面該轉(zhuǎn)化方法在保持存在緊密銜接約束關(guān)系的工序在正序調(diào)度方案中與“反轉(zhuǎn)調(diào)度方案”位置相同的同時，另一方面又通過貪婪解碼算法左移“反轉(zhuǎn)調(diào)度方案”中不存在緊密銜接約束關(guān)系的工序。因此，轉(zhuǎn)化后生成的調(diào)度方案能保證調(diào)度方案的最大完工時間值不增加，并有進一步減少的可能。

2.5.2 基于插入式貪婪解碼的主動解碼

按照文獻[14]提出的方法對獲得的逆序調(diào)度方案進行逆序調(diào)整便可得到原問題的調(diào)度方案(即“反轉(zhuǎn)調(diào)度方案”)，然而從反轉(zhuǎn)調(diào)度方案的甘特圖中不難發(fā)現(xiàn)，除關(guān)鍵路徑上的工序外，其他工序的開工時間并非都是其能開工的最早時間。因此，為避免本文算法的最終調(diào)度結(jié)果也出現(xiàn)上述問題，本文又提出一種能保證生成原緊密銜接綜合調(diào)度問題的主動調(diào)度的解碼方法。該主動解碼操作與上述基于插入式貪婪解碼的主動逆序調(diào)度解碼方法大體相同，主要不同之處在于步驟2和步驟5的(1)，它們在原緊密銜接綜合調(diào)度問題的主動解碼方法中的具體操作如下：

步驟2：按照從右到左的順序，依次讀取染色體上的正序虛擬零部件PVCi的下標號(稱正序虛擬零部件僅為了與上述逆序虛擬零部件區(qū)分開)。

步驟5的(1)：確定在不考慮加工設(shè)備狀況的情況下緊密銜接正序虛擬零部件PVCi對應(yīng)的一系列工序oi1,…,oii′可行的預(yù)定最早開工時間ssi1,…,ssii′和預(yù)定最早完工時間cci1,…,ccii′。此外，需要說明的是：工序oi1,…,oii′順序是滿足它們在原問題中的緊密銜接約束關(guān)系的。具體操作如下：

1)由于工序oi1,…,oii′在原問題的擴展加工工藝樹中所對應(yīng)的部分仍為樹狀結(jié)構(gòu)，仍可視為一個獨立的加工工藝樹，且根節(jié)點對應(yīng)的工序為oii′。分別將工序oi1,…,oii′視為葉節(jié)點，計算它們在相應(yīng)的加工工藝樹中的路徑長度，且分別記為pi1,…,pii′。

2)通過公式dpij=max(pij′)-pij,spij=pij+sij,msp=max(spij),ssij=msp-pij,ccij=ssij+tij，?j∈{1,2,…,i′},?j′∈{1,2,…,i′}，依次計算出工序oi1,…,oii′可行的預(yù)定最早開工時間和最早完工時間。

3 實例測試

眾所周知，針對傳統(tǒng)的作業(yè)車間調(diào)度問題算法的研究可直接采用已有的國際通用基準實例進行測試，然而目前復(fù)雜產(chǎn)品綜合調(diào)度問題尚未建立起基準測試實例，更不用說緊密銜接綜合調(diào)度問題基準測試實例。為驗證本文所提算法的性能，選用目前發(fā)現(xiàn)的相關(guān)文獻中的測試實例進行測試。由于本文在基于逆序虛擬零部件雙親孩子表示法的編碼方法的基礎(chǔ)上，提出了基于主動逆序調(diào)度方案轉(zhuǎn)化的解碼方法和基于插入式貪婪解碼的主動解碼方法。雖然這兩種解碼方法都能求解出原緊密銜接綜合調(diào)度解的解碼方法，但是為了更好地發(fā)揮它們各自的優(yōu)勢，并提高它們對應(yīng)算法的性能，在下面的實例測試中，本文針對它們分別采用不同的策略進行處理。由于基于主動逆序調(diào)度方案轉(zhuǎn)化的解碼方法實際上在每個解碼過程中使用了兩次貪婪解碼方法，這無疑增加了計算時間，結(jié)合該方法具有不增加調(diào)度優(yōu)化目標的優(yōu)點，本文在測試過程中只針對經(jīng)過不斷迭代最終獲得最優(yōu)主動逆序調(diào)度方案進行轉(zhuǎn)化操作，以求在更加短的時間內(nèi)獲得原問題滿意的解。而基于插入式貪婪解碼的主動解碼方法不存在上述基于主動逆序調(diào)度方案轉(zhuǎn)化的解碼方法需要兩次解碼的問題，因此本文在下面測試過程中對于種群中的每個個體都使用該主動解碼方法直接生成原問題的主動調(diào)度。

本文兩種算法是在Win7系統(tǒng)下采用MATLAB語言編程實現(xiàn)，運行的計算機中央處理器的主頻為3.40 GHz，內(nèi)存為8.00 GB，對下述每個實例都各自獨立運行求解10次。算法的相關(guān)參數(shù)設(shè)置相同，具體如下：種群規(guī)模大小為100，最大迭代次數(shù)為50，交叉概率為0.9，變異概率為0.1。

3.1 實例1

本實例來源于文獻[14]，它實際上是一個嚴格意義上的存在非單一緊前工序緊密銜接約束關(guān)系的緊密銜接綜合調(diào)度問題。圖2所示即為其逆序擴展加工工藝樹，通過剪枝查找操作后建立的逆序虛擬零部件雙親孩子表示法如表1所示。分別采用本文兩種算法對該實例進行求解。基于主動逆序調(diào)度方案轉(zhuǎn)化的遺傳算法在求解的10次過程中，平均完工時間為19且最優(yōu)解也為19，平均用時為2.359 s，其中一個調(diào)度結(jié)果如圖7所示。基于插入式貪婪解碼的遺傳算法在求解的10次過程中，平均完工時間也為19且最優(yōu)解也為19，平均用時為2.48 s，其中一個調(diào)度結(jié)果如圖8所示。文獻[14]提出的基于逆序信號驅(qū)動的緊密銜接綜合調(diào)度算法求得的結(jié)果為19，相應(yīng)的調(diào)度結(jié)果如圖9所示。顯然，本文兩種算法都能得到與基于逆序信號驅(qū)動的緊密銜接綜合調(diào)度算法相同的結(jié)果，且平均用時不超過3 s，因此，本實例測試結(jié)果表明本文算法的有效性。

3.2 實例2

本實例來源于文獻[20]，它實際上是一個嚴格意義上存在單一緊前工序緊密銜接約束關(guān)系的多復(fù)雜產(chǎn)品緊密銜接綜合調(diào)度問題。通過剪枝查找操作后建立的逆序虛擬零部件雙親孩子表示法如表2所示。分別采用本文兩種算法對該實例進行求解?；谥鲃幽嫘蛘{(diào)度方案轉(zhuǎn)化的遺傳算法在求解的10次過程中，平均完工時間為41，且最優(yōu)解也為41，平均用時為3.924 s，其中一個調(diào)度結(jié)果如圖10所示?；诓迦胧截澙方獯a的遺傳算法在求解的10次過程中，平均完工時間也為41，且最優(yōu)解也為41，平均用時為4.247 s，其中一個調(diào)度結(jié)果如圖11所示。將本文兩種算法的求解結(jié)果與其他文獻算法的求得結(jié)果進行比較，文獻[6]中算法的求解結(jié)果為44，相應(yīng)的調(diào)度結(jié)果如圖12所示，文獻[20]中算法的求解結(jié)果為46，相應(yīng)的調(diào)度結(jié)果如圖13所示。顯然，本文兩種算法的求解結(jié)果都優(yōu)于上述文獻中算法的求解結(jié)果，且平均用時不超過5 s，因此，本實例測試結(jié)果表明本文算法的有效性和優(yōu)越性。

表2 逆序虛擬零部件雙親孩子表示法示例

3.3 實例3

本實例來源于文獻[13]，它實際上是一個嚴格意義上存在單一緊前工序緊密銜接約束關(guān)系的多層緊密銜接綜合調(diào)度問題。通過剪枝查找操作后建立的逆序虛擬零部件雙親孩子表示法如表3所示。分別采用本文兩種算法對該實例進行求解?；谥鲃幽嫘蛘{(diào)度方案轉(zhuǎn)化的解碼方法的遺傳算法在求解的10次過程中，平均完工時間為26，且最優(yōu)解也為26，平均用時為5.683 s，其中一個調(diào)度結(jié)果如圖14所示?；诓迦胧截澙方獯a的遺傳算法在求解的10次過程中，平均完工時間為27且最優(yōu)解也為27，平均用時為6.191 s，其中一個調(diào)度結(jié)果如圖15所示。將本文兩種算法的求解結(jié)果與文獻[13]中算法的求得結(jié)果進行比較，而文獻[13]中算法的求解結(jié)果為28，相應(yīng)的調(diào)度結(jié)果如圖16所示。顯然，本文兩種算法的求解結(jié)果都優(yōu)于上述文獻中算法的求解結(jié)果，且平均用時不超過7 s，因此，本實例測試結(jié)果表明本文算法的有效性和優(yōu)越性。

表3 逆序虛擬零部件雙親孩子表示法示例

3.4 實例4

本實例來源于文獻[14]，它是比實例3更加復(fù)雜的存在單一緊前工序緊密銜接約束關(guān)系的多層緊密銜接綜合調(diào)度問題。通過剪枝查找操作后建立的逆序虛擬零部件雙親孩子表示法如表4所示。針對本實例，分別采用本文兩種不同解碼方法的遺傳算法對該實例進行求解，基于主動逆序調(diào)度方案轉(zhuǎn)化的遺傳算法在求解的10次過程中，平均完工時間為28，且最優(yōu)解也為28，平均用時為5.683 s，其中一個調(diào)度結(jié)果如圖17所示?；诓迦胧截澙方獯a的遺傳算法在求解的10次過程中，求解平均完工時間為28，且獲得最優(yōu)解也為28，并且每次的平均用時為6.848 s，其中一個調(diào)度結(jié)果如圖18所示。將本文算法的求解結(jié)果與其他文獻算法的求得結(jié)果進行比較，文獻[13]中算法的求解結(jié)果為31，相應(yīng)的調(diào)度結(jié)果如圖19所示。文獻[14]中算法的求解結(jié)果為29，相應(yīng)的調(diào)度結(jié)果如圖20所示，同時不難看出工序A2、A18、A19和A12等都不是它們能開工的最早時間，即該調(diào)度方案為非主動調(diào)度。顯然，本文算法的求解結(jié)果優(yōu)于上述文獻中算法的求解結(jié)果，且每次的平均用時不超過7 s，此外，本文所提出的基于插入式貪婪解碼的遺傳算法能保證生成主動調(diào)度。綜上所述，本實例測試結(jié)果也表明本文算法的有效性和優(yōu)越性。

表4 逆序虛擬零部件雙親孩子表示法示例

4 結(jié)束語

本文將單一緊前工序的緊密銜接綜合調(diào)度問題和非單一緊前工序的緊密銜接綜合調(diào)度問題統(tǒng)一進行處理，結(jié)合問題之間的共性，從逆序調(diào)度的角度提出了基于逆序虛擬零部件的遺傳算法，提高了算法的通用性。相關(guān)結(jié)論如下：

(1)通過對復(fù)雜產(chǎn)品逆序擴展加工工藝樹的有向圖進行剪枝查找操作，達到了降低層次、簡化約束的目的，同時建立了逆序虛擬零部件雙親孩子表示法，并提出了相應(yīng)的編碼方法，為后續(xù)問題的解決奠定了堅實的基礎(chǔ)。

(2)針對基于逆序虛擬零部件雙親孩子表示法，設(shè)計出了相應(yīng)的能滿足復(fù)雜產(chǎn)品逆序虛擬零部件順序約束的遺傳算子，并提出了兩種各具特色的解碼方法，保證了生成原問題的可行解，提高了算法的求解速度和質(zhì)量。

(3)通過對已有文獻中相關(guān)實例的測試，驗證了本文算法求解緊密銜接綜合調(diào)度問題的有效性和優(yōu)越性。

本文所提出的遺傳算法為解決緊密銜接綜合調(diào)度問題提供一種新的解決方法，且具有較高的通用性和有效性，同時也對進一步深入研究緊密銜接綜合調(diào)度問題有一定的理論和實際意義。此外，也為遺傳算法求解其他特殊綜合調(diào)度問題提供了一定的借鑒價值，如存在多工序同時結(jié)束的綜合調(diào)度問題、存在多設(shè)備工序的綜合調(diào)度問題等。