熊福力，杜 瑤，曹勁松，汪琳婷

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

0 引言

裝配式建筑現(xiàn)已成為國家和行業(yè)大力發(fā)展的新型建筑模式，具有施工時間短、生產(chǎn)效率高、環(huán)境污染小等特點。預(yù)制構(gòu)件作為裝配式建筑中極為重要的一環(huán)，也受到了這種新興建筑模式發(fā)展帶來的機遇和挑戰(zhàn)。然而，對于國內(nèi)現(xiàn)階段預(yù)制構(gòu)件生產(chǎn)模式而言，全自動化生產(chǎn)方式現(xiàn)在還為時過早，所有預(yù)制件工廠都采用機器處理與工人作業(yè)共存的方式。因此對于這種生產(chǎn)模式，同一項工作的效益可能隨所配置的工人不同而有很大的區(qū)別。這也導(dǎo)致相同工序的處理時間的可變性，最終將影響生產(chǎn)調(diào)度的可靠性。這種缺陷將造成生產(chǎn)管理效率低下、生產(chǎn)計劃失效，潛在地導(dǎo)致運營混亂、工期延長和供應(yīng)鏈成本增加。因此，工人配置與預(yù)制構(gòu)件生產(chǎn)調(diào)度的集成優(yōu)化對現(xiàn)階段預(yù)制構(gòu)件生產(chǎn)調(diào)度研究具有重要的理論意義和實用價值。

在預(yù)制構(gòu)件生產(chǎn)調(diào)度問題上，近年來已取得一定的成果。CHAN等[1]以最小化完工時間和拖期/提前交貨懲罰成本為目標(biāo)建立了流水車間調(diào)度模型(Flow Shop Scheduling Model, FSSM)；KO等[2]在此基礎(chǔ)上建立了預(yù)制構(gòu)件生產(chǎn)六階段生產(chǎn)模型；YANG等[3]以最小化空閑時間、拖期和提前懲罰、存儲成本、完工時間等目標(biāo)建立了多預(yù)制生產(chǎn)線的FSSM。隨后WANG等[4]提出了改進的九階段生產(chǎn)調(diào)度模型，并考慮了模具制造、預(yù)制件存儲和運輸?shù)纫蛩貙ιa(chǎn)過程的影響。熊福力等[5]以最大化總凈利潤為目標(biāo)解決了預(yù)制構(gòu)件生產(chǎn)中交貨期配置、訂單選擇與生產(chǎn)調(diào)度的同時決策問題。秦璇等[6]則考慮了預(yù)制構(gòu)件生產(chǎn)過程中受資源約束的多目標(biāo)調(diào)度問題。上述研究缺乏實現(xiàn)生產(chǎn)成本和及時交貨這兩個相互沖突的目標(biāo)之間權(quán)衡的方法。此外，實際生產(chǎn)中會有一定因素的干擾，每道工序的處理時間會隨著工人資源配置的不同而不同，進而對生產(chǎn)調(diào)度造成直接影響，但以上研究中皆把每道工序的處理時間設(shè)置為固定值，即假定工人資源已經(jīng)配置好，在實際生產(chǎn)過程中往往需要根據(jù)實際訂單情況，對工人資源和生產(chǎn)調(diào)度進行集成優(yōu)化。

在考慮勞動力資源的調(diào)度優(yōu)化方面，YURA[7]首先加入了對人員因素的考慮，提出員工對于生產(chǎn)進度表的滿意度是維持員工士氣的重要原因，理想的生產(chǎn)計劃應(yīng)根據(jù)員工的工作日、休假、加班等偏好調(diào)度，提出在到期日約束下滿足工人的偏好；THOMPSON等[8]考慮使用具有不同生產(chǎn)力的員工組來制定勞動力計劃的問題；ELSHAFEI等[9]提出一種動態(tài)規(guī)劃(Dynamic Programming, DP)算法，解決具有若干實際休假時間約束的人工調(diào)度問題，并給出了每個員工的工作順序所決定的成本結(jié)構(gòu)，同時提出一個適合于中等規(guī)模實例的DP算法來確定最優(yōu)的工作分配，使總?cè)斯こ杀咀钚』?，同時在規(guī)定的約束條件下滿足工作需求；PAN等[10]提出一種具有兩階段啟發(fā)式算法的混合整數(shù)規(guī)劃模型，用于解決精密工程行業(yè)的人力調(diào)度問題，并提出一個兩階段的啟發(fā)式算法，第一階段通過考慮作業(yè)，機器和其生產(chǎn)計劃來計算每個班次的技能要求，第二階段通過考慮技能及來分配操作員到機器；ZHANG等[11]開發(fā)了一種改進的學(xué)習(xí)曲線來代替對數(shù)線性學(xué)習(xí)曲線，以監(jiān)控工人績效的提升，還考慮了工人先前的經(jīng)驗和機器在學(xué)習(xí)過程中的影響；AHMADIAN FARD FINI等[12]提出一種數(shù)學(xué)模型，用于確定機組人員具有不同經(jīng)驗水平的單技能和多技能工人的最佳組合，以通過考慮多技能、不同技能水平和學(xué)習(xí)對機組人員的重疊影響來最大限度地縮短建設(shè)項目的工期生產(chǎn)率;陳俊杰等[13]建立了考慮勝任力差異的人力資源受限多目標(biāo)項目調(diào)度問題模型，提出兩階段優(yōu)化算法。上述工人配置問題研究中，在裝配式建筑背景下，尚未有集成預(yù)制構(gòu)件生產(chǎn)調(diào)度與工人配置的研究，究其原因主要有以下兩點：

