鐘宏揚(yáng)，劉建軍，黎英杰，陳慶新

(廣東工業(yè)大學(xué) 廣東省計(jì)算機(jī)集成制造系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006)

作業(yè)車間調(diào)度問(wèn)題 (job shop scheduling problem,JSP) 是一類具有工程應(yīng)用背景的強(qiáng)NP難問(wèn)題，傳統(tǒng)的作業(yè)車間調(diào)度通常假設(shè)加工工件之間完全相互獨(dú)立，加工工件的所有工序完工以后即視為可交付[1]。近年來(lái)，以客戶為導(dǎo)向的多品種小批量生產(chǎn)方式興起，產(chǎn)品的多元化裝配結(jié)構(gòu)使得裝配工序調(diào)度復(fù)雜化，因此裝配作業(yè)車間調(diào)度問(wèn)題 (assembly job shop scheduling problem,AJSP) 也成為JSP問(wèn)題的一類更具現(xiàn)實(shí)意義的拓展研究?jī)?nèi)容[2-4]。

裝配作業(yè)車間包括加工和裝配兩個(gè)階段，工序順序與裝配結(jié)構(gòu)的強(qiáng)關(guān)聯(lián)耦合約束為雙階段的調(diào)度計(jì)劃提出了更多的協(xié)同需求[5]。當(dāng)前AJSP研究大多集中在全局性齊套的裝配，即假定產(chǎn)品的所有零部件齊套后直接進(jìn)行總裝作業(yè)，如文獻(xiàn)[6]是在產(chǎn)品所有關(guān)聯(lián)裝配任務(wù)都完工后，附加一定的裝配工期后即表示產(chǎn)品為完工，并不涉及具體裝配資源的調(diào)度。但實(shí)際生產(chǎn)中產(chǎn)品也存在漸增性齊套的裝配結(jié)構(gòu)，關(guān)聯(lián)零件先通過(guò)部裝組成部件后，待部件齊套后再執(zhí)行總裝[7-8]。產(chǎn)品存在差異化的裝配層次特征，加之多產(chǎn)品并行生產(chǎn)的特點(diǎn)，為裝配資源調(diào)度提出了更多的挑戰(zhàn)。

另一方面，在經(jīng)典的JSP與AJSP問(wèn)題中，加工任務(wù)被視為一個(gè)整體不可拆分。整批流轉(zhuǎn)加工的方式雖然可以減少工序的準(zhǔn)備時(shí)間，但也降低了車間物料運(yùn)輸?shù)牧鲃?dòng)性，增加了訂單在高負(fù)載強(qiáng)度生產(chǎn)環(huán)境下的拖期風(fēng)險(xiǎn)。對(duì)加工任務(wù)進(jìn)行合理批量劃分，可以促使子批交疊并行生產(chǎn)，進(jìn)而提升車間的設(shè)備利用率，縮短生產(chǎn)周期[9-11]。允許對(duì)加工任務(wù)進(jìn)行分批生產(chǎn)與傳輸?shù)膯?wèn)題屬于分批調(diào)度優(yōu)化問(wèn)題[12]。分批調(diào)度涉及批量劃分和排序優(yōu)化兩個(gè)子問(wèn)題，批量劃分對(duì)后續(xù)排序優(yōu)化效果奠定基礎(chǔ)，故而需要全局性較好的算法來(lái)確保分批結(jié)果的優(yōu)度。已有的裝配作業(yè)分批優(yōu)化算法大多數(shù)面向全局性齊套需求[13-14]，在漸增性齊套的生產(chǎn)制約關(guān)系下，經(jīng)典的遺傳編碼與進(jìn)化操作難以適用。本文以最小化產(chǎn)品的拖期成本與庫(kù)存持有成本之和為優(yōu)化目標(biāo)，構(gòu)建一套基于改進(jìn)性遺傳算法與高效作業(yè)分派規(guī)則相耦合的分步式求解框架。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該算法在多層級(jí)裝配作業(yè)車間調(diào)度問(wèn)題的有效性，并評(píng)估與分析所提算法對(duì)不同樹(shù)狀結(jié)構(gòu)產(chǎn)品的調(diào)度性能。

1 問(wèn)題描述

