宋李俊，魯若愚，李孝斌，龔小容,*

（1.重慶理工大學(xué) 機(jī)械工程學(xué)院，重慶 400054；2.重慶大學(xué) 機(jī)械與運(yùn)載工程學(xué)院，重慶 400044）

0 引言

經(jīng)濟(jì)全球化的大背景下，制造自動(dòng)化、柔性化、智能化和高度集成化推動(dòng)全球產(chǎn)業(yè)競(jìng)爭(zhēng)格局發(fā)生著重大調(diào)整，制造企業(yè)間的競(jìng)爭(zhēng)愈趨激烈。在過(guò)去，按訂單生產(chǎn)型（Make To Order,MTO）企業(yè)在訂單接受和訂單生產(chǎn)上分別由銷售部門和生產(chǎn)部決策，銷售部門往往只關(guān)心訂單接受的數(shù)量而不考慮訂單的生產(chǎn)，而生產(chǎn)部門更多考慮生產(chǎn)訂單交期的滿足，對(duì)訂單總體效益較少關(guān)注。這樣的分開決策往往會(huì)導(dǎo)致接受的訂單大大超過(guò)生產(chǎn)能力而產(chǎn)生訂單的延遲懲罰成本，從而導(dǎo)致企業(yè)效益受損和名譽(yù)受損，更嚴(yán)重的會(huì)導(dǎo)致客戶的流失。為了企業(yè)效益提升，MTO企業(yè)開始對(duì)訂單接受與調(diào)度（Order Acceptance and Scheduling,OAS）問(wèn)題進(jìn)行集成決策，在訂單接受同時(shí)根據(jù)訂單特點(diǎn)和要求進(jìn)行優(yōu)化調(diào)度排產(chǎn)，在滿足訂單交期的前提下盡可能接受更多訂單。

目前，已有一些學(xué)者對(duì)OAS問(wèn)題進(jìn)行了一定的研究。Slotnick和Morton是OAS問(wèn)題較早的研究者，他們將企業(yè)生產(chǎn)環(huán)境抽象為一臺(tái)機(jī)器，加工不允許搶占和中斷，客戶接受一定的交貨期延遲，延期懲罰是與延期天數(shù)線性相關(guān)的遞增函數(shù)，對(duì)比結(jié)果表明在產(chǎn)能有限的約束下，訂單接受和調(diào)度聯(lián)合決策比分開決策利潤(rùn)率更高，證實(shí)了OAS問(wèn)題的研究意義與實(shí)用價(jià)值[1]。Oguz等進(jìn)一步擴(kuò)展了Slotnick和Morton研究的優(yōu)化決策模型，考慮訂單發(fā)布時(shí)間和序列生產(chǎn)準(zhǔn)備時(shí)間帶來(lái)的復(fù)雜性，提出了一種混合整數(shù)線性規(guī)劃模型[2]。Back等進(jìn)一步考慮了有限產(chǎn)能約束，并假設(shè)準(zhǔn)備時(shí)間對(duì)釋放時(shí)間存在部分依賴關(guān)系，提出了一個(gè)新的混合整數(shù)線性規(guī)劃模型[3]。王柏琳等針對(duì)多品種混合制造商的不相關(guān)并行機(jī)訂單拒絕問(wèn)題，以總成本最小為目標(biāo)，基于列表拒絕方法和訂單拒絕準(zhǔn)則設(shè)計(jì)了采用單親-傳統(tǒng)雙遺傳算子的協(xié)同進(jìn)化遺傳算法[4]。Wang等人研究了一種不相關(guān)并行機(jī)OAS決策問(wèn)題，以總收益與總加權(quán)延誤的差額為目標(biāo)函數(shù)，建立了兩個(gè)混合整數(shù)規(guī)劃模型，并提出了一種分枝定界算法[5]。Naderi等針對(duì)訂單選擇和相同并行機(jī)調(diào)度問(wèn)題，建立了預(yù)處理技術(shù)、有效不等式和優(yōu)勢(shì)規(guī)則等增強(qiáng)策略改進(jìn)一個(gè)混合整數(shù)規(guī)劃數(shù)學(xué)模型，并利用分支松弛和檢查（BRC）方法將模型進(jìn)行了分解[6]。宋李俊等人針對(duì)JIT模式下多節(jié)點(diǎn)流水線具有訂單交貨延遲懲罰與產(chǎn)品庫(kù)存平衡約束的OAS決策問(wèn)題，建立了總利潤(rùn)最大化決策模型，并設(shè)計(jì)了改進(jìn)型雙層編碼遺傳算法進(jìn)行求解[7]。