(1)從研究背景層面看，裝配式建筑背景下的預(yù)制構(gòu)件生產(chǎn)屬于新興產(chǎn)業(yè)，發(fā)展時間較短，雖然目前已有一些針對預(yù)制構(gòu)件生產(chǎn)調(diào)度問題的相關(guān)研究，隨著實際生產(chǎn)管理問題的不斷涌現(xiàn)，以及信息技術(shù)和優(yōu)化技術(shù)的不斷發(fā)展，還存在較大的研究發(fā)展空間。而本文所研究的問題就是其中之一。

(2)從問題本身層面看，預(yù)制構(gòu)件生產(chǎn)工序之間的差異較大，具有可利用時間與不可利用時間混合、串并行混合、可中斷和不可中斷混合以及資源可利用時間和資源量受限等特點，通常來講，即使是單一工人配置問題和單一的生產(chǎn)調(diào)度問題就已經(jīng)是NP-hard問題，因此在這種復(fù)雜生產(chǎn)背景下，將二者集成優(yōu)化無疑具有一定的挑戰(zhàn)性，但同時對于提高預(yù)制構(gòu)件生產(chǎn)企業(yè)凈收益和改善客戶滿意度具有重要的意義。

基于以上分析，本文考慮了預(yù)制構(gòu)件生產(chǎn)背景下的生產(chǎn)調(diào)度與工人配置集成優(yōu)化問題，以期為預(yù)制構(gòu)件制造企業(yè)及類似制造企業(yè)提供有價值的管理啟示。首先以最小化工人成本和拖期懲罰總費用為目標(biāo)建立了預(yù)制構(gòu)件工人配置與生產(chǎn)調(diào)度集成優(yōu)化數(shù)學(xué)模型，隨后基于交替分解思想，提出一種交替式混合遺傳—迭代貪婪搜索算法(Alternative Hybrid Genetic-Iterated Greedy Algorithm, AHGA_IG)，并通過大量計算實驗驗證了所提算法的有效性。

1 問題描述與數(shù)學(xué)模型

1.1 生產(chǎn)背景描述

預(yù)制構(gòu)件生產(chǎn)一般包含6道工序：①鑄模；②放置預(yù)埋件；③混凝土澆灌；④蒸汽養(yǎng)護；⑤脫模；⑥修復(fù)。每道工序僅有一臺機器(即單生產(chǎn)線工作模式)。預(yù)制構(gòu)件生產(chǎn)不同于傳統(tǒng)流水車間問題，其生產(chǎn)工序分為可中斷工序(如第1、2、5、6工序)和不可中斷工序(如第3、4工序)。如圖1中可中斷工序情形1和情形2所示，可中斷工序如果可以在工作時間內(nèi)完成，則正常生產(chǎn)；否則，訂單需繼續(xù)處理至下班時間，剩余工作中斷至次日工作時間完成。不可中斷工序(如第3、4工序)指工序在處理完成前不能中斷操作，否則會出現(xiàn)工件損壞等情況，不可中斷工序如果在工人允許加班時間內(nèi)可以完成則加班完成，否則該工序推遲于次日工作時間開始處理，如圖1中不可中斷工序且需要人工情形1和情形2所示。第4道工序蒸汽養(yǎng)護屬于不可中斷工序，但不需要工人操作，因此不受工作時間約束。其完工時間如圖1中不可中斷且不需要人工情形1～情形3所示。