裝配作業(yè)車間所生產(chǎn)的產(chǎn)品根據(jù)客戶要求，在需求數(shù)量、裝配結(jié)構(gòu)與工藝上都有不同程度的差異。如圖1所示，裝配作業(yè)車間的生產(chǎn)包括加工與裝配兩個(gè)階段，故其調(diào)度涉及加工階段與裝配階段的生產(chǎn)資源。各個(gè)裝配層級(jí)部件/組件的裝配工序需要等待直屬關(guān)聯(lián)零部件齊套以后方可執(zhí)行。準(zhǔn)時(shí)交付水平成為衡量MTO (make-to-order) 型企業(yè)競(jìng)爭(zhēng)力的重要指標(biāo)，基于文獻(xiàn)[15]提出的最小化拖期與庫(kù)存持有成本之和的優(yōu)化目標(biāo)，產(chǎn)品的交付性能與車間的庫(kù)存持有成本都受制于其下屬關(guān)聯(lián)任務(wù)加工進(jìn)度的協(xié)同性，而漸增性齊套裝配中的庫(kù)存持有成本主要由裝配工序等待關(guān)聯(lián)零部件齊套的時(shí)間產(chǎn)生。零部件子批完工后會(huì)進(jìn)入半成品庫(kù)存區(qū)，等待其關(guān)聯(lián)任務(wù)都齊套后，才能由庫(kù)存等待區(qū)轉(zhuǎn)入到裝配單元進(jìn)行加工，在此等待關(guān)聯(lián)零部件齊套的期間會(huì)產(chǎn)生相應(yīng)的庫(kù)存持有成本。本文借助分批生產(chǎn)與傳輸技術(shù)，將各層級(jí)的零部件劃分為可以獨(dú)立流轉(zhuǎn)的子批。通過(guò)將子批在加工/裝配資源上交疊并行生產(chǎn)，實(shí)現(xiàn)生產(chǎn)進(jìn)度的協(xié)同。

圖1 多層級(jí)裝配作業(yè)車間簡(jiǎn)圖Figure 1 Diagram of a multi-level assembly job shop

本文所考慮的多層級(jí)裝配作業(yè)車間分批調(diào)度問(wèn)題描述如下：在調(diào)度時(shí)刻，待交付的產(chǎn)品集合為P={Ph|h=1,2,···,p}，對(duì)于任一類產(chǎn)品Ph，其需求批量為DBh，并具有特定的裝配結(jié)構(gòu)。產(chǎn)品Ph需要經(jīng)過(guò)加工階段與裝配階段，加工階段共有a個(gè)加工單元M={Mi|i=1,2,···,a}，而裝配階段有b個(gè)裝配單元A={Ai|i=1,2,···,b}。零部件的加工/裝配工藝路徑因零件類型而異，面臨的優(yōu)化問(wèn)題是對(duì)各類零部件進(jìn)行批量劃分，以確定零部件的分批數(shù)量以及子批的批量大小，再對(duì)分割好的各個(gè)子批進(jìn)行優(yōu)化排序，以最小化庫(kù)存持有成本和拖期成本之和。

在構(gòu)建多層級(jí)裝配作業(yè)車間生產(chǎn)調(diào)度模型前，有以下假設(shè)：1) 在零時(shí)刻，所有零部件分割后的子批信息已知，并均可被選上機(jī)加工；2) 不考慮物料在資源之間的運(yùn)輸時(shí)間；3) 生產(chǎn)過(guò)程中沒(méi)有物料短缺或者機(jī)器故障等異常擾動(dòng)出現(xiàn)；4) 不同類零件子批之間在上機(jī)前的切換需要工序準(zhǔn)備時(shí)間，同類零部件子批連續(xù)加工/裝配不需要工序準(zhǔn)備時(shí)間，工序準(zhǔn)備時(shí)間只與工序相關(guān)而與子批的大小無(wú)關(guān)；5) 每個(gè)工件在任意一臺(tái)機(jī)器上僅加工一道工序；6) 工序一旦開(kāi)工，則不允許終止。

2 模型構(gòu)建

2.1 模型相關(guān)符號(hào)定義

本文所涉及的符號(hào)與參數(shù)定義如表1所示。

表1 符號(hào)與參數(shù)定義Table 1 Definitions of symbols and parameters

2.2 數(shù)學(xué)模型構(gòu)建

裝配作業(yè)車間分批調(diào)度包括批量劃分與子批調(diào)度兩個(gè)決策，批量劃分決策層一定程度上影響子批調(diào)度結(jié)果的優(yōu)劣性。任務(wù)劃分的子批過(guò)少，子批批量過(guò)大則不利于任務(wù)在車間流轉(zhuǎn)，高負(fù)載車間環(huán)境下產(chǎn)品拖期風(fēng)險(xiǎn)隨之增加；反之，任務(wù)劃分的子批過(guò)多，雖然有助于加速任務(wù)交疊并行加工，但造成了因裝夾工具切換而產(chǎn)生的準(zhǔn)備時(shí)間增加，因部分子批提前完工而產(chǎn)生的裝配齊套等待時(shí)間也隨之增加。分批結(jié)果對(duì)因產(chǎn)品拖期而產(chǎn)生的懲罰成本與因裝配齊套等待而產(chǎn)生的庫(kù)存持有成本有深遠(yuǎn)影響，受到文獻(xiàn)[15]所構(gòu)建的數(shù)學(xué)模型啟發(fā)，本節(jié)以最小化所有產(chǎn)品的庫(kù)存成本與拖期成本之和為優(yōu)化目標(biāo)函數(shù)，構(gòu)建了多層級(jí)裝配作業(yè)車間分批調(diào)度模型，具體如下。