從現(xiàn)有的相關(guān)文獻(xiàn)來(lái)看，對(duì)OAS問(wèn)題的研究主要集中在單機(jī)（單節(jié)點(diǎn)）環(huán)境[8～10]或并行機(jī)環(huán)境[11,12]，對(duì)于更復(fù)雜的多階段加工環(huán)境的研究較少。本文以兩階段裝配流水線為研究對(duì)象，基于有限產(chǎn)能考慮訂單序列相關(guān)準(zhǔn)備時(shí)間約束，建立以訂單利潤(rùn)最大為目標(biāo)的訂單接受與調(diào)度模型，并設(shè)計(jì)一種變鄰域半置換遺傳算法（Semi-permutation-based Genetic Algorithm-Variable Neighborhood Search，SPGA-VNS）進(jìn)行求解。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

本文提及的兩階段裝配流水線生產(chǎn)流程可以描述為：產(chǎn)品生產(chǎn)分為配套零件加工、裝配兩個(gè)階段，第一個(gè)階段有M個(gè)并行的流水加工單元，不同的加工單元完成不同的零部件加工，本文將M個(gè)加工單元簡(jiǎn)化為M臺(tái)特定的異速并行加工機(jī)器；第二個(gè)階段有1個(gè)裝配單元，當(dāng)各配套零件加工完成后，裝配單元支持將零件裝配成完整產(chǎn)品，其生產(chǎn)流程模型如圖1所示。

圖1 兩階段裝配流水線生產(chǎn)流程模型

兩階段裝配流水線OAS問(wèn)題可以描述為：企業(yè)初始時(shí)刻收到n個(gè)生產(chǎn)訂單可供選擇，在滿足兩階段裝配流程生產(chǎn)模式情況下，確定接受哪些訂單以及制定被接受訂單的調(diào)度方案，以實(shí)現(xiàn)訂單收益最大化。其中，訂單采用柔性交貨期形式進(jìn)行交付，即若訂單在約定交貨期之后、最遲交貨期之前完成生產(chǎn)，則視為延期交付，將產(chǎn)生延期懲罰；若在約定交貨期前完成生產(chǎn)，則視為按期交貨，無(wú)懲罰；若在最遲交貨期之后完成生產(chǎn)，則視為延期懲罰大于訂單收益，訂單將被拒絕。該問(wèn)題模型需要滿足以下假設(shè)：

1）所有參數(shù)均為已知和確定的。

2）所有訂單都在初始時(shí)刻（設(shè)為t=1時(shí)刻）可在任何機(jī)器上進(jìn)行加工。

3）機(jī)器加工或裝配過(guò)程為非搶占式。

4）每個(gè)訂單的工藝路線為確定的。

5）每個(gè)訂單之間均不存在先后約束。

6）機(jī)器持續(xù)可用。

7）加工存在訂單序列相關(guān)的加工準(zhǔn)備時(shí)間。

8）任何一個(gè)訂單完成第一階段所零件加工后才可開始裝配。

9）兩個(gè)生產(chǎn)階段間存在足夠大的緩沖區(qū)域。

為了方便建模，本文符號(hào)定義如表1所示。

表1 符號(hào)定義

1.2 模型建立

根據(jù)以上描述建立采用時(shí)間索引(Time-indexed formulation,TIF)方法的混合整數(shù)線性規(guī)劃模型。目標(biāo)為訂單利潤(rùn)最大化。數(shù)學(xué)模型如下：

