熊福力，儲(chǔ)夢(mèng)伶

(西安建筑科技大學(xué) 信息與控制工程學(xué)院，陜西 西安 710055)

0 引言

近5年來，中國(guó)等多個(gè)國(guó)家出臺(tái)了一系列政策，推動(dòng)預(yù)制構(gòu)件產(chǎn)業(yè)化發(fā)展，提高其占全部建筑的比例。北京市住房和城鄉(xiāng)建設(shè)委員會(huì)發(fā)布了《2020年生態(tài)環(huán)境保護(hù)工作計(jì)劃和措施》來繼續(xù)穩(wěn)步推進(jìn)裝配式建筑工作，力爭(zhēng)2020年實(shí)現(xiàn)裝配式建筑占新建建筑面積比例30%以上。與現(xiàn)澆施工相比，預(yù)制構(gòu)件因具有耐用性、美學(xué)多功能性、節(jié)能環(huán)保的獨(dú)特優(yōu)勢(shì)[1]而廣受歡迎。

預(yù)制構(gòu)件的生產(chǎn)過程屬于流水生產(chǎn)過程，到目前為止，關(guān)于預(yù)制生產(chǎn)調(diào)度已有不少研究成果。LEU等[2]考慮了起重機(jī)和工人影響因素下的調(diào)度；KO等[3]在處理時(shí)間和系統(tǒng)故障引起的干擾等不確定因素下，研究了預(yù)制構(gòu)件生產(chǎn)調(diào)度；KHALILI等[4]針對(duì)預(yù)制構(gòu)件資源優(yōu)化問題，在考慮預(yù)制構(gòu)件配置策略和組件分組策略的基礎(chǔ)上建立了該類問題的混合整數(shù)線性規(guī)劃模型；CHAN等[5]建立了一個(gè)流水車間排序模型，并采用遺傳算法(Genetic Algorithm, GA)對(duì)模型進(jìn)行優(yōu)化。然而，以上文獻(xiàn)均在假定交貨期固定的條件下研究預(yù)制構(gòu)件生產(chǎn)調(diào)度問題，而在實(shí)際生產(chǎn)中，制造商往往需要根據(jù)企業(yè)的生產(chǎn)能力與客戶協(xié)商制定交貨期，并通過拒絕部分訂單來減少拖期懲罰以獲取最大利潤(rùn)，因此需要綜合考慮交貨期配置和生產(chǎn)調(diào)度。

為了按期交付產(chǎn)品，制造商需要為客戶指定有效的調(diào)度方案并配置合理的工期，否則將會(huì)因生產(chǎn)調(diào)度不當(dāng)導(dǎo)致預(yù)制構(gòu)件延遲交付，增加總工期和總成本并造成客戶流失。合理的優(yōu)化和調(diào)度方法是增加收益、降低成本、提高客戶滿意度和節(jié)約時(shí)間的關(guān)鍵。LI等[6]在新工件到達(dá)時(shí)，通過重調(diào)度確定交貨期；KIM等[7]采用離散時(shí)間仿真方式實(shí)時(shí)響應(yīng)交貨期變化，考慮交貨期不確定下的調(diào)度新規(guī)則，并建立了動(dòng)態(tài)生產(chǎn)調(diào)度模型；SHABTAY[8]以最小化提前懲罰和拖期懲罰為目標(biāo)，研究了一類交貨期可控的單機(jī)調(diào)度問題；CHEN等[9]研究了一個(gè)同時(shí)包含工件處理調(diào)度和交付調(diào)度的單機(jī)調(diào)度問題；BACKER[10]對(duì)離散和間歇過程的提前—拖期調(diào)度問題進(jìn)行研究，但未考慮訂單接受問題；GUERRERO等[11]最早提出訂單接受與調(diào)度(Order Acceptance and Scheduling, OAS)問題。在此基礎(chǔ)上，WANG等[12]開發(fā)了兩種啟發(fā)式調(diào)度方法，在兩臺(tái)功能完全相同的處理機(jī)上實(shí)現(xiàn)了利潤(rùn)最大化；NOBIBON等[13]研究了計(jì)劃訂單和潛在訂單，以及訂單的調(diào)度問題。無論在傳統(tǒng)流水車間生產(chǎn)環(huán)境還是預(yù)制構(gòu)件生產(chǎn)環(huán)境下，有關(guān)訂單接受、調(diào)度與交貨期配置問題的綜合優(yōu)化尚未有文獻(xiàn)報(bào)導(dǎo)。預(yù)制構(gòu)件的工況具有可中斷和不可中斷、串行和并行工序并存等特點(diǎn)[2-5]，比傳統(tǒng)的流水車間生產(chǎn)更加復(fù)雜，在實(shí)際預(yù)制構(gòu)件生產(chǎn)過程中，迫切需要對(duì)交貨期配置、訂單接受和調(diào)度進(jìn)行同時(shí)優(yōu)化，然而三者集成優(yōu)化的難度非常具有挑戰(zhàn)性。