其中，式(1) 為本文的目標(biāo)函數(shù)，即最小化所有產(chǎn)品的拖期成本與庫(kù)存持有成本之和，通過(guò)統(tǒng)一量綱的方式將所有產(chǎn)品的拖期成本與庫(kù)存持有成本累加。式 (2) 定義了待交付產(chǎn)品h的生產(chǎn)周期，其等于下屬所有子批最晚完工時(shí)間；式 (3) 為基準(zhǔn)交貨期的設(shè)定，是以關(guān)鍵路徑總工時(shí)與交貨松弛系數(shù)之積；基于式 (3) 所生成的交貨期基準(zhǔn)，式(4) 與式(5) 分別表示交貨期下界與上界；式 (6) 約束了工件子批Lhjs的加工順序先后關(guān)系；式 (7) 則定義了工件子批Lhjs在緊前工序完工后，在緊后工序加工隊(duì)列的排隊(duì)等待時(shí)間約束；式 (8) 表示當(dāng)且僅當(dāng)工件子批的裝夾類型與當(dāng)前加工機(jī)器裝夾類型一致時(shí)，不需要切換夾具等準(zhǔn)備工作，否則需要額外切換夾具的準(zhǔn)備時(shí)間；式 (9) 約束了裝配工序的開(kāi)工時(shí)間不得早于直屬零部件的完工時(shí)間，并且裝配子批的批量不得大于直屬零部件的子批批量；式 (10) 表示產(chǎn)品h需求數(shù)量，下屬零部件批量與各零部件子批量之間的關(guān)系；式 (11) 為工件批次Lhj的分批數(shù)量約束；式 (12) 表示所有零件的子批都可以在零時(shí)刻被選擇上機(jī)；式 (13) 將拖期成本定義為產(chǎn)品h的拖期時(shí)間、需求數(shù)量、產(chǎn)品單位拖期成本之積，式(14) 將產(chǎn)品庫(kù)存持有成本定義為產(chǎn)品h各層級(jí)零部件等待關(guān)聯(lián)零部件完工所產(chǎn)生的裝配等待時(shí)間、批量大小、單位庫(kù)存成本之積；式 (15) 與式 (16) 則表示工件批次Lhj下的各個(gè)子批的加工/裝配工時(shí)與準(zhǔn)備工時(shí)是相同的。

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

3.1 算法求解流程

多層級(jí)裝配作業(yè)車間調(diào)度問(wèn)題涉及批量劃分與調(diào)度兩個(gè)子問(wèn)題，而處理該類問(wèn)題的策略主要有分步優(yōu)化策略和集成優(yōu)化策略[15]。集成優(yōu)化策略是將批量劃分和排序兩個(gè)子問(wèn)題建立聯(lián)合優(yōu)化模型，并構(gòu)建全局優(yōu)化算法進(jìn)行求解。集成優(yōu)化策略可以確保求解質(zhì)量，但過(guò)于低效的求解效率使其在實(shí)際生產(chǎn)中難以在可承受的時(shí)間內(nèi)獲取令用戶滿意的解。故本文采用分步優(yōu)化策略，通過(guò)在計(jì)劃層執(zhí)行任務(wù)分批后，再對(duì)分割后的子批執(zhí)行調(diào)度排序。以遺傳算法為代表的智能算法具有良好的全局搜索能力，但子批調(diào)度問(wèn)題涉及漸增性齊套約束，難以設(shè)計(jì)合適的基因編碼表達(dá)方式以及高效的遺傳迭代動(dòng)作。啟發(fā)式規(guī)則可以相對(duì)直觀快速地反映多層級(jí)裝配產(chǎn)品在生產(chǎn)過(guò)程所涉及的復(fù)雜裝配約束。鑒于此，如流程圖2所示，將遺傳算法應(yīng)用在批量劃分問(wèn)題上以迭代優(yōu)化分批結(jié)果，再基于作業(yè)分派規(guī)則對(duì)生成的分批方案進(jìn)行高效快速地調(diào)度排序，此類混合求解框架可以較大程度地發(fā)揮智能算法與作業(yè)分派規(guī)則的特點(diǎn)與優(yōu)勢(shì)。

圖2 混合求解算法框架流程Figure 2 Flow chart of the hybrid algorithms

3.2 遺傳算法的分批優(yōu)化

遺傳算法 (genetic algorithm,GA) 是一個(gè)被公認(rèn)為具有良好全局并行搜索能力的智能算法，其在作業(yè)車間調(diào)度等相關(guān)拓展問(wèn)題的優(yōu)化求解上被廣泛應(yīng)用。本文將遺傳算法用于優(yōu)化多層級(jí)裝配作業(yè)車間的批量劃分子問(wèn)題，其涉及了各類工件需要拆分的子批數(shù)量以及各子批的批量大小。為此本節(jié)首先設(shè)計(jì)分批優(yōu)化的染色體編碼方式，為充分發(fā)揮遺傳算法的全局搜索能力打下基礎(chǔ)。其次，設(shè)計(jì)了一套交叉變異操作以維持生成子代解的合法性，并提升算法搜索效率。

3.2.1 染色體編碼