式(1)表示目標(biāo)函數(shù)為訂單收益與延期懲罰之差；式(2)表示每個(gè)訂單只在某個(gè)確定時(shí)刻在第一階段的機(jī)器上開始加工；式(3)表示訂單j在第一階段加工機(jī)器i上的加工完成時(shí)刻；式(4)表示訂單j在第一階段的加工完成時(shí)刻大于或等于其在任意機(jī)器i上的加工完成時(shí)刻；式(5)表示任何一個(gè)時(shí)刻機(jī)器i上最多只有一個(gè)訂單在加工；式(6)表示每個(gè)訂單只在第二階段的某個(gè)確定時(shí)刻在裝配機(jī)器上開始裝配；式(7)表示訂單j在第二階段的裝配完工時(shí)刻；式(8)表示訂單j必須在完成其第一階段所有加工后才能開始裝配；式(9)表示訂單j在第一階段的加工完成時(shí)刻必須小于或等于其裝配開始時(shí)刻；式(10)表示任何一個(gè)時(shí)刻裝配機(jī)器上最多只有一個(gè)訂單在裝配；式(11)表示訂單j的裝配完工時(shí)刻必須小于或等于訂單j的最遲交貨期；式(12)表示訂單j必須在其第一階段加工時(shí)間范圍內(nèi)開始加工；式(13)表示訂單j必須在其第二階段加工時(shí)間范圍內(nèi)開始裝配；式(14)表示訂單j的裝配開始時(shí)刻大于其在第一階段機(jī)器上的最大加工時(shí)間；式(15)表示決策變量的取值范圍。

2 算法設(shè)計(jì)

同粒子群、蟻群、模擬退火等算法相比，遺傳算法具有操作簡(jiǎn)單、迭代時(shí)間短、全局尋優(yōu)能力強(qiáng)、魯棒性好等特點(diǎn)，更適用于求解復(fù)雜生產(chǎn)環(huán)境下的OAS問(wèn)題。但遺傳算法存在搜索效率較低和容易過(guò)早收斂等不足，因此對(duì)遺傳算法進(jìn)行一定程度的改進(jìn)或與其他算法混合，是增強(qiáng)其局部搜索能力、加快收斂速度以及提高解質(zhì)量的有效手段。本文針對(duì)兩階段裝配流水線訂單接受與調(diào)度問(wèn)題求解，提出一種變鄰域半置換改進(jìn)遺傳算法，利用整數(shù)矩陣編碼和啟發(fā)式規(guī)則提升初始種群的質(zhì)量，設(shè)計(jì)隨機(jī)半置換單點(diǎn)交叉、互換變異等改進(jìn)遺傳策略提高解的質(zhì)量，并提出原基因重插入法確保新種群個(gè)體均為可行解，結(jié)合變鄰域搜索提高算法的局部搜索能力。

2.1 染色體編碼

考慮到加工裝配流水線由m臺(tái)異速并行機(jī)器和1臺(tái)裝配機(jī)器組成，本文采用基于訂單順序的整數(shù)矩陣對(duì)染色體進(jìn)行編碼。一個(gè)完整的個(gè)體為一個(gè)m+1行、n列的整數(shù)編碼矩陣，編碼矩陣中每一行代表一條染色體，如圖2所示。編碼矩陣的前m行表示第一階段的加工機(jī)器i上的訂單加工順序，數(shù)字表示對(duì)應(yīng)的訂單序號(hào)；編碼矩陣的第m+1行表示第二階段的裝配機(jī)器上訂單的裝配順序。

圖2 整數(shù)矩陣編碼

2.2 種群初始化

初始種群由三個(gè)種類，共N個(gè)種群個(gè)體組成。

1）第一類種群個(gè)體采用隨機(jī)策略，共生成0.6N個(gè)。首先，隨機(jī)排序生成第一階段加工機(jī)器1的訂單加工順序，然后采用隨機(jī)相鄰半置換策略生成其他機(jī)器訂單加工順序，即在保持最先開始加工的訂單序號(hào)不變的情況下，其余n-1個(gè)訂單的加工順序均采用兩個(gè)隨機(jī)選擇的相鄰訂單的成對(duì)交換2n次生成，最后第二階段裝配機(jī)器上的訂單裝配順序采用FIFO規(guī)則生成。