鑒于預(yù)制構(gòu)件生產(chǎn)調(diào)度問題的復(fù)雜性，通常采用智能優(yōu)化算法解決該類問題。在預(yù)制構(gòu)件調(diào)度方面，學(xué)者們采用GA[14-18]、禁忌搜索[19-21]、粒子群優(yōu)化算法[22]、精確算法[23-25]等求解流水車間調(diào)度問題。雖然迭代貪婪算法(Iterated Greedy algorithm, IG)易于實(shí)現(xiàn)且在求解置換流水車間調(diào)度問題上具有較大優(yōu)勢(shì)，但是研究仍然不夠深入；RUZI等[26]設(shè)計(jì)了IG解決置換流水車間調(diào)度問題；RIBAS等[27]針對(duì)阻塞流水車間調(diào)度問題提出一種IG，在計(jì)算時(shí)間和求解質(zhì)量上取得了較好的效果。大多數(shù)IG研究是從改進(jìn)原始標(biāo)準(zhǔn)IG中的破壞—構(gòu)造機(jī)制入手,達(dá)到提升IG求解質(zhì)量和求解效率的目的,而對(duì)IG中鄰域搜索方式的研究相對(duì)較少。

本文針對(duì)預(yù)制構(gòu)件的實(shí)際生產(chǎn)過程，建立了交貨期配置、訂單接受與調(diào)度集成(Integrated Due date assignment, Order acceptance and Scheduling in Precast Production Environments, IDOS_PPE)優(yōu)化模型。在交貨期可變的情況下固定工件排序，通過統(tǒng)計(jì)和深入分析實(shí)際生產(chǎn)數(shù)據(jù)，挖掘問題知識(shí)用于引導(dǎo)算法搜索方向，探討問題的解決方案，獲取最優(yōu)交貨期策略，通過集成變鄰域結(jié)構(gòu)提出一種用于求解IDOS_PPE問題的高效IG來優(yōu)化預(yù)制生產(chǎn)總收益，以期為預(yù)制構(gòu)件制造企業(yè)提供啟示。

1 IDOS_PPE優(yōu)化模型

1.1 問題描述

IDOS_PPE問題可被描述如下:在預(yù)制流水車間環(huán)境中，需要被安排的待加工工件集合J={j1,j2,…,jJ}；每個(gè)待加工工件j需在6道工序S={S1,S2,…,S6}上處理且每種類型工件的各道工序處理時(shí)間pj,s均已知；工序之間遵循工藝約束,每個(gè)工件按照預(yù)制構(gòu)件的生產(chǎn)流程依次經(jīng)過6道工序進(jìn)行生產(chǎn)，即各工件依次經(jīng)過模具組裝、預(yù)埋件安裝、澆筑、蒸汽養(yǎng)護(hù)、拆模和精加工；要求同時(shí)優(yōu)化訂單交貨期、訂單選擇和生產(chǎn)調(diào)度，使凈利潤(rùn)最大。需要指出的是，與傳統(tǒng)流水車間調(diào)度問題相比，IDOS_PPE問題具有如下特點(diǎn)：

(1)研究對(duì)象層面