本文設(shè)計(jì)了基于實(shí)數(shù)編碼方式的二維數(shù)組式染色體，其中染色體結(jié)構(gòu)的第1列表示的是各類工件被拆分成的子批數(shù)量，后續(xù)的各列依次表示被拆分后的各個(gè)子批的批量，所以一行基因代表了某一類零部件的分批結(jié)果。如圖3所示，一個(gè)待交付數(shù)量為10的單裝配層級(jí)產(chǎn)品，其直屬的4類加工件和一類裝配件需求數(shù)量也為10。圖3所生成分批方案構(gòu)成了一個(gè)5×5維度的數(shù)組，各類工件的分批批數(shù)依次為5、2、4、3、2。值得注意的是，當(dāng)分批后的子批數(shù)量不滿足染色體的最大有效長(zhǎng)度 (產(chǎn)品下屬各類工件的最大分批數(shù)量)，長(zhǎng)度不滿足的部分需要用零進(jìn)行補(bǔ)充，如圖3中第2行的工件被分為2個(gè)批量為5的子批。

圖3 染色體編碼結(jié)構(gòu)示例Figure 3 An example of chromosome coding

3.2.2 交叉與變異操作

為了保證編碼在遺傳迭代過(guò)程中的完整性，設(shè)計(jì)了一套面向裝配作業(yè)車間分批問(wèn)題的交叉和變異操作。如圖4所示，對(duì)于需求數(shù)量為10的單裝配層級(jí)產(chǎn)品，父代1與父代2兩條染色體結(jié)構(gòu)表征其分批的兩套方案。先對(duì)父代1與父代2執(zhí)行交叉操作，將兩條父代染色體中的第5類裝配件的編碼信息進(jìn)行交叉互換后，生成兩個(gè)子代染色體。

圖4 染色體交叉變異操作示例Figure 4 An example of crossover and mutation operation

基于交叉操作階段生成的兩個(gè)子代染色體，分別對(duì)子代1的第2類工件與子代2的第5類工件執(zhí)行變異操作。變異操作作用于染色體編碼第1列的分批信息，將子代1的第2類工件與子代2的第5類工件分批數(shù)量都從2變?yōu)?以后，隨即產(chǎn)生的子批批量也重新生成。交叉變異操作執(zhí)行完成后，再根據(jù)輪盤(pán)賭的方法，基于種群的適應(yīng)度函數(shù)進(jìn)行選擇操作。

3.3 作業(yè)分派式調(diào)度

基于遺傳算法所確定的工件分批方案，采用基于優(yōu)先度的作業(yè)分派規(guī)則對(duì)劃分的子批任務(wù)進(jìn)行調(diào)度，總體流程如圖2所示，詳細(xì)步驟如下。

步驟1待交付產(chǎn)品下屬的所有任務(wù)分為3個(gè)集合，待完工任務(wù)集合對(duì)應(yīng)的是各臺(tái)加工/裝配單元中的等待隊(duì)列任務(wù)集合，表示子批任務(wù)還有未完成的加工/裝配工序；裝配等待任務(wù)集合對(duì)應(yīng)的是零部件已經(jīng)完成所有工序，但需要等待關(guān)聯(lián)任務(wù)完工齊套后以執(zhí)行更高層級(jí)的裝配；可交付隊(duì)列則表示產(chǎn)品已經(jīng)完成總裝可以交付用戶。

步驟2根據(jù)相應(yīng)的作業(yè)分派規(guī)則，依次安排待完工任務(wù)集合的子批任務(wù)執(zhí)行加工/裝配任務(wù)。

步驟3若子批任務(wù)完成當(dāng)前加工/裝配工序后仍未完工，則繼續(xù)執(zhí)行步驟2。如果子批任務(wù)完成了加工/裝配階段的所有工序，則將其狀態(tài)轉(zhuǎn)為完工并轉(zhuǎn)入裝配等待任務(wù)集合并執(zhí)行步驟4。

步驟4判斷子批任務(wù)所處的裝配層級(jí)，如果子批任務(wù)未到達(dá)最高裝配層級(jí)，則執(zhí)行步驟5；若子批任務(wù)已經(jīng)達(dá)到產(chǎn)品總裝層,則將子批任務(wù)轉(zhuǎn)移到可交付隊(duì)列。

步驟5判斷子批任務(wù)同屬裝配層級(jí)的其他關(guān)聯(lián)任務(wù)是否已經(jīng)齊套，且各類關(guān)聯(lián)工件子批的最小批量是否滿足上一層及裝配子批的批量開(kāi)工需求，若滿足則將子批任務(wù)轉(zhuǎn)入待完工任務(wù)集合，否則保留在裝配等待隊(duì)列中等待關(guān)聯(lián)任務(wù)完工。