不同的工人配置方案不但會造成訂單處理時間的變化，影響訂單的最大完工時間，而且配置不同等級或不同數(shù)量的工人需要支付的工人薪資成本也會隨之變化。根據(jù)預(yù)制生產(chǎn)過程的實際工人需求，對各工序中所需工人數(shù)量進行約束，如表1所示。其中第4道工序為蒸汽養(yǎng)護，工廠采用全自動化方式處理，不需要工人干預(yù)且處理時間不隨工人配置方案調(diào)整而變化。不同等級的工人具有不同的處理水平和操作熟練度，對同一訂單的處理時間也不相同，同時也具有不同的薪資待遇。因此，對不同等級工人的工作效率和薪資水平作出如下假設(shè)：①將工人分為初級工人、中級工人、高級工人3種等級；②不同等級工人具有不同的工作效率ηl和薪資水平Wl；③工人等級越低，工作效率ηl和薪資水平Wl也越低。訂單調(diào)整處理時間與原處理時間成正比，與分配工人的工作效率ηl和工人數(shù)量Nl,s成反比。為使模型更加精確，工人成本的計算采用績效制，即以工人工作時間計算工人工資，若工作時間為0，則該工人沒有工資。

表1 各生產(chǎn)工序工人數(shù)量約束

1.2 問題描述

基于以上預(yù)制構(gòu)件生產(chǎn)背景，預(yù)制構(gòu)件生產(chǎn)調(diào)度與工人配置集成優(yōu)化問題可描述如下：J個訂單需要按照相同的處理順序經(jīng)過S道預(yù)制構(gòu)件生產(chǎn)工序且訂單在每道工序上只能處理一次，每道工序每次只能同時處理一個訂單(第4道工序蒸汽養(yǎng)護除外，其采用并行處理方式)。各訂單在各工序上所需的處理時間已知，但其會隨工人配置方案的改變而變化，受工人配置方案影響的調(diào)整處理時間在訂單處理前為已知。問題需要對各處理工序上的工人進行配置，計算工人配置后的調(diào)整處理時間，并以最小化工人成本和訂單拖期懲罰為目標(biāo)優(yōu)化生產(chǎn)調(diào)度和工人配置。

為使問題更加明確，對生產(chǎn)過程作出如下假設(shè)：

(1)每道工序有且僅有一臺機器；(2)所有工件、機器在調(diào)度零時刻均為可用狀態(tài)；(3)所有工人在上班時間均為可配置狀態(tài)；(4)所有工人均有能力處理所有工序；(5)每道工序配置的工人均為同一等級；(6)工序間緩沖區(qū)容量為無限；(7)不考慮工件惡化、人員請假和機器突發(fā)故障情況。

(8)各工人采用8小時工作制，允許加班時間不超過3小時，否則必須停止工作。即工作時間HW=8，可加班時間HO=3，非工作時間HN=16。

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

基于以上問題描述，建立如下數(shù)學(xué)模型：

(1)標(biāo)引和輸入?yún)?shù)

J為訂單數(shù)量;

N為工人數(shù)量;

S為工序數(shù)量;

L為工人等級數(shù)量;

j∶={1,2,…,J}為訂單編號;

s∶={1,2,…,S}為工序編號;

l∶={1,2,…,L}為工人等級編號;

Pj,s為工序s上訂單j的原處理時間;

dj為訂單j交貨期;

βj為訂單j單位時間拖期懲罰;

Wl為l級工人單位時間薪水;

ηl為l級工人工作效率;

HW為工作時間;