與傳統(tǒng)流水線不同的是，預(yù)制構(gòu)件生產(chǎn)流水線具有串并行混合生產(chǎn)的特點(diǎn)，例如在蒸汽養(yǎng)護(hù)階段，多個(gè)蒸汽養(yǎng)護(hù)室可以同時(shí)并行處理多個(gè)工件，而其他5個(gè)生產(chǎn)階段則為串行生產(chǎn)階段，同一時(shí)刻只能處理一個(gè)工件。同時(shí)從預(yù)制構(gòu)件生產(chǎn)實(shí)際出發(fā)，考慮8小時(shí)工作制和4小時(shí)加班制，每天都有12 h非工作時(shí)間，這個(gè)時(shí)間段內(nèi)需要工人參與的生產(chǎn)過程將無法進(jìn)行，而傳統(tǒng)的流水生產(chǎn)[26-27]通常假設(shè)一天24 h均可利用；預(yù)制構(gòu)件生產(chǎn)流程中既包括可中斷工序又包括不可中斷工序，如圖1所示。例如在澆筑階段，一旦開工就不允許中斷，因此在澆筑階段安排生產(chǎn)時(shí)，應(yīng)該考慮在工人下班之前能否完成，如果無法完成，則安排在下一個(gè)工作日開工；在模具組裝、預(yù)埋件安裝、拆模和精加工等生產(chǎn)階段，如果加班后還無法完成，則允許中斷，未完成的工作將推遲到下一個(gè)工作日，而傳統(tǒng)的流水生產(chǎn)過程通常假設(shè)各個(gè)階段的生產(chǎn)過程不可間斷。綜上所述，本文研究對(duì)象考慮了可利用時(shí)間與不可利用時(shí)間、串并行混合、可中斷與不可中斷混合等生產(chǎn)特點(diǎn)，比傳統(tǒng)的流水車間更加復(fù)雜。

(2)決策問題層面

傳統(tǒng)的流水車間調(diào)度問題通常假定訂單和交貨期固定，對(duì)流水線的工件生產(chǎn)做出調(diào)度決策。在預(yù)制構(gòu)件生產(chǎn)競(jìng)爭(zhēng)日益激烈的環(huán)境下，為避免過高的懲罰費(fèi)用并追求利潤(rùn)最大化，預(yù)制構(gòu)件制造商通常并不盲目接受所有訂單，而是根據(jù)預(yù)制構(gòu)件企業(yè)生產(chǎn)能力和顧客需求選擇可以獲得更多利潤(rùn)的訂單；同時(shí)在顧客容許的范圍內(nèi)確定交貨期，進(jìn)而安排訂單生產(chǎn)調(diào)度。因此，該問題是比傳統(tǒng)流水車間調(diào)度問題更復(fù)雜的多層次離散集成優(yōu)化問題，需要對(duì)訂單選擇、交貨期配置和生產(chǎn)調(diào)度進(jìn)行綜合決策。

1.2 參數(shù)及變量說明

(1)模型標(biāo)引及參數(shù)

J為訂單數(shù)量；

j為訂單索引，j∈J:={1,…,J}；

[k]為位置索引，k∈K:={1,2,…,J}，表示在一個(gè)生產(chǎn)序列中的第k個(gè)位置；

s為工序索引，s∈S:={1,2,…,6}；

pj,s為訂單j在第s道工序的處理時(shí)間；

Qj為訂單j的毛利潤(rùn)；

HW為工作日正常工作時(shí)間，HW=8 h；

HA為工作日允許加班時(shí)間，HA=4 h；

HN為工作日非工作時(shí)間；

deadlinej為訂單j的截止日期；

wj為訂單j的單位時(shí)間拖期懲罰系數(shù)；

γj為客戶滿意度系數(shù)；

πj為序列中的第j個(gè)訂單；

Π為訂單調(diào)度方案，π∈П:={π1,π2,…,πj}。

(2)決策變量

yj為二進(jìn)制變量，如果訂單j被接受則為1，否則為0。

xj,[k]為二進(jìn)制變量，如果訂單j被接受并分配給生產(chǎn)序列中的第k個(gè)位置則為1，否則為0；

Cj為訂單j六道工序的完工時(shí)間，Cj:=Cj,6；

Cj,s為訂單j在第s道工序的完工時(shí)間；