多層級(jí)裝配作業(yè)車間調(diào)度中協(xié)同關(guān)聯(lián)批次加工進(jìn)度存在兩個(gè)難點(diǎn)：1) 差異化的工藝路徑長(zhǎng)度以及工序工時(shí)使得部件直屬零件的進(jìn)度難以協(xié)同；2) 部件下屬關(guān)聯(lián)零部件的最小完工批量要滿足其裝配工序的批量開(kāi)工需求。鑒于此，高效的作業(yè)分派規(guī)則可以快速地基于分批結(jié)果生成調(diào)度方案。根據(jù)裝配作業(yè)車間調(diào)度相關(guān)文獻(xiàn)[6]，已有的裝配作業(yè)調(diào)度規(guī)則通常按以下4個(gè)典型維度進(jìn)行設(shè)計(jì)。

1) 流水時(shí)間類的規(guī)則：與加工任務(wù)工序工時(shí)，任務(wù)工藝路徑累計(jì)工時(shí)等參數(shù)相關(guān)；

2) 訂單層協(xié)同的規(guī)則：與訂單下屬各任務(wù)的加工進(jìn)度相關(guān)；

3) 任務(wù)層協(xié)同規(guī)則：與任務(wù)下屬未完工工序、工時(shí)等參數(shù)相關(guān)；

4) 交貨期設(shè)置規(guī)則：與訂單、工序交貨期等參數(shù)相關(guān)。

表2為相關(guān)文獻(xiàn)所涉及的裝配作業(yè)車間分派規(guī)則。

表2 裝配作業(yè)車間作業(yè)分派規(guī)則Table 2 Priority dispatching rules in assembly job shops

其中，RANKhjsk為子批任務(wù)的加工優(yōu)先級(jí)；UTh為Ph工件類型 數(shù)；UShj為L(zhǎng)hj未完工子批數(shù)；UOhjs為L(zhǎng)hjs未完工工序數(shù)；RM為未完工子批任務(wù)。

4 仿真實(shí)驗(yàn)

4.1 仿真參數(shù)與實(shí)驗(yàn)設(shè)計(jì)

