多層級裝配作業(yè)車間分批調度算法設計與分析

鐘宏揚，劉建軍，黎英杰，陳慶新

(廣東工業(yè)大學 廣東省計算機集成制造系統(tǒng)重點實驗室，廣東 廣州 510006)

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

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

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

1 問題描述

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

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

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

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

2 模型構建

2.1 模型相關符號定義

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

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

2.2 數(shù)學模型構建

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

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

3 算法設計

3.1 算法求解流程

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

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

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

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

3.2.1 染色體編碼

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

圖3 染色體編碼結構示例Figure 3 An example of chromosome coding

3.2.2 交叉與變異操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中，RANKhjsk為子批任務的加工優(yōu)先級；UTh為Ph工件類型 數(shù)；UShj為Lhj未完工子批數(shù)；UOhjs為Lhjs未完工工序數(shù)；RM為未完工子批任務。

4 仿真實驗

4.1 仿真參數(shù)與實驗設計

裝配作業(yè)車間的產(chǎn)品BOM結構特征與其裝配層級數(shù)量、各層級的直屬零部件數(shù)量緊密相關，分批調度對差異化產(chǎn)品產(chǎn)生的協(xié)同性能也會有所不同。文獻[16]考慮了3種特點鮮明裝配結構的產(chǎn)品。1) Flat型產(chǎn)品。是由多個零件直接裝配而成的單層級樹形結構，僅僅需滿足全局性裝配齊套，見圖5 (a)。2) Tall型產(chǎn)品。屬于多層級樹形結構，每一層級僅有兩個直屬零部件裝配而成，屬于漸增性齊套，見圖5 (b)。3) Complex型產(chǎn)品。綜合了前兩種類型產(chǎn)品的特征，既屬于多層級樹狀結構，每層級的直屬零部件也不少于兩個，見圖5 (c)。本文的實驗目的之一就在探究所提出的分批調度算法在圖5所示9種產(chǎn)品結構上的性能差異。

圖5 產(chǎn)品樹狀結構Figure 5 Tree structures of assembly products

分批策略決定了批量劃分問題的解空間，是影響分批調度算法性能的重要因素。常用的分批策略有等量分批，一致分批與可變分批[9]。其中，等量分批因為其直觀、計算效率高的特點被應用在批量流相關研究中[17]。與此同時，等量分批也被認作是可變分批的一種特殊形式，本文的實驗目的之二就在于研究可變分批策略相比等量分批策略是否可以提高混合算法的調度性能。

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

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

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

表3 實驗參數(shù)設置Table 3 Parameter settings of experiments

4.2 實驗結果與分析

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

4.2.1 算法性能受交貨期強度設置的影響

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

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

圖6 交貨期強度設置對算法的影響Figure 6 The influences of delively time intensiry on algorithms

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

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

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

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

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

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

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

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

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

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

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

前一組實驗初步分析了NS策略下不同分派規(guī)則的調度性能，接下來要對作業(yè)分派規(guī)則在等量分批策略與可變分批策略下的性能進行產(chǎn)品結構的適應性分析，圖7為3種樹形結構下作業(yè)分派規(guī)則與兩種分批策略的耦合調度性能比較。

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

對各組實驗結果進行初步分析可以得到如下結論。

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

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

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

5 結語

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

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