C[k],s為訂單j在生產(chǎn)序列第k個(gè)位置第s道工序的完工時(shí)間；

Tj為訂單j的拖期；

A[k],s為訂單在生產(chǎn)序列第k個(gè)位置第s道工序的累計(jì)時(shí)間；

D[k],s為訂單在生產(chǎn)序列第k個(gè)位置第s道工序的累計(jì)工作天數(shù)。

1.3 數(shù)學(xué)模型

大多數(shù)企業(yè)在預(yù)制構(gòu)件生產(chǎn)調(diào)度環(huán)節(jié)希望盡可能多地獲得利潤(rùn),因此以最大化凈利潤(rùn)為優(yōu)化目標(biāo)建立調(diào)度優(yōu)化模型。本文所建模型基于如下假設(shè):①訂單在機(jī)器上的設(shè)定時(shí)間忽略不計(jì)；②工位和模具之間的緩沖區(qū)是無限的；③生產(chǎn)中沒有優(yōu)先權(quán)，先處理到達(dá)訂單；④不考慮機(jī)器故障、工人缺勤等緊急情況；⑤來自同一個(gè)客戶的訂單分解為多個(gè)生產(chǎn)訂單，一個(gè)生產(chǎn)訂單抽象為一個(gè)工件。

(1)

yj∈{0，1},xj,[k]∈{0，1}；

(2)

C[k],s≥0,D[k],s≥0,A[k],s≥0；

(3)

(4)

(5)

(6)

(7)

D[k],s=?A[k],s/24?,?s；

(8)

s∈{1,2,3,5,6},k∈K{1};

(9)

s∈{1,2,5,6},k∈K；

(10)

(11)

(12)

C[k],s=

s=4,k∈K。

(13)

其中：式(1)為目標(biāo)函數(shù)，TNR為總凈利潤(rùn)，NRj為訂單j的凈利潤(rùn)；式(2)定義兩類決策變量；式(3)為各變量的取值范圍；式(4)約束訂單j最優(yōu)交貨期的取值范圍；式(5)計(jì)算完工時(shí)間大于交貨期時(shí)的拖期；式(6)約束每個(gè)被接受的訂單都分配至序列中的一個(gè)位置；式(7)約束任一訂單的加工必須且僅能在該工序?qū)?yīng)的機(jī)器上完成一次；式(8)計(jì)算工作天數(shù)。

預(yù)制構(gòu)件6道工序的完成時(shí)間可由式(9)～式(13)得到。其中式(9)為傳統(tǒng)流水車間訂單加工的累計(jì)完成時(shí)間，即訂單某道工序的完工時(shí)間等于其開始時(shí)間與處理時(shí)間之和；式(10)為在傳統(tǒng)流水車間基礎(chǔ)上，預(yù)制構(gòu)件八小時(shí)工作制且不可加班約束條件下，第1,2,5,6道工序的完工時(shí)間。

澆筑(第3道工序)為不可間斷工序且需順序執(zhí)行，因此若不能在包括加班的時(shí)間段內(nèi)完成，則需推遲到下一個(gè)工作日進(jìn)行。式(11)是在傳統(tǒng)流水車間基礎(chǔ)上，考慮預(yù)制構(gòu)件八小時(shí)工作制且可加班的條件下，第3道工序的完工時(shí)間。

蒸汽養(yǎng)護(hù)為不可間斷工序且可多個(gè)訂單并行加工，需12 h不間斷處理，因此存在兩種情況：①養(yǎng)護(hù)過程可在包括加班的時(shí)間段內(nèi)完成；②養(yǎng)護(hù)過程在夜間完成，其完成時(shí)間視為下一個(gè)工作日的開始時(shí)間。式(12)為傳統(tǒng)流水車間的完成時(shí)間；式(13)為在傳統(tǒng)流水車間基礎(chǔ)上，考慮預(yù)制構(gòu)件八小時(shí)工作制且可加班的條件下，第4道工序的完工時(shí)間。