裝配作業(yè)車間的產(chǎn)品BOM結(jié)構(gòu)特征與其裝配層級(jí)數(shù)量、各層級(jí)的直屬零部件數(shù)量緊密相關(guān)，分批調(diào)度對(duì)差異化產(chǎn)品產(chǎn)生的協(xié)同性能也會(huì)有所不同。文獻(xiàn)[16]考慮了3種特點(diǎn)鮮明裝配結(jié)構(gòu)的產(chǎn)品。1) Flat型產(chǎn)品。是由多個(gè)零件直接裝配而成的單層級(jí)樹(shù)形結(jié)構(gòu)，僅僅需滿足全局性裝配齊套，見(jiàn)圖5 (a)。2) Tall型產(chǎn)品。屬于多層級(jí)樹(shù)形結(jié)構(gòu)，每一層級(jí)僅有兩個(gè)直屬零部件裝配而成，屬于漸增性齊套，見(jiàn)圖5 (b)。3) Complex型產(chǎn)品。綜合了前兩種類型產(chǎn)品的特征，既屬于多層級(jí)樹(shù)狀結(jié)構(gòu)，每層級(jí)的直屬零部件也不少于兩個(gè)，見(jiàn)圖5 (c)。本文的實(shí)驗(yàn)?zāi)康闹痪驮谔骄克岢龅姆峙{(diào)度算法在圖5所示9種產(chǎn)品結(jié)構(gòu)上的性能差異。

圖5 產(chǎn)品樹(shù)狀結(jié)構(gòu)Figure 5 Tree structures of assembly products

分批策略決定了批量劃分問(wèn)題的解空間，是影響分批調(diào)度算法性能的重要因素。常用的分批策略有等量分批，一致分批與可變分批[9]。其中，等量分批因?yàn)槠渲庇^、計(jì)算效率高的特點(diǎn)被應(yīng)用在批量流相關(guān)研究中[17]。與此同時(shí)，等量分批也被認(rèn)作是可變分批的一種特殊形式，本文的實(shí)驗(yàn)?zāi)康闹驮谟谘芯靠勺兎峙呗韵啾鹊攘糠峙呗允欠窨梢蕴岣呋旌纤惴ǖ恼{(diào)度性能。

本文所考慮的優(yōu)化目標(biāo)與交貨期設(shè)置緊密相關(guān)，裝配作業(yè)車間的交貨期設(shè)置通常是參照經(jīng)典的關(guān)鍵路徑法，其中涉及交貨期強(qiáng)度系數(shù)。本文將探究在不同交貨期強(qiáng)度下，評(píng)估分批調(diào)度算法在各類裝配樹(shù)形結(jié)構(gòu)產(chǎn)品下的性能變化，并以此為設(shè)定交貨期強(qiáng)度基準(zhǔn)。

按照前文所述的實(shí)驗(yàn)動(dòng)機(jī)，本文的仿真實(shí)驗(yàn)將如下推進(jìn)：首先，在不同交貨期強(qiáng)度下，分析所提出分批優(yōu)化調(diào)度算法在各類產(chǎn)品下的性能變化，并設(shè)定交貨期基準(zhǔn)；其次，在給定的交貨期設(shè)置下，分析不同作業(yè)分派規(guī)則在不分批策略 (none sublot,NS) 對(duì)各類樹(shù)形結(jié)構(gòu)產(chǎn)品的性能影響；最后，分析比較等量分批 (equal sublot,ES) 與可變分批 (variable sublot,VS) 兩種策略與作業(yè)分派規(guī)則在各類樹(shù)形結(jié)構(gòu)產(chǎn)品下的耦合性能。

如表3所示的仿真實(shí)驗(yàn)所涉及參數(shù)是基于文獻(xiàn)[15]而來(lái)，為避免實(shí)驗(yàn)中存在過(guò)多自變量，本文將所考慮的9種樹(shù)形結(jié)構(gòu)產(chǎn)品按照其結(jié)構(gòu)特征分為Flat、Tall、Complex 3類依次進(jìn)行調(diào)度。

表3 實(shí)驗(yàn)參數(shù)設(shè)置Table 3 Parameter settings of experiments

4.2 實(shí)驗(yàn)結(jié)果與分析

本文所構(gòu)建的多層級(jí)裝配作業(yè)車間實(shí)驗(yàn)平臺(tái)基于Matlab2016b開(kāi)發(fā)，在同一種實(shí)驗(yàn)參數(shù)組合下取10次實(shí)驗(yàn)觀察值的均值作為最終的實(shí)驗(yàn)結(jié)果。為確保遺傳算法的收斂性與穩(wěn)定性，本文首先開(kāi)展一系列預(yù)實(shí)驗(yàn)以確定遺傳算法相關(guān)的重要參數(shù)：種群大小為100條染色體，迭代終止條件為最大遺傳代數(shù)100代，交叉概率為0.7，變異概率為0.05，代溝設(shè)置為0.9。為更好地分析分批調(diào)度算法在不同實(shí)驗(yàn)參數(shù)下的性能變化，除去優(yōu)化目標(biāo)Obj以外，還統(tǒng)計(jì)了拖期總成本CE、庫(kù)存總持有成本CL和所有產(chǎn)品完工后的最大完成時(shí)間Ctmax作為觀察指標(biāo)。

4.2.1 算法性能受交貨期強(qiáng)度設(shè)置的影響

本文所考慮的實(shí)驗(yàn)變量因素較多，出于交貨期設(shè)置對(duì)優(yōu)化目標(biāo)有較大影響考慮，第一階段的實(shí)驗(yàn)先在3種分批策略以及各類樹(shù)形產(chǎn)品結(jié)構(gòu)下，分析算法性能受交貨期強(qiáng)度設(shè)置的影響?；旌纤惴ㄖ胁捎肙DD規(guī)則以控制變量，通過(guò)預(yù)實(shí)驗(yàn)，交貨期松弛系數(shù)λ值1.15、1.35、1.55分別代表3種交貨期強(qiáng)度(緊、中、松)。

圖6表現(xiàn)了3種策略下算法的優(yōu)化目標(biāo)受到交貨期設(shè)置而產(chǎn)生的性能變化。如圖6 (a) 所示，在NS策略下，算法在Tall型結(jié)構(gòu)的產(chǎn)品調(diào)度結(jié)果最差，Complex其次，F(xiàn)lat型最好。在同等交貨期強(qiáng)度下，Tall型產(chǎn)品的結(jié)構(gòu)特征是裝配層級(jí)較多，這不僅容易造成相對(duì)高的產(chǎn)品拖期風(fēng)險(xiǎn)，更會(huì)產(chǎn)生因漸增性齊套裝配帶來(lái)的庫(kù)存持有成本增長(zhǎng)。隨著交貨期強(qiáng)度逐漸變低，目標(biāo)函數(shù)會(huì)出現(xiàn)拐點(diǎn)，原因在于高交付壓力下容易產(chǎn)生高額的拖期懲罰成本，而低交付壓力則又容易因交付時(shí)間未到而產(chǎn)生額外的庫(kù)存持有成本。由此可見(jiàn)，交貨期強(qiáng)度的合理設(shè)置對(duì)優(yōu)化目標(biāo)的影響。

圖6 交貨期強(qiáng)度設(shè)置對(duì)算法的影響Figure 6 The influences of delively time intensiry on algorithms

圖6 (b) 和 (c) 分別為等量分批與可變分批策略下目標(biāo)函數(shù)隨交貨期變化，可以明顯發(fā)現(xiàn)3類產(chǎn)品結(jié)構(gòu)在同等交貨期強(qiáng)度下，分批策略對(duì)優(yōu)化目標(biāo)有不同程度的性能提升。不同之處在于，優(yōu)化目標(biāo)是隨著交貨期強(qiáng)度下降而劣化，這一方面說(shuō)明了相比低交貨期強(qiáng)度帶來(lái)的低拖期懲罰，分批策略下可能會(huì)造成更多因裝配等待而產(chǎn)生的庫(kù)存持有成本。另一方面，過(guò)寬的交貨期強(qiáng)度也使得過(guò)早完工的產(chǎn)品無(wú)法交付而產(chǎn)生額外的庫(kù)存持有成本。

4.2.2 不分批策略下調(diào)度規(guī)則的性能分析

根據(jù)前一階段的交貨期設(shè)置的實(shí)驗(yàn)結(jié)果，本節(jié)將進(jìn)一步分析作業(yè)分派規(guī)則的選擇對(duì)混合算法的性能影響。為控制變量以及屏蔽過(guò)多實(shí)驗(yàn)因素干擾，本階段采用NS策略，交貨期系數(shù)λ設(shè)置為1.35。因?yàn)镹S策略下，前階段實(shí)驗(yàn)結(jié)果顯示該交貨期設(shè)置可以獲取優(yōu)化目標(biāo)的臨界點(diǎn)。