2）第二類種群個(gè)體采用單位加工時(shí)間收益越大優(yōu)先策略，共生成0.2N個(gè)。首先基于訂單Rj/Pj的非升序排列生成第一階段加工機(jī)器1上的訂單加工順序，然后采用隨機(jī)相鄰半置換策略生成剩余機(jī)器上的訂單加工順序，最后第二階段裝配機(jī)器上的訂單裝配順序采用FIFO規(guī)則生成。

3）第三類種群個(gè)體采用單位加工時(shí)間延期懲罰越低優(yōu)先策略，共生成0.2N個(gè)。首先基于訂單Wj/Pj的非降序排列生成第一階段加工機(jī)器1上的訂單加工順序，然后采用隨機(jī)相鄰半置換策略生成剩余機(jī)器上的訂單加工順序，最后第二階段裝配機(jī)器上的訂單裝配順序采用FIFO規(guī)則生成。

2.3 適應(yīng)度函數(shù)

種群中個(gè)體的適應(yīng)度值代表其對(duì)環(huán)境的適應(yīng)程度，同時(shí)也反映了現(xiàn)有種群每一個(gè)體的質(zhì)量好壞，本文將模型的目標(biāo)函數(shù)作為算法的適應(yīng)度函數(shù)：

2.4 選擇操作

采用錦標(biāo)賽法作為選擇操作策略，并利用精英保留策略保證種群中的最優(yōu)個(gè)體一定被選中。帶精英保留策略的錦標(biāo)賽法步驟為：

步驟1：確定每次從父代種群中隨機(jī)抽取個(gè)體的數(shù)量，本文設(shè)定數(shù)量為0.05N。

步驟2：父代種群個(gè)體按照適應(yīng)度值非增序排列，選擇最優(yōu)的1%父代個(gè)體直接復(fù)制進(jìn)入新種群。

步驟3：從經(jīng)過(guò)精英保留后的種群中隨機(jī)抽取0.05N個(gè)父代個(gè)體，比較每個(gè)被抽取個(gè)體的適應(yīng)度值，復(fù)制適應(yīng)度值相對(duì)較大的個(gè)體作為新的父代保留。

步驟4：重復(fù)步驟3的操作，直到新的父代種群規(guī)模達(dá)到N。

2.5 交叉操作

本文采用整數(shù)矩陣編碼，選擇單點(diǎn)交叉作為交叉操作方法，然而并非每個(gè)經(jīng)單點(diǎn)交叉后的個(gè)體都是可行解，若新個(gè)體的染色體中存在基因重復(fù)，將導(dǎo)致新個(gè)體成為一個(gè)不可行解。因此本文設(shè)計(jì)了原基因重插入法，以此保證交叉生成的新個(gè)體是可行解，其操作步驟為：

步驟1：隨機(jī)選擇交叉點(diǎn)，假設(shè)交叉點(diǎn)確定為位置4和位置5基因之間處，隨后對(duì)兩個(gè)父代染色體進(jìn)行單點(diǎn)交叉操作，互換交叉點(diǎn)后的基因片段后父代Ⅰ產(chǎn)生的子代染色體為6→5→1→4→1→2。從左往右檢查子代染色體，可以發(fā)現(xiàn)基因1為重復(fù)基因，將較早出現(xiàn)的基因1從染色體中剔除，剔除后的子代染色體變?yōu)?→5→4→1→2。

圖3 步驟1

步驟2：將父代Ⅰ的互換基因片段添加到子代染色體的末尾。

圖4 步驟2

步驟3：再次檢查子代染色體，確認(rèn)基因2為重復(fù)基因，將較后出現(xiàn)的重復(fù)基因剔除，得到可行解子代染色體為6→5→4→1→2→3。

圖5 步驟3

步驟4：當(dāng)父代Ⅱ經(jīng)相同步驟得到子代染色體6→5→4→3→2→1后，交叉操作結(jié)束。

2.5 變異操作

采用互換變異對(duì)染色體進(jìn)行變異操作，如圖6所示，隨機(jī)選定染色體上的兩個(gè)基因（染色體上的第一個(gè)基因除外）互換位置產(chǎn)生新的染色體。

圖6 互換變異

2.6 變鄰域搜索

鄰域結(jié)構(gòu)是變鄰域搜索算法的核心部分，將會(huì)直接影響算法的搜索質(zhì)量。根據(jù)染色體的編碼機(jī)制，設(shè)計(jì)以下兩種鄰域結(jié)構(gòu)：