本文首先給出固定調(diào)度排序下的最優(yōu)交貨期配置性質(zhì)和最優(yōu)交貨期配置策略，然后給出集成交貨期配置策略的混合迭代貪婪算法(Hybrid Iterated Greedy algorithm, HIG)。最后通過與枚舉法的計(jì)算結(jié)果對(duì)比，分析了基于問題特征提出的知識(shí)結(jié)構(gòu)對(duì)集成算法的影響，進(jìn)而驗(yàn)證了最優(yōu)配置策略的有效性。

2 交貨期配置策略

針對(duì)該問題，在給定調(diào)度序列的情況下可以得到如下性質(zhì)：

算法1固定排序情況訂單接受與交貨期指派偽代碼。

輸入：算例數(shù)據(jù)和算法參數(shù)。

1 Set Π←(π1,π2,…,πj,…,πJ)

2 Set ΠA=Φ,ΠR=Φ

3 for all j:=1 to J do

4 Compute the completion time of order πj

5 If Cπj

6 accept order πj,ΠA:=ΠA∪{πj}

7 else

8 reject order πj,ΠR:=ΠR∪{πj}

9 recompute Cπj+1,…,CπJ

10 end if

11 end for

12 for all orders πj∈ΠA

13 If γπj=0, then

18 else

21 end if

22 end for

3 混合迭代貪婪算法

因?yàn)橛嘘P(guān)IDOS_PPE的研究至今未見報(bào)道，而傳統(tǒng)的預(yù)制構(gòu)件生產(chǎn)調(diào)度[2-5]或流水車間調(diào)度的研究一般僅限于對(duì)機(jī)器上的工件排序進(jìn)行單一決策，所以其調(diào)度算法很難直接應(yīng)用于IDOS_PPE問題，需要根據(jù)問題特點(diǎn)設(shè)計(jì)特定算法。本章通過集成啟發(fā)式初始化方法、最優(yōu)交貨期配置策略、多種鄰域結(jié)構(gòu)和破壞—構(gòu)造機(jī)制，提出一種有效的混合IG搜索框架，其算法偽代碼如算法2所示。該算法框架的特點(diǎn)在于可以根據(jù)給定調(diào)度，結(jié)合最優(yōu)交貨期性質(zhì)，快速給出最優(yōu)交貨期，從而提高目標(biāo)函數(shù)的評(píng)價(jià)效率，同時(shí)通過集成啟發(fā)式、鄰域搜索和破壞—構(gòu)造機(jī)制有效改進(jìn)問題求解質(zhì)量?；谠摽蚣?，結(jié)合不同的鄰域搜索方式，提出4種HIG(HIG_VNA，HIG_LS1，HIG_LS2，HIG_LS3)。因?yàn)閭鹘y(tǒng)預(yù)制構(gòu)件生產(chǎn)調(diào)度問題通常采用GA[2-5]求解，所以在驗(yàn)證知識(shí)結(jié)構(gòu)(性質(zhì)1～性質(zhì)3)有效性的基礎(chǔ)上，還設(shè)計(jì)了基于集成問題知識(shí)的混合GA框架?；谠摽蚣?，結(jié)合不同的鄰域搜索方式，提出兩種混合GA與HIG進(jìn)行對(duì)比，詳見4.2.2節(jié)。下面具體介紹編碼方式、初始化、局部搜索和破壞—構(gòu)造等重要算法組成。

算法2IG算法偽代碼。

輸入：算例數(shù)據(jù)和算法參數(shù)。

輸出：最佳解Π*和對(duì)應(yīng)的目標(biāo)函數(shù)值TNR(Π*)。

1 Π0←GenerateInitialSolutionby NEH-based heuristic;

2 Π*←LS(Π0)

3 repeat

4 Πp←Destruction(Π*)

5 Π′←Construction(Πp)

6 Π′←LS(Π′)

7 Π*←AcceptanceCriterion(Π*,Π′)

8 until termination condition is met

9 return Π*,TNR(Π*)

3.1 編碼方式

將HIG中J個(gè)訂單的調(diào)度序列Π設(shè)置為一個(gè)1×J向量，按照訂單的排列順序從左至右進(jìn)行生產(chǎn)加工，對(duì)于訂單被拒而導(dǎo)致的訂單數(shù)量小于J的序列,用0填充以滿足向量的完整性。