本階段將對(duì)8種作業(yè)分派規(guī)則下的混合算法，在3種裝配結(jié)構(gòu)下分析其優(yōu)化目標(biāo)、拖期成本、庫(kù)存持有成本以及Ctmax等多個(gè)指標(biāo)。實(shí)驗(yàn)結(jié)果如表4～表6所示，可以得出以下3個(gè)初步結(jié)論。

表4 Flat型產(chǎn)品在NS策略下的調(diào)度結(jié)果Table 4 Scheduling results of flat structure products under NS strategy

表5 Tall型產(chǎn)品在NS策略下的調(diào)度結(jié)果Table 5 Scheduling results of tall structure products under NS strategy

表6 Complex型產(chǎn)品在NS策略下的調(diào)度結(jié)果Table 6 Scheduling results of complex structure products under NS strategy

1) 基于交貨期屬性的作業(yè)分派規(guī)則 (EDD、ODD、MST) 在各類產(chǎn)品結(jié)構(gòu)下都表現(xiàn)出了較好的性能，在Flat與Complex型產(chǎn)品下，交貨期類的規(guī)則優(yōu)勢(shì)非常明顯。

2) Flat型產(chǎn)品下，ODD規(guī)則性能最優(yōu)，原因在于Flat型產(chǎn)品屬于全局性齊套，面向工序交貨期的規(guī)則可以有效引導(dǎo)關(guān)聯(lián)零部件在單層裝配結(jié)構(gòu)下的進(jìn)度協(xié)同性；而Tall型產(chǎn)品結(jié)構(gòu)下EDD規(guī)則的性能好于ODD規(guī)則，因?yàn)榻回浧谠O(shè)置考慮了裝配工序、裝配層級(jí)數(shù)等因素，產(chǎn)品的交貨期差異比較明顯。EDD規(guī)則可以有效協(xié)同某一產(chǎn)品下屬所有零部件的關(guān)聯(lián)任務(wù)進(jìn)度，因其賦予下屬零部件相同優(yōu)先級(jí)；最后在Complex型產(chǎn)品下，MST規(guī)則通過(guò)協(xié)調(diào)交貨期與總工時(shí)之間的進(jìn)度來(lái)設(shè)置不同程度的優(yōu)先級(jí)，從而保證良好的進(jìn)度協(xié)同性。

3) 在3種樹(shù)形結(jié)構(gòu)的產(chǎn)品調(diào)度中，TWKR規(guī)則都取得了EDD規(guī)則相同的性能，因?yàn)檫@兩種規(guī)則都是面向訂單層的，其決定了下屬的所有關(guān)聯(lián)零部件加工優(yōu)先級(jí)都一致，另外交貨期設(shè)置也跟累計(jì)加工與裝配工時(shí)相關(guān)，所以獲得相同的調(diào)度性能也符合預(yù)期。

4.2.3 分批策略下作業(yè)分派規(guī)則適應(yīng)性分析

前一組實(shí)驗(yàn)初步分析了NS策略下不同分派規(guī)則的調(diào)度性能，接下來(lái)要對(duì)作業(yè)分派規(guī)則在等量分批策略與可變分批策略下的性能進(jìn)行產(chǎn)品結(jié)構(gòu)的適應(yīng)性分析，圖7為3種樹(shù)形結(jié)構(gòu)下作業(yè)分派規(guī)則與兩種分批策略的耦合調(diào)度性能比較。

圖7 分批策略與調(diào)度規(guī)則在不同樹(shù)形結(jié)構(gòu)產(chǎn)品下的耦合性能比較Figure 7 Comparison of coupling performance between lot-splitting strategies and priority dispatching rules under different tree-structure products

對(duì)各組實(shí)驗(yàn)結(jié)果進(jìn)行初步分析可以得到如下結(jié)論。

1) 分批策略下，各個(gè)作業(yè)分派規(guī)則的性能相比NS策略都有顯著提升。在分批策略的選擇上，ES策略在絕大多數(shù)的場(chǎng)景下都好過(guò)VS策略，原因在于ES策略產(chǎn)生的子批數(shù)量以及批量大小更加均衡，一定程度上可以促進(jìn)關(guān)聯(lián)任務(wù)之間的進(jìn)度協(xié)同性。例如在圖7 (c2)中，在Tall型產(chǎn)品下ES策略的庫(kù)存持有成本要明顯優(yōu)于VS策略。雖然ES策略的分批結(jié)果理論上是VS策略分批結(jié)果的子集，但在限定的迭代優(yōu)化條件下，VS策略僅能在部分場(chǎng)景中達(dá)到ES策略的分批效果，故而會(huì)出現(xiàn)兩種分批策略性能差異不大的現(xiàn)象。