1）鄰域結(jié)構(gòu)NS1采用部分逆序反轉(zhuǎn)策略。該策略對(duì)原始染色體進(jìn)行較大幅度變動(dòng)，以擴(kuò)大鄰域搜索空間，能夠更好的跳出局部最優(yōu)。例如一條染色體的原本基因編碼為6→5→4→1→2→3，隨機(jī)選擇兩個(gè)基因位置4和6（基因位置1不可選），將兩個(gè)之間的基因逆轉(zhuǎn)，得到新的染色體6→5→4→3→2→1。

2）鄰域結(jié)構(gòu)NS2采用插入策略。該策略隨機(jī)選擇兩個(gè)基因位置（基因位置1不可選），將靠后位置上的基因插入至靠前位置的基因前，位置2之后的基因則依次后移，得到新的染色體。

本文對(duì)構(gòu)造鄰域進(jìn)行動(dòng)態(tài)構(gòu)建，交替使用兩種鄰域結(jié)構(gòu)，避免單一鄰域結(jié)構(gòu)導(dǎo)致搜索效率降低。

2.7 訂單拒絕操作

當(dāng)初始種群經(jīng)過(guò)迭代，滿足遺傳算法終止條件時(shí)，計(jì)算新種群中每一個(gè)體適應(yīng)度值，定義適應(yīng)度值最大的個(gè)體為最優(yōu)個(gè)體，其適應(yīng)度值f(N)即為當(dāng)前種群的最大目標(biāo)函數(shù)值。若該個(gè)體中存在延期訂單，則進(jìn)入訂單拒絕操作：新種群中每一個(gè)體隨機(jī)去掉一個(gè)訂單。

假如某種群個(gè)體的第一條染色體為5→4→1→2→3，隨機(jī)去除一個(gè)訂單（假設(shè)為1號(hào)訂單）后，表示1號(hào)訂單被拒絕，2、3、4、5號(hào)訂單被接受。

被接受的訂單將根據(jù)種群初始化策略，產(chǎn)生新的初始種群。

2.8 SPGA-VNS算法流程

變鄰域半置換遺傳算法（SPGA-VNS）求解流程如圖7所示：

圖7 SPGA-VNS算法流程圖

3 案例分析

3.1 環(huán)境設(shè)置

由于目前針對(duì)兩階段裝配流水線的訂單接受與調(diào)度問(wèn)題研究方面尚未有標(biāo)準(zhǔn)算例提出，為了測(cè)試所提出的SPGA-VNS性能，本文參考已有的文獻(xiàn)生成測(cè)試算例，具體生成方案如下：

第一階段加工機(jī)器數(shù)量有m=2、4、6三種不同數(shù)量，訂單數(shù)量規(guī)模分為小規(guī)模、中規(guī)模和大規(guī)模三種不同數(shù)量規(guī)模，分別對(duì)應(yīng)n=10、20、30，n=50、75、100以及n=150、200。針對(duì)不同規(guī)模的算例，每一種機(jī)器數(shù)量與訂單數(shù)量的組合都采用隨機(jī)的方式，生成10個(gè)算例。

每臺(tái)機(jī)器上的加工或裝配時(shí)間由[1,10]之間的離散均勻分布隨機(jī)產(chǎn)生，即U[1,10]。訂單的單位延期懲罰同樣由U[1,10]隨機(jī)生成。第一階段加工機(jī)器上的準(zhǔn)備時(shí)間由U[1,5]隨機(jī)產(chǎn)生。由于本文所研究問(wèn)題的交貨期為柔性交貨期，所以定義訂單的松弛時(shí)間DTj由U[1,β.PTi]隨機(jī)生成，其中PTi=Σpij，松弛程度β可從集合{0.25，0.50，0.75}中選擇。每個(gè)訂單的交貨期Dj=maxi{DTj+Sijk+Pij+Pj}，訂單的收益Rj服從U[1,20]。

算法參數(shù)具體設(shè)定為：種群規(guī)模N=100、迭代次數(shù)Gen=1、最大迭代次數(shù)maxGen=100、交叉概率CP=0.8、變異概率MP=0.2。