3.2 初始化

采用構(gòu)造啟發(fā)式算法進(jìn)行初始化，得到質(zhì)量較好解。首先將一批訂單中每個(gè)訂單6道工序的總時(shí)間按非遞增順序排列，選擇兩個(gè)時(shí)間最少的訂單作為集合Π1，剩余訂單組成集合Π2。將Π2中的每個(gè)訂單插入使TNR最大的Π1中，保存并更新當(dāng)前最好解。

3.3 局部搜索

為提高算法的全局搜索能力，防止算法陷入局部最優(yōu)，設(shè)計(jì)了4種鄰域搜索方法，進(jìn)而給出4種混合迭代搜索算法。

(1)LS1(基于Swap_all操作) 從調(diào)度序列Π=(π1,π2,…,πj,…,πk,…,πJ)中按順序依次交換(π1,π2),(π1,π3),…,(π1,πJ),…,(π2,π3),…,(π2,πJ),…,(πJ-1,πJ)，保留并更新當(dāng)前最好解。

(2)LS2(基于Insert操作) 即在序列Π*中每次隨機(jī)選擇一個(gè)之前未被選擇的訂單插入剩余訂單的所有位置，保留并更新當(dāng)前最好解。

(3)LS3(基于Swap_double和Insert操作) 通過調(diào)整兩種鄰域結(jié)構(gòu)的比例，按照一定概率對(duì)Swap_double和Insert兩種鄰域結(jié)構(gòu)進(jìn)行選擇。其中Swap_double操作，即從一個(gè)完整序列Π=(π1,π2,…,πj,…,πk,…,πJ)中隨機(jī)選擇兩個(gè)不同位置的訂單πj和πk進(jìn)行交換，形成新序列Π*=(π1,π2,…,πk,…,πj,…,πJ)。

(4)變鄰域上升搜索策略(Variable Neighborhood Ascend, VNA)k=1表示運(yùn)用Swap_all操作，k=2表示運(yùn)用Insert操作，偽代碼如下：

算法3VNA。

輸入：當(dāng)前解Π,當(dāng)前最佳解Π*。

輸出：最佳解Π*和對(duì)應(yīng)的目標(biāo)值TNR(Π*)。

1 k=1

2 while k≤2 do

3 Π′:=LSk(Π)% LSk：using local search strategy k

4 If TNR(Π′)>TNR(Π)do

5 Π:=Π′

6 k:=1

7 else if

8 k:=k+1

9 end if

10 If TNR(Π)>TNR(Π*)do

11 Π*:=Π

12 break

13 end if

14 end while

15 return Π*,TNR(Π*)

3.4 破壞—構(gòu)造階段

在IG中，采用破壞與重新構(gòu)造策略對(duì)最優(yōu)解進(jìn)行擾動(dòng)，防止其陷入局部最優(yōu)。從序列Π*中隨機(jī)選擇d個(gè)訂單并從Π*中刪除，然后按已選擇的順序?qū)⑵涮砑拥溅癲中，最后將Πd中的每個(gè)訂單逐步插入Π*，保留并更新當(dāng)前最好解。

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

所有實(shí)驗(yàn)均在Intel Core i7-9700，1.80 GHz CPU，8.00 G RAM，Win10 64位操作系統(tǒng)和MATLAB 2016a編程環(huán)境下編譯運(yùn)行。因?yàn)槟壳皼]有標(biāo)準(zhǔn)測(cè)試算例測(cè)試PPFSP(precast permutation flow shop scheduling problem),所以以Brandimarte[28]預(yù)制構(gòu)件車間調(diào)度問題標(biāo)準(zhǔn)算例中的10種不同類型訂單為基礎(chǔ)，選取小、中、大規(guī)模訂單，每種規(guī)模訂單隨機(jī)生成10組算例，算例中各道工序的生產(chǎn)數(shù)據(jù)如表1所示。

表1 各類型預(yù)制構(gòu)件6道工序的實(shí)際生產(chǎn)數(shù)據(jù)[28]

通過田口方法調(diào)節(jié)算法參數(shù)，得到優(yōu)化后的參數(shù)，如表2所示。