2) 在ES與VS策略下，基于交貨期的作業(yè)分派規(guī)則ODD、EDD、MST在3種產(chǎn)品的優(yōu)化目標(biāo)上都有良好的調(diào)度性能。這延續(xù)了NS策略下的作業(yè)分派規(guī)則性能特征，一定程度上說(shuō)明了作業(yè)分派規(guī)則的效力在分批策略下得到了良好的繼承。

3) 如圖7 (a1) 所示，在Flat型的產(chǎn)品下，基于ES分批策略的IR規(guī)則在目標(biāo)函數(shù)值上表現(xiàn)最佳。因?yàn)镕lat型產(chǎn)品屬于全局性齊套，下屬任務(wù)的協(xié)同性更多取決于關(guān)聯(lián)任務(wù)未完工的工序數(shù)量差異。在等量分批策略下，IR規(guī)則可以很好地處理關(guān)聯(lián)任務(wù)的加工進(jìn)度協(xié)同。如圖7 (a2) 所示，在Tall型產(chǎn)品下，基于ES策略的SPT規(guī)則可以獲得最佳的目標(biāo)函數(shù)值。Tall型產(chǎn)品因?yàn)樯婕暗难b配層級(jí)較多，而每一層級(jí)的直屬裝配件類型較少。SPT規(guī)則可以加速批量較小的子批任務(wù)的流轉(zhuǎn)，進(jìn)而減少裝配等待時(shí)間，所以庫(kù)存持有成本有很大改善。如圖7 (a3) 所示，在Complex型產(chǎn)品中，基于ES策略的ODD規(guī)則在目標(biāo)函數(shù)值上表現(xiàn)最佳。Complex型產(chǎn)品具有較多的裝配層級(jí)且每一層級(jí)的直屬裝配件也較多，加之零部件具有差異化的加工/裝配工序與工時(shí)，ODD規(guī)則基于訂單交貨期生成零部件在加工/裝配階段的工序交貨期，可以作為各層級(jí)關(guān)聯(lián)零部件生產(chǎn)/裝配進(jìn)度協(xié)同的基準(zhǔn)有效降低庫(kù)存持有成本 (見(jiàn)圖7 (c3))，進(jìn)而取得更佳的目標(biāo)函數(shù)值。

5 結(jié)語(yǔ)

本文以多層級(jí)裝配作業(yè)車間分批調(diào)度問(wèn)題作為研究背景，構(gòu)建了以最小化拖期成本與庫(kù)存持有成本之和為目標(biāo)的調(diào)度模型，提出了基于遺傳算法與作業(yè)分派規(guī)則的混合求解算法，利用遺傳算法出色的全局搜索能力保證分批問(wèn)題的求解優(yōu)度，再利用作業(yè)分派規(guī)則對(duì)分批結(jié)果快速生成調(diào)度計(jì)劃。鑒于交貨期、分批策略以及作業(yè)分派的選擇對(duì)混合求解算法存在一定的影響，設(shè)計(jì)了漸進(jìn)型的仿真實(shí)驗(yàn)進(jìn)行評(píng)估分析。實(shí)驗(yàn)結(jié)果表明，1) 給定交貨期強(qiáng)度下，產(chǎn)品裝配層級(jí)越多，產(chǎn)生的裝配齊套等待時(shí)間越長(zhǎng)，進(jìn)而導(dǎo)致庫(kù)存持有成本劇增，分批調(diào)度算法在目標(biāo)函數(shù)上呈明顯劣化趨勢(shì)。2) 分批調(diào)度可以使批量小的子批任務(wù)有較好的流動(dòng)性，促進(jìn)各層級(jí)關(guān)聯(lián)零部件的加工協(xié)同，降低裝配齊套等待產(chǎn)生的庫(kù)存持有成本。3) 在給定迭代優(yōu)化條件下，等量分批策略可以有效降低庫(kù)存持有成本，故而可以獲得比可變分批策略更為可觀的優(yōu)化目標(biāo)值。4) 分批調(diào)度的混合求解算法需要考慮產(chǎn)品的結(jié)構(gòu)特征，進(jìn)而選擇合適的作業(yè)分派規(guī)則。

針對(duì)本文所考慮因素的不足，未來(lái)將從以下兩個(gè)方面進(jìn)行研究：1) 建立更為全面的制造成本計(jì)算體系，將在制品成本、準(zhǔn)備時(shí)間成本和轉(zhuǎn)運(yùn)成本考慮到優(yōu)化目標(biāo)，從而使模型更為貼合實(shí)際；2) 將子批傳輸策略引入分批調(diào)度模型，進(jìn)而對(duì)生產(chǎn)的流動(dòng)性進(jìn)一步改善。