對(duì)比算法如下：

1）遺傳算法(GA)：與SPGA-VNS相比，該遺傳算法在種群初始化、交叉操作方面與SPGA-VNS不同，且未對(duì)變異產(chǎn)生的新種群進(jìn)行鄰域搜索，其他操作都與所提出的SPGA-VNS方法類似。

2）半置換遺傳算法（SPGA）：與SPGA-VNS相比，SPGA在種群初始化、交叉、變異、訂單拒絕等方面均無(wú)區(qū)別，唯一不同是未采用鄰域搜索算法對(duì)種群進(jìn)行鄰域搜索。

SPGA-VNS、SPGA、GA以及CPLEX均在Intel Core i7 CPU、16GB RAM、Windows10操作系統(tǒng)和Python3.7環(huán)境下進(jìn)行編譯。

3.2 結(jié)果分析

本文通過(guò)不同規(guī)模算例優(yōu)化解數(shù)量B-number、對(duì)偶間隙Gap以及CPU計(jì)算時(shí)間Time(s)來(lái)衡量SPGA-VNS算法的性能。備注：CPLEX在3600秒內(nèi)能找到優(yōu)化解，則記可行解為數(shù)量1；在3600秒以外才能找到可行解，則記可行解數(shù)量為0，CPLEX在運(yùn)行時(shí)長(zhǎng)7200秒以內(nèi)無(wú)法找到可行解，則記錄該算例CPLEX的可行解數(shù)量為NA。SPGA-VNS算法在3600秒內(nèi)可以找到目標(biāo)值大于或等于CPLEX的可行解，則記非劣解數(shù)量為1，否則為0。

從表2可以看出，CPLEX雖在小規(guī)模算例中解得127個(gè)可行解，但隨著機(jī)器數(shù)量的增加，可行解數(shù)量也在減少。由于訂單數(shù)量更多的中規(guī)模算例中，CPLEX已難以在規(guī)定時(shí)間內(nèi)求得可行解，因此不再給出大規(guī)模算例下CPLEX可行解和算法非劣解數(shù)量。SPGA-VNS算法在小規(guī)模算例中求得了96個(gè)非劣解，多于SPGA算法的75個(gè)和GA算法的42個(gè)。雖然訂單和機(jī)器數(shù)量的不斷增加，使得三種算法的非劣解數(shù)量雖然都逐漸變少，但SPGA-VNS和SPGA算法的求解性能優(yōu)勢(shì)逐漸明顯，找到的非劣解數(shù)量均遠(yuǎn)多于GA算法。與此同時(shí)，β的增大使得算例的求解難度在不斷上升，CPLEX和三種算法的求解表現(xiàn)均與β呈現(xiàn)出了負(fù)相關(guān)的變化趨勢(shì)。

表2 小規(guī)模和中規(guī)模算例可行解和非劣解結(jié)果表

以上結(jié)果說(shuō)明，利用SPGA-VNS算求解小規(guī)模和中規(guī)模算例是可行的，且隨機(jī)半置換策略在規(guī)模越大的算例中，對(duì)求解效果的提升作用越明顯。

對(duì)偶間隙能夠反映出解在目標(biāo)值層面的相對(duì)優(yōu)劣，對(duì)表3中的對(duì)偶間隙Gap定義如下：

從表3可以看出，小規(guī)模算例中，在只有2個(gè)加工機(jī)器時(shí)，CPLEX能找到目標(biāo)值不低于其他算法的可行解，當(dāng)加工機(jī)器數(shù)量增至4個(gè)時(shí)，SPGA-VNS等三種算法均能找到目標(biāo)值不小于CPLEX的非劣解，且對(duì)偶間隙隨著訂單數(shù)量的增大和β值的上升開始出現(xiàn)負(fù)數(shù)，這表明算法在機(jī)器數(shù)量較多時(shí)，求解質(zhì)量?jī)?yōu)于CPLEX。在所有中等規(guī)模算例中，采用了隨機(jī)半置換策略的SPGA-VNS和SPGA算法都能找到比CPLEX可行解的平均目標(biāo)值更大的優(yōu)化解，并且算例規(guī)模越大，SPGA-VNS和SPGA算法的求解優(yōu)勢(shì)越明顯。