表2 算法參數(shù)說明

枚舉法是在訂單最優(yōu)交貨期不確定的情況下，通過逐個(gè)計(jì)算所有可選擇的交貨期來尋找最優(yōu)NR。圖2所示為γ在不同取值下通過枚舉法計(jì)算得到的3種不同類型訂單的目標(biāo)值隨交貨期變化的趨勢(shì)，其中橫軸表示交貨期，縱軸表示目標(biāo)值。當(dāng)γ過小時(shí)，如圖2a～圖2c所示，訂單交貨期越大，TNR越大，然而由于忽略了顧客滿意度，不利于工廠長(zhǎng)遠(yuǎn)發(fā)展；當(dāng)γ過大時(shí)，如圖2e和圖2f所示，部分訂單在交貨期下均為零或負(fù)值，不符合實(shí)際生產(chǎn)要求。因此，最終選擇γ=3。

4.2 結(jié)果分析

4.2.1 知識(shí)結(jié)構(gòu)對(duì)算法的影響

為進(jìn)一步說明所提知識(shí)結(jié)構(gòu)(性質(zhì)1～性質(zhì)3)的有效性，將通過知識(shí)結(jié)構(gòu)(性質(zhì)1～性質(zhì)3)配置交貨期和采用枚舉法計(jì)算交貨期兩種方法在充分的迭代次數(shù)下，從最大值、平均值和運(yùn)算時(shí)間進(jìn)行對(duì)比，結(jié)果如表3所示。兩種對(duì)比算法(基于枚舉法的HIG和基于問題特定知識(shí)的HIG)在相同規(guī)模算例下，計(jì)算結(jié)果的平均值與最大值的平均偏差率均小于0.16%，驗(yàn)證了用知識(shí)結(jié)構(gòu)(性質(zhì)1～性質(zhì)3)設(shè)計(jì)求解規(guī)則的方法是可行且有效的。在算法效率方面，融入知識(shí)結(jié)構(gòu)(性質(zhì)1～性質(zhì)3)的HIG算法在J= 20，30，50，70時(shí)，運(yùn)行時(shí)間分別提高8.55%，9.88%，14.33%，16.10%。隨著訂單規(guī)模的增大，與基于枚舉法的混合HIG相比，基于問題知識(shí)結(jié)構(gòu)(性質(zhì)1～性質(zhì)3)的HIG在求解時(shí)間上的優(yōu)勢(shì)更為明顯。因此，該知識(shí)結(jié)構(gòu)能有效降低工廠因計(jì)算而產(chǎn)生的時(shí)間浪費(fèi)，提高工廠的整體運(yùn)行效率。

表3 基于知識(shí)結(jié)構(gòu)和枚舉法的HIG比較

續(xù)表3

4.2.2 算法性能對(duì)比分析

求解預(yù)制構(gòu)件流水車間調(diào)度問題最常用的智能算法是GA[16-19]，由于傳統(tǒng)GA具有全局搜索性強(qiáng)、收斂速度慢且易早熟的特點(diǎn)，針對(duì)每一代搜索到的最佳個(gè)體進(jìn)行局部搜索，提出HGA_LS2和HGA_VNA算法作為HIG的對(duì)比算法。為進(jìn)一步說明變鄰域上升搜索策略VNA的優(yōu)越性，對(duì)6種算法(HIG_VNA，HGA_LS1，HGA_LS2，HIG_LS3，HGA_LS2HGA_VNA)進(jìn)行比較。由圖3可知，由于并行結(jié)構(gòu)的優(yōu)越性和特殊性，所有算法均快速收斂。其中，HIG_LS1算法的收斂速度最快，但求解質(zhì)量較差，算法易陷入局部最優(yōu)；HIG_VNA算法的收斂速度僅次于HIG_LS1。在所有算例中,無論解的質(zhì)量還是算法的收斂精度和穩(wěn)定性，6種算法中HIG_VNA算法解的質(zhì)量在各規(guī)模算例中均為最好。