HO為可加班時間(HO

HN為非工作時間(HN=24-Hw)。

(2)決策變量

Xl,s為工序s中配置的l級工人的數(shù)量;

Yl,s為0-1決策變量，表示工序s中是否配置l級工人;

Cj,s為訂單j在工序s上的完工時間;

Aj,s為訂單j在工序s上的累計完成時間。

(3)目標(biāo)函數(shù)

(1)

(4)約束條件

(2)

(3)

s∈{1,2,5,6},?j；

(4)

s∈{1,2,3,5,6},?j；

(5)

(6)

Cj,3=

(7)

Cj,4=

(8)

(9)

(10)

(11)

(12)

(13)

Xl,s,Cj,s≥0,?l,s；

(14)

(15)

從以上模型可以看出，從變量角度看，模型中既包括連續(xù)變量(如Cj,s)，也包括離散變量(如Xl,s和Yl,s)。從約束角度看，模型中既包括線性約束(如式(2)和式(3))，同時還包括非線性約束(如式(4)～式(8))。綜上所述，該模型難以利用現(xiàn)有商業(yè)優(yōu)化軟件進行直接求解。

本文所研究的問題具有如下特點：①從研究對象層面看，本文所研究的預(yù)制構(gòu)件流水車間具有可利用時間與不可利用時間、串并行混合、可中斷與不可中斷混合、不同技術(shù)等級工人混合等生產(chǎn)特點，比傳統(tǒng)的流水車間更為復(fù)雜。②從問題求解層面看，本文所研究的問題，是比傳統(tǒng)單一流水車間調(diào)度問題或者單一的工人資源配置更為復(fù)雜的多決策離散集成優(yōu)化問題，需要以拖期懲罰和工人成本費用最小化為目標(biāo)，根據(jù)預(yù)制構(gòu)件企業(yè)機器資源和勞動力資源能力以及客戶實際需求，同時對工人配置和生產(chǎn)調(diào)度進行綜合決策，對生產(chǎn)調(diào)度方案和工人配置方案作出綜合決策。需要指出的是，傳統(tǒng)的單一流水車間調(diào)度和工人資源配置問題在大多數(shù)情況下都是典型的NP-hard問題[14]，對于中大規(guī)模問題，精確算法通常難以在合理的時間內(nèi)求得最優(yōu)解，因此，對于本文的集成優(yōu)化問題，將通過深入分析問題結(jié)構(gòu)，集成構(gòu)造啟發(fā)式、最優(yōu)交貨期配置、鄰域搜索以及破壞—構(gòu)造機制，提出有效的混合智能優(yōu)化方法，克服整數(shù)變量、多決策屬性和大量非線性復(fù)雜約束帶來的求解困難。

2 算法設(shè)計

生產(chǎn)調(diào)度與工人配置是預(yù)制構(gòu)件生產(chǎn)中兩個非常重要的管理問題。其中工人配置會對預(yù)制構(gòu)件生產(chǎn)各階段處理時間和生產(chǎn)成本造成較大影響，而各階段處理時間又會對生產(chǎn)調(diào)度結(jié)果產(chǎn)生直接影響；同時生產(chǎn)調(diào)度方案也會對不同等級工人資源配置策略產(chǎn)生直接影響。而在已有對于工人配置問題研究的文獻中，通常采用工人配置與生產(chǎn)調(diào)度的遞階優(yōu)化，而沒有考慮生產(chǎn)調(diào)度方案也會對工人配置造成影響[14]。因此生產(chǎn)調(diào)度與工人配置二者的集成優(yōu)化尤為重要，但這也無疑增加了求解難度。為降低問題求解難度，本文借鑒分解協(xié)調(diào)的思想，將原問題分解為工人指派層子問題和生產(chǎn)調(diào)度層子問題，通過兩個子問題的求解結(jié)果信息交互，交替求解改進每個子問題的解，進而優(yōu)化原問題的總目標(biāo)值。具體來說，基于交替分解思想，通過集成構(gòu)造啟發(fā)式、群體搜索、鄰域搜索和破壞—構(gòu)造機制，提出了一種混合遺傳—迭代貪婪交替搜索算法(AHGA_IG)：其主要思想是首先利用啟發(fā)式方法產(chǎn)生一初始工人配置和生產(chǎn)調(diào)度解；隨后，固定生產(chǎn)調(diào)度方案，設(shè)計一種混合遺傳配置算法用于優(yōu)化工人配置方案；反過來固定工人配置方案，設(shè)計一種迭代貪婪調(diào)度算法用于優(yōu)化生產(chǎn)調(diào)度，如此兩階段交替優(yōu)化，直到滿足終止條件。

與傳統(tǒng)流水車間調(diào)度問題相比，預(yù)制構(gòu)件調(diào)度因為生產(chǎn)工藝中存在串并行混合、可中斷與不可中斷工序和資源可利用時間受限等特點，所以更為復(fù)雜。傳統(tǒng)流水車間調(diào)度問題已被證明具有強NP難特性[15]，因此本文所研究問題同樣屬于NP難問題。對于此類問題，精確算法理論上雖然可以求得最優(yōu)解，但是其求解時間隨問題規(guī)模增大呈指數(shù)倍增長，很難在較短時間內(nèi)給出滿足工業(yè)實際需求的合理解決方案。鑒于智能優(yōu)化方法在解決大規(guī)模組合優(yōu)化問題方面的優(yōu)勢[1-6]，基于交替迭代框架，通過集成構(gòu)造啟發(fā)式、群體搜索、鄰域搜索，以及破壞—構(gòu)造機制，提出一種混合遺傳—迭代貪婪交替搜索算法(AHGA_IG)。其算法流程如圖2所示。在AHGA_IG中，首先根據(jù)啟發(fā)式規(guī)則構(gòu)造初始解，即初始化工人配置方案和生產(chǎn)調(diào)度方案；隨后固定初始生產(chǎn)調(diào)度方案使用遺傳配置算法優(yōu)化工人配置方案；當(dāng)滿足工人配置終止條件時輸出優(yōu)化后工人配置方案，并計算訂單調(diào)整處理時間；再使用迭代貪婪調(diào)度算法優(yōu)化生產(chǎn)調(diào)度方案；當(dāng)滿足生產(chǎn)調(diào)度終止條件時判斷是否滿足總體終止條件，若未滿足則返回工人配置階段按照優(yōu)化后生產(chǎn)調(diào)度方案繼續(xù)優(yōu)化工人配置方案，如此交替迭代優(yōu)化。滿足算法終止條件則輸出優(yōu)化后工人指派方案、生產(chǎn)調(diào)度方案、目標(biāo)函數(shù)值。以下將對混合遺傳—迭代貪婪交替搜索算法的編碼方式、初始解構(gòu)造、遺傳配置算法、迭代貪婪調(diào)度算法和接受準(zhǔn)則部分進行詳細(xì)介紹。

2.1 編碼方式

工人配置問題需要同時為各工序分配不同等級和不同數(shù)量的工人，采用雙層整數(shù)編碼方式。編碼長度為S×n，n=J/n1為訂單組數(shù)，n1為每組訂單的數(shù)量。預(yù)制構(gòu)件生產(chǎn)過程中，預(yù)制構(gòu)件處理時間較長，在大規(guī)模生產(chǎn)問題中，若皆采用同一人員配置不符合實際生產(chǎn)要求，因此將n1個訂單分為一組，每組訂單之間產(chǎn)生不同的工人配置方案。每組工人配置方案中，第一層為分配給各工序的工人數(shù)量；第二層為分配給各工序的工人等級。為便于理解，給出如下實例，如圖3所示。編碼表示第1組(G1)中，第1道工序分配到2級(中級)工人3名；第2道工序分配到1級(初級)工人6名；以此類推，第6道工序則分配到1級(初級)工人4名；其他分組也同樣如此。其中第6道工序為蒸汽養(yǎng)護，屬于自動化過程，不需要工人操作，因此不進行工人分配，工人等級和工人數(shù)量均設(shè)為0。

調(diào)度層采用整數(shù)編碼方式。其中編碼表示為訂單的編號，編號在序列中的前后順序表示訂單的處理順序，位置越靠前，則處理優(yōu)先級越高。如圖4所示，該編碼方式表示的訂單處理順序為：1→3→2→6→8→5→7→9→4→10，則在生產(chǎn)中訂單將按照該順序依次經(jīng)過所有處理工序，不得搶占。

2.2 初始解構(gòu)造

初始解的構(gòu)造對算法的求解速度和解的質(zhì)量有較大的影響，適合于問題的初始解能夠顯著提高算法的搜索性能。因此對初始化工人配置方案和生產(chǎn)調(diào)度方案進行如下說明：

工人配置階段決策變量為各工序所分配的工人數(shù)量和工人等級。因此工人配置問題初始解構(gòu)造采用最小化工人成本和最小化訂單處理時間兩種啟發(fā)式規(guī)則。根據(jù)這兩種啟發(fā)式規(guī)則將產(chǎn)生兩種初始解:①所有分組中的所有工序工人等級分配初級工人，且工人數(shù)量設(shè)定為工序人數(shù)約束的最小值。該初始解分配最小工人數(shù)和最低等級工人，將具有最小的工人成本。②所有分組中的所有工序工人等級分配高級工人，且工人數(shù)量設(shè)定為工序人數(shù)約束的最大值。該初始解將分配最高等級工人和最大工人數(shù)，將具有最高的處理效率，即最小的訂單處理時間。

生產(chǎn)調(diào)度階段中訂單拖期懲罰和訂單交貨期密切相關(guān)，訂單交貨期越長，產(chǎn)生拖期懲罰的可能性越低或產(chǎn)生的拖期懲罰越小。因此，生產(chǎn)調(diào)度問題初始解將按照訂單交貨期排序，交貨期越短則訂單越早處理。

2.3 遺傳配置算法

遺傳算法(Genetic Algorithm, GA)通過模擬生物界中“適者生存”原則，對種群內(nèi)的染色體使用選擇、交叉、變異等操作來更新當(dāng)前解，目前在指派問題的研究中得到廣泛應(yīng)用[16-17]。工人配置問題中采用遺傳配置算法，利用雙層編碼表示工人配置方案，因此采用交叉、變異、選擇3種操作來更新當(dāng)前解具有較大操作便利性。以訂單數(shù)量=20，每組訂單的數(shù)量n1=10，即訂單組數(shù)n=2為例，具體操作流程如圖5a所示，工人配置方案當(dāng)前解為(3,6,1,0,3,4,4,3,3,0,2,4;2,1,2,0,2,1,3,1,1,0,2,3)。首先使用輪盤賭法對種群進行選擇操作，得到(3,6,1,0,3,4,4,3,3,0,2,4;2,1,2,0,2,1,3,1,1,0,2,3)，(3,4,1,0,2,3,2,4,3,0,1,1;3,2,3,0,1,2,3,1,2,0,1,2)兩組解。隨后使用交叉操作。在交叉過程中，首先對染色體第一層工人數(shù)量進行兩點交叉，隨機產(chǎn)生兩個交叉點，將兩交叉點間的染色體交換，保證交叉過程中互換的為相同工序的工人數(shù)量，保證滿足工序上的工人數(shù)量約束。再對第二層進行兩點交叉，隨機產(chǎn)生兩個交叉點，將兩條染色體交叉點間的部分進行交換。對兩層分別進行交叉操作，將增大對解空間的探索和開發(fā)。交叉操作將形成兩條新的染色體(3,4,1,0,3,4,4,4,3,0,1,4;2,2,3,0,2,1,3,1,1,0,1,2)和(3,6,1,0,2,3,2,3,3,0,2,1;3,1,2,0,1,2,3,1,2,0,2,3)。最后對染色體進行變異操作，將變異點處配置的工人數(shù)量和等級按照約束重新配置。變異后形成兩組新的解分別為：(3,4,1,0,5,4,4,4,4,0,1,4;2,2,3,0,1,1,3,1,3,0,1,2)和(3,6,1,0,2,1,2,3,3,0,2,4;3,1,2,0,1,3,3,1,2,0,2,1)。

2.4 迭代貪婪調(diào)度算法

迭代貪婪(Iterative Greedy, IG)算法是一種簡單的算法，具有易于實現(xiàn)、效率高、參數(shù)少等特點，并且適用于任何考慮構(gòu)造方法的問題。IG算法主要通過迭代破壞階段和后續(xù)重建階段來構(gòu)建解決方案，再配合局部搜索與類似于模擬退火的接受準(zhǔn)則來更新當(dāng)前解。并且IG算法在求解生產(chǎn)調(diào)度問題方面已有應(yīng)用并取得了較好的效果[18-19]。因此在解決調(diào)度層問題時設(shè)計了一種混合迭代貪婪調(diào)度算法，使用破壞操作、重建操作以及局部搜索來更新當(dāng)前解。訂單數(shù)量J=10為例，具體操作流程如圖5b所示。生產(chǎn)調(diào)度方案的當(dāng)前解為(1,3,2,6,8,5,7,9,4,10)。破壞規(guī)則為將解決方案中的部分部件剔除，產(chǎn)生不完全的解決方案，被破壞的方案構(gòu)件為(2,5,10)，破壞后的解決方案為(1,3,6,8,7,9,4)。重建操作使用NEH(Nawaz-Enscore-Ham)啟發(fā)式方法，將剔除的部件按照最優(yōu)的方式重新插入不完全的解決方案中，重新構(gòu)成完整的解決方案(5,1,3,10,6,2,8,7,9,4)。最后對完整的解決方案進行局部搜索，將前插點后面的解決方案插入序列最前方，形成新的解(9,4,5,1,3,10,6,2,8,7)。

2.5 接受準(zhǔn)則

3 實驗設(shè)計與計算結(jié)果分析

3.1 實驗設(shè)計

遺傳算法近年來在流水車間生產(chǎn)調(diào)度問題中有較多應(yīng)用，并取得了良好的效果[20-21]，同樣，禁忌搜索算法依據(jù)禁忌表特性避免重復(fù)搜索解決方案，大大提高搜索到全局最優(yōu)解的概率和搜索效率，并且具有較強的避免陷入局部最優(yōu)的能力，在生產(chǎn)調(diào)度問題中也有廣泛應(yīng)用[22-23]。果蠅算法為近年來流水車間中較為新穎的算法[24-25]。因此，為充分驗證AHGA_IG算法的性能，本文還設(shè)計了混合遺傳—禁忌交替搜索算法(AHGA and Tabu Search, AHGA_TS)、混合遺傳交替搜索算法(AHGA_GA)和混合遺傳—果蠅交替搜索算法(AHGA and Fruitfly Optimization Algorithm, AHGA_FOA)用于與AHGA_IG算法進行對比。AHGA_TS算法在生產(chǎn)調(diào)度層中將破壞和重建操作改為禁忌操作；AHGA_GA算法在生產(chǎn)調(diào)度層使用經(jīng)典遺傳算法實現(xiàn)；在AHGA_FOA算法中，調(diào)度層主要參考王凌等[24]提出的離散果蠅算法進行設(shè)計，使用嗅覺和視覺搜索過程對生產(chǎn)調(diào)度層問題進行求解。

目標(biāo)函數(shù)為最小化工人成本與拖期懲罰，但由于各工廠具有不同的薪資待遇，當(dāng)工人成本和拖期懲罰處于不同比重時，可能會對問題的結(jié)果有所影響。為測試不同薪資水平對實驗結(jié)果的影響，將分為3種不同薪資水平情況對各算法進行實驗。實驗中所有算法均采用JAVA語言編程實現(xiàn)，代碼測試環(huán)境為Intel i7_9750H/2.6 GHz/16.0 GB/IntelliJ IDEA。

各訂單交貨期dj按照[MK(1-τ-R/2),MK(1-τ+R/2)]均勻隨機產(chǎn)生，其中MK為利用構(gòu)造啟發(fā)式得到的最大完工時間，τ為松緊系數(shù)，R為產(chǎn)生寬度。實驗數(shù)據(jù)如下：訂單數(shù)量J∈{10,20,30,50,70}，拖期懲罰系數(shù)βj∈{10,20}，每組訂單數(shù)量n1=10。按照訂單數(shù)量分為小(J∈{10})、中(J∈{20,30})、大(J∈{20,70})三種問題規(guī)模進行試驗。每種訂單規(guī)模生成10組不同測試算例，每組算例運行30次，避免隨機誤差對于試驗的影響。對同一規(guī)模算例，為公平起見，所有算法均采用相同時間運行。為評估算法性能，定義平均相對偏差率(ARPD)如下：

(16)

其中：Fmin(Alg)表示當(dāng)前算例中Alg算法取得的最小值(最小化問題的最優(yōu)值);ref為當(dāng)前測試算例的參考值，即所有算法在當(dāng)前測試算例中取得的最小值。

3.2 計算結(jié)果

3.2.1 情形一：低等薪資水平

當(dāng)工人處于低等薪資水平時，為測試3種算法的求解能力和算法間的差異。將各等級工人工作效率ηl及單位時間薪資Wl設(shè)置如表2所示。實驗通過5種訂單規(guī)模，分50組測試算例進行，將每種訂單規(guī)模的10組算例結(jié)果取平均值，得到表3中各算法ARPD均值和標(biāo)準(zhǔn)差均值統(tǒng)計結(jié)果。由表3可以看出，AHGA_IG算法ARPD值最小，其中在訂單規(guī)模為10時，ARPD=0.00%，說明其在該訂單規(guī)模時每次都能求解得到3種算法中的最小值，在3種算法中具有較好的求解質(zhì)量。AHGA_IG算法標(biāo)準(zhǔn)差在各個規(guī)模下均優(yōu)于其他兩種算法，說明該算法具有更好的魯棒性。AHGA_GA算法在求解質(zhì)量上略差于AHGA_IG算法，但優(yōu)于AHGA_TS算法和AHGA_FOA算法。AHGA_TS算法平均標(biāo)準(zhǔn)差達到216.76，遠超于其他算法，因此其魯棒性較差，AHGA_FOA算法標(biāo)準(zhǔn)差與AHGA_IG算法相近，但ARPD值遠超AHGA_IG算法，具有較差的求解質(zhì)量。由此可知，AHGA_IG算法在工人處于低等薪資水平時較其他算法具有較強的求解質(zhì)量和魯棒性。

表2 各級工人工作效率及單位時間薪資表

表3 情形一各算法ARPD均值、標(biāo)準(zhǔn)差(std.)均值統(tǒng)計結(jié)果

3.2.2 情形二：中等薪資水平

在中等薪資水平下，將各等級工人工作效率ηl及單位時間薪資Wl設(shè)置如表4所示。各算法ARPD均值和標(biāo)準(zhǔn)差均值統(tǒng)計結(jié)果如表5所示。由表5中數(shù)據(jù)可以得出，當(dāng)工人處于中等薪資水平時，就ARPD而言，AHGA_IG算法在各規(guī)模上均優(yōu)于其他3種算法，具有較高的求解質(zhì)量。就標(biāo)準(zhǔn)差而言，AHGA_IG算法在大多數(shù)規(guī)模小于其他算法，當(dāng)訂單數(shù)量J=20時，AHGA_GA算法優(yōu)于AHGA_IG算法，但差距較小。AHGA_TS算法依舊在所有算法中標(biāo)準(zhǔn)差最大，具有較差的穩(wěn)定性，AHGA_FOA算法ARPD值遠大于其他算法，具有較差的求解質(zhì)量。綜合分析，AHGA_IG算法在此情形下依舊是綜合性能表現(xiàn)較好的算法。

表4 各級工人工作效率及單位時間薪資表

表5 情形二各算法ARPD均值、標(biāo)準(zhǔn)差(std.)均值統(tǒng)計結(jié)果

3.2.3 情形三：高等薪資水平

在工人處于高等薪資水平時，各等級工人工作效率ηl及單位時間薪資Wl設(shè)置和各算法ARPD均值和標(biāo)準(zhǔn)差均值統(tǒng)計結(jié)果如表6和表7所示。從表7中數(shù)據(jù)可得，3種算法標(biāo)準(zhǔn)差較大，這是由于工人處于高等薪資水平，工人成本增大，導(dǎo)致目標(biāo)值變大，標(biāo)準(zhǔn)差與目標(biāo)值比值平均值為4.06%，處于合理范圍。AHGA_IG算法ARPD和標(biāo)準(zhǔn)差值均小于其他算法，AHGA_TS算法在此情形下標(biāo)準(zhǔn)差和ARPD值優(yōu)于AHGA_GA算法和AHGA_FOA算法，AHGA_FOA在標(biāo)準(zhǔn)差和ARPD方面均表現(xiàn)較差。由此可得，AHGA_IG算法在此情況下仍是求解性能和魯棒性更優(yōu)的算法。

表6 各級工人工作效率及單位時間薪資表

表7 情形三各算法ARPD均值、標(biāo)準(zhǔn)差(std.)均值統(tǒng)計結(jié)果

3.3 結(jié)果分析

以訂單規(guī)模30為例，3種算法在各薪資水平下的收斂情況如圖6所示。AHGA_IG算法在各薪資水平下均收斂最快，并且具有較高的求解質(zhì)量。AHGA_FOA算法也能較快達到收斂狀態(tài)，但其解的質(zhì)量較差，AHGA_GA算法能夠在較快達到收斂狀態(tài)的同時兼顧解的質(zhì)量，AHGA_TS算法則在收斂效果上表現(xiàn)較差。AHGA_IG算法各情形下在求解質(zhì)量、魯棒性均優(yōu)于其他算法，在收斂性上，AHGA_IG算法均能夠較快地達到收斂。因此，認(rèn)為AHGA_IG算法相較于AHGA_TS算法、AHGA_GA算法和AHGA_FOA算法具有更好的求解能力、魯棒性和收斂性，在預(yù)制構(gòu)件生產(chǎn)調(diào)度與工人配置集成優(yōu)化問題上表現(xiàn)更優(yōu)。

現(xiàn)階段各預(yù)制構(gòu)件生產(chǎn)工廠多采用基于經(jīng)驗的啟發(fā)式方式進行工人配置和生產(chǎn)調(diào)度，為驗證AHGA_IG算法與啟發(fā)式方式間求解性能差異，各工人薪資水平下算法改進率如表8所示。由此可得，AHGA_IG在各工人薪資水平下各訂單規(guī)模均相比啟發(fā)式方法求解性能有較大的提升，其中各工人薪資水平分別對應(yīng)貧困地區(qū)、一般地區(qū)和發(fā)達地區(qū)的工人薪資。由此可得，AHGA_IG算法適用于各地區(qū)預(yù)制構(gòu)件生產(chǎn)工廠，對預(yù)制構(gòu)件生產(chǎn)調(diào)度問題與工人配置問題集成優(yōu)化，具有較好的優(yōu)化性能。

表8 各工人薪資水平情形下算法改進率 %

4 結(jié)束語

本文研究了一類預(yù)制構(gòu)件生產(chǎn)調(diào)度與工人配置集成優(yōu)化問題，充分考慮了預(yù)制構(gòu)件生產(chǎn)工藝、工人配置以及資源受限等實際生產(chǎn)特點，以最小化工人成本和拖期懲罰為目標(biāo)，建立了預(yù)制構(gòu)件生產(chǎn)調(diào)度與工人配置集成優(yōu)化數(shù)學(xué)模型，并提出一種有效的混合遺傳—迭代貪婪交替搜索算法。并與AHGA_GA算法和AHGA_TS算法在不同工人薪資水平情況下通過不同數(shù)據(jù)規(guī)模訂單進行了算法性能測試。計算結(jié)果顯示，與其他兩種交替式混合智能優(yōu)化算法相比，AHGA_IG在搜索性能、穩(wěn)定性和收斂性上均具有較好的表現(xiàn)，并且相對于預(yù)制構(gòu)件企業(yè)常用的基于經(jīng)驗的啟發(fā)式方法具有較大改進，平均改進13%以上，有望在實際應(yīng)用中取得顯著的經(jīng)濟效益并改善顧客滿意度。

在預(yù)制生產(chǎn)6道工序中，第1,2,5,6階段主要由人工完成，因此處理時間有一定波動，增加考慮工人配置的不確定處理時間和訂單接收與調(diào)度問題將是下一步研究重點，并以此為目標(biāo)，進一步挖掘問題特征，設(shè)計更高效的求解算法。