表3 小規(guī)模和中規(guī)模算例平均對(duì)偶間隙結(jié)果表

此外，橫向?qū)Ρ热N算法，在小規(guī)模算例中，SPGA-VNS算法的平均對(duì)偶間隙為-2.12%，略優(yōu)于SPGA和GA算法，但在中規(guī)模算例中，SPGA-VNS算法的求解質(zhì)量表現(xiàn)出了更明顯的優(yōu)勢(shì)，平均對(duì)偶間隙較之SPGA和GA算法分別提升了19.60%和5.38%。

在表4中，重新定義對(duì)偶間隙為SPGA-VNS和SPGA算法的優(yōu)化解與GA算法的優(yōu)化解在目標(biāo)值方面的差距，具體計(jì)算公式如式(18)所示：

表4 大規(guī)模算例平均對(duì)偶間隙結(jié)果表

從表4可以看出，相對(duì)于GA算法，SPGA-VNS和SPGA算法在大規(guī)模算例中，優(yōu)化解的平均目標(biāo)值都有較大幅度的提升。

CPU計(jì)算時(shí)間結(jié)果如表5所示，SPGA-VNS和SPGA算法的求解速度較之GA算法均有著一定幅度的領(lǐng)先，且隨著算例規(guī)模逐漸增大，優(yōu)勢(shì)更加明顯。在大規(guī)模算例中，采用隨機(jī)半置換策略的SPGA算法求解速度提升了17.52%，同樣采用隨機(jī)半置換策略并結(jié)合變鄰域搜索的SPGA-VNS則是進(jìn)一步將求解速度提升了25.39%。

表5 大規(guī)模算例CPU計(jì)算時(shí)間結(jié)果表

表6給出了4×10規(guī)模算例下，采用分開決策、聯(lián)合決策的計(jì)算結(jié)果。通過(guò)訂單利潤(rùn)、延期懲罰、以及訂單延期三個(gè)方面的對(duì)比，可以看出，對(duì)訂單接受和生產(chǎn)調(diào)度進(jìn)行聯(lián)合決策可以在訂單利潤(rùn)目標(biāo)方面比分開決策取得更好的效果，且SPGA-VNS算法可以有效地求解復(fù)雜環(huán)境下的OAS問(wèn)題。

表6 4×10規(guī)模算例分開決策與聯(lián)合決策結(jié)果表

圖8給出了規(guī)模為4×10的小規(guī)模算例在迭代100次時(shí)的算法收斂曲線?？梢钥闯觯琒PGA-VNS和SPGA算法能夠得到較大的適應(yīng)度值，這說(shuō)明隨機(jī)半置換策略能夠有效提高算法求解質(zhì)量；另外，SPGA-VNS算法能在迭代30次左右找到最優(yōu)解，先于SPGA和GA算法，說(shuō)明變鄰域搜索策略有效的加快了算法收斂速度。以上結(jié)果表明，本文提出的SPGA-VNS算法就具有良好的求解質(zhì)量和收斂性。

圖8 小規(guī)模算例算法收斂曲線

4 結(jié)語(yǔ)

本文針對(duì)兩階段裝配流水線的訂單接受與調(diào)度問(wèn)題，在考慮具有訂單序列相關(guān)準(zhǔn)備時(shí)間約束基礎(chǔ)上，建立了以訂單利潤(rùn)最大化為目標(biāo)的TIF-MILP模型，提出了一種采用整數(shù)矩陣編碼、啟發(fā)式規(guī)則改進(jìn)初始種群生成策略、隨機(jī)半置換單點(diǎn)交叉、互換變異等改進(jìn)策略的改進(jìn)遺傳算法SPGA-VNS，并采用原基因重插入法保證新種群個(gè)體均為可行解，結(jié)合變鄰域搜索提高算法的局部搜索能力。最后，通過(guò)不同規(guī)模的隨機(jī)算例測(cè)試結(jié)果表明，SPGA-VNS算法相較于SPGA、GA算法，可以在合理的時(shí)間內(nèi)更快找到目標(biāo)值更大的優(yōu)化解，具有良好的求解質(zhì)量和收斂性。