為比較HIG_VNA算法的性能，對(duì)不同規(guī)模的90個(gè)算例進(jìn)行測(cè)試，分別用6種算法求解。為公平比較，對(duì)每個(gè)訂單規(guī)模為J的測(cè)試算例獨(dú)立運(yùn)行10次，停止準(zhǔn)則設(shè)置為最大運(yùn)行時(shí)間(J·6/10) s。表4所示為各算法在不同規(guī)模算例下最大值和平均值的相對(duì)偏差率，圖4所示為6種算法的平均偏差率ARPD，圖5所示為不同規(guī)模算例下的平均值與標(biāo)準(zhǔn)差的誤差棒。本文采用平均相對(duì)偏差率ARPD評(píng)估算法整體性能：

表4 各算法在不同規(guī)模算例下最大值和平均值的相對(duì)偏差率

續(xù)表4

l=1，…，L；

(14)

(15)

在6種算法中，HIG_VNA在所有算例上的最大值和平均值均最為優(yōu)異，HIG_LS2次之，HIG_LS3表現(xiàn)最差，由此表明HIG_VNA在求解預(yù)制構(gòu)件OAS問題時(shí)具有相對(duì)較好的性能。與HIG_Insert相比，HIG_VNA在J=20,30,50,70算例上，平均值的ARPD分別平均提升0.3%，1.16%，1.12%，1.20%，由此可知VNA變鄰域結(jié)構(gòu)在求解中大規(guī)模問題上的優(yōu)勢(shì)更加明顯。與HGA_VNA相比，HIG_VNA在J=20,30,50,70算例上，最大值的ARPD分別平均提升0.93%，1.27%，2.01%，1.40%，由此可知HIG更適于求解預(yù)制構(gòu)件工期配置、OAS的集成優(yōu)化問題。綜上所述，因?yàn)镠IG的破壞—構(gòu)造機(jī)制保留了全局搜索能力，獨(dú)特的變鄰域結(jié)構(gòu)VNA進(jìn)一步提高了算法的局部尋優(yōu)能力，所以HIG_VNA算法具有優(yōu)秀的尋優(yōu)能力。

由圖4可見，對(duì)于所有算例，HIG_VNA的標(biāo)準(zhǔn)差比HGA_VNA更小，說明HIG_VNA具有更好的魯棒性，算法性更穩(wěn)定。在J=20算例中，HGA_VNA的3個(gè)算例、HGA_LS2的4個(gè)算例，HIG_LS2的7個(gè)算例找到了當(dāng)前最好解，HIG_VNA找到全部當(dāng)前最好解，主要原因是小規(guī)模算例中各算法搜到全局最優(yōu)解的概率較大。

5 結(jié)束語

為克服預(yù)制構(gòu)件工期緊張和生產(chǎn)能力不足的問題，本文以最大化總凈利潤(rùn)為目標(biāo)，針對(duì)IDOS_PPE問題建立了混合整數(shù)非線性數(shù)學(xué)規(guī)劃模型。鑒于該問題的復(fù)雜性，首先給出固定調(diào)度排序下交貨期的最優(yōu)配置，在此基礎(chǔ)上，通過集成問題特定知識(shí)、快速啟發(fā)式方法、VNA變鄰域結(jié)構(gòu)和破壞—構(gòu)造機(jī)制，提出一種有效的混合迭代貪婪搜索框架用以同時(shí)確定最優(yōu)交貨期、可接受的訂單和調(diào)度排序。計(jì)算結(jié)果顯示，該算法在各種訂單規(guī)模下均顯示出較好的求解速度和求解質(zhì)量，可為預(yù)制構(gòu)件生產(chǎn)企業(yè)決策者提供很好的參考。

未來研究可考慮動(dòng)態(tài)環(huán)境(如機(jī)器故障、緊急訂單等突發(fā)事件)下的預(yù)制構(gòu)件OAS問題。隨著目前生產(chǎn)制造的全球化，為提高生產(chǎn)競(jìng)爭(zhēng)力，很多預(yù)制構(gòu)件由原來的單工廠制造模式轉(zhuǎn)向分布式多工廠制造模式，在本文算法框架基礎(chǔ)上研究分布式預(yù)制構(gòu)件OAS問題將是很有意義的課題。