基于多層編碼優化算法的汽車生產物流調度

郭 躍，衛 丹，鄭晨櫻

（1.寧波工程學院，浙江 寧波 315211；2.長安大學，陜西 西安 710064）

1 引言

中國物流與采購聯合會發布的《中國汽車物流發展報告(2018)》[1]展現了中國對汽車生產物流行業的重視。汽車生產物流行業的核心問題是物流調度的問題，為提高汽車制造企業的核心競爭力，企業必須充分利用資源，并設置合理的生產調度以確保交付時間、降低生產成本、提高設備利用率。所以，良好的生產物流調度系統是提高生產效率、增加經濟效益的一個重要構成要素，有效的物流調度優化算法可以減少商業周轉時間、提高產量、降低庫存，達到最低生產成本的目的。因此調度優化算法是否有效，對于汽車生產企業有著重要影響，故該研究具有重要的現實意義。

2 國內外研究現狀

目前對于汽車制造業的研究，學術界已有較為詳盡的論述，對于汽車生產的物流調度以及關于各種路徑優化算法的研究，近年來也有許多學者從不同的角度進行探討和實證研究，主要觀點如下：

2.1 汽車制造業與生產物流之間的聯系

全球汽車制造業經過不斷的革新和發展，目前已經進入成熟期，成為世界上規模最大的產業之一。由于汽車制造業的產業鏈長、覆蓋面廣、綜合性強、技術要求高、附加值高，在全球主要工業國家的產業結構中占據重要地位。

Gabriela Slusariuc[2]認為汽車行業現在是世界上最大的加工生產行業。汽車工業不僅是能源和原材料的巨大消費國，也是一個巨大的就業來源。Dario Dunkovic和Goran Jukic[3]在分析現代生產物流變化的起源時，考慮到這些變化是由供應鏈末端的業務供應商關系模式的發展所造成的，為了縮短交貨期，預計生產商越來越多地根據市場需求調整生產動態和產能。周維[4]提出在汽車制造業企業各項生產要素成本逐年上漲、競爭環境壓力增大、資源配置有限等眾多因素的影響下，汽車制造企業所面臨的挑戰不斷增加，因此汽車制造業轉型和升級并進一步提升企業的核心競爭力變成了一項艱巨而緊迫的任務。

汽車制造業經歷了單件生產、大量生產、精益生產和模塊化生產的發展過程。20 世紀90 年代，隨著汽車制造業模塊化時代的到來，加強汽車生產物流成為增強企業核心競爭力的關鍵因素。通過對汽車制造業的現狀分析，可以看到生產制造與物流系統的關系如同人體中血液循環系統與內臟器官的關系一樣，物流系統是生產制造各環節組成有機整體的紐帶，又是生產過程維持有序發展的基礎?，F代制造企業的生產物流具體是指工廠中從支持生產活動所需要的原材料進廠管理開始，經存儲、裝配、加工、包裝，直至成品出廠這一整個過程的物料流動及與之有關的管理活動，生產物流擔負運輸、儲存、裝卸物流等任務。由于傳統的生產物流設備落后，物流信息管理分散、不準確、傳送速度慢，落后的生產物流將會牽制生產的高速發展。生產制造系統規模不斷擴大、生產的柔性化水平和自動化水平日益提高，要求生產物流也要相應地發展，使之與現代生產制造系統相適應。

近年來國內學者對生產物流也有了大量的研究。龔波[5]把Petri網和計算機仿真技術結合起來，論證了計算機仿真和Petri網技術在生產物流研究中的可行性和優勢，研究了聯合使用Petri 網和計算機仿真，對企業生產物流系統進行優化的方法。岳衛宏[6]運用粒子群算法，探討了某造船企業分段生產過程中的資源合理配置問題，以平面分段流水線為例，利用SIMIO仿真工具，對平面分段的生產流程進行仿真，認為將先進的生產管理模式引入造船企業的生產物流管理，可實現流程的優化和資源的合理配置。朱華炳[7]采用基本Petri網對制造物流系統各個子系統進行建模，提出了面向對象的著色賦時Petri網(OCTPN)的物流系統建模方法，同時對制造加工及物流系統進行集成建模,建立了包含制造加工系統和物流系統的層次化模型，并就汽車后橋車間物流系統規劃的實例基于OCTPN方法進行建模和分析，采用E-Factory、Witness軟件進行計算機輔助建模和仿真，對汽車后橋車間生產物流系統進行了設計與優化。

2.2 汽車生產物流算法問題的研究

結合算法對物流調度進行優化的研究在國內外已有建樹。Sakawa等[8]從個體間相似度著手，完成了一種算法，將模糊生產周期和出貨時間進行多目標調度。華山[9]在研究AGENT－生產調度系統時，結合螞蟻算法對JSSP問題進行了仿真優化。吳衛忠等[10]利用多目標優化法求解多目標混合流水車間調度問題。Lei等[11]利用粒子群優化算法求解作業車間調度問題，并將調度問題有效轉化為連續優化的策略，提出帕累托存檔PSO 優化算法。Ju 等[12]提出建立多目標優化調度模型，批量生產優化調度策略，將多種PSO 搜索的優點、遺傳算法的優點進行整合，得出自旋性PSO 搜索的多種群混合算法，達到高效率和高質量的目的。潘勝[13]基于準時化模式的生產理念，研究考慮機器準備時間的兩階段生產流水線物流的工件最佳排序問題，以最小化最大拖期和提前期為目標函數，提出了一種變鄰域遺傳搜索算法。

有許多學者對生產物流遺傳算法進行了更加深入的研究。Falkenauer和Bouffouix[14]結合遺傳算法進行編碼，編碼時還使用了交叉算子，利用函數法對物流配送大、中、小型生產物流調度優化模型進行分析，得到最優調度。Jain和Eimaraghy[15]在研究靈活性制造系統中應用了遺傳算法，并得到了較好的生產物流調度優化結果。Esquivel[16]等在流水車間和單元制造系統中使用遺傳算法解決調度問題，實現了最高效率完工的目的。王成堯[17]等在研究E/T 調度問題時，應用模糊生產時間法、遺傳算法，指出遺傳算子與調度優化結果的最優性相關聯。王凌[18]等在研究混沌優化法時結合遺傳算法，使得混沌優化法有了進一步的改進。林博[19]在遺傳算法的基礎上,提出了改進遺傳算法,主要針對選擇和交叉兩個部分進行了改進，并通過一個物流配送車輛路徑問題的實例，用改進遺傳算法求解,進行MATLAB 編程仿真，得到了較為理想的效果。支姝[20]采用自然數編碼的方法，初始群體的生成采用混合方式，即部分隨機生成、部分根據初始解生成，選擇策略采用輪盤賭選擇法和截斷選擇法相結合的方法,用改進的邊重組法代替常用的PMX、OX、CX交叉法。根據設定的終止條件，最終取得滿意解。最后，通過C++實現了算法，用Solomon 測試數據里C101 中25 個客戶集的數據進行驗證，并與不同算法所得解進行對比，其求解結果和計算時間都有明顯改進。所得結果在基于遺傳算法求解城市物流配送車輛路徑問題領域和物流系統的開發中具有一定的參考價值。

2.3 文獻評述

上述文獻主要研究了汽車制造業生產物流的特征與現狀以及生產物流與汽車制造業之間存在的緊密聯系，提出傳統汽車制造業的轉型與升級已經迫在眉睫，應重視發展汽車制造業生產物流，使之與現代生產制造系統相適應的觀點。對于汽車生產物流算法的研究，主要介紹了國內外運用算法改進物流調度的研究，但發現對于使用算法改進汽車制造業物流調度的實證研究還比較缺乏，有必要緊密結合我國汽車制造業特點并運用算法加強物流調度的實證研究，通過算法優化解決汽車生產物流調度中存在的一些問題。而本文所提出的多層編碼優化算法便是基于遺傳算法，在遺傳算法的基礎上進行創新和改進。多層編碼優化算法的數學模型采用遺傳算法進行計算并在遺傳算法的基礎上運用了雙層編碼方法設計了一種交叉方法，改進了遺傳算法的執行流程，有一定的創新性。

3 數學建模

3.1 汽車制造業生產物流特點

隨著汽車制造業的信息化程度加深，汽車制造工廠自動化物流不斷創新。汽車制造業生產物流作為汽車制造的關鍵環節，對其成本控制和效益提高不可忽視。一般的汽車制造工廠均包括倉儲、短駁、揀貨、上線等操作。根據文獻[21-22]，可以得出汽車制造業生產物流的定義：汽車制造業生產物流就是把要增值的金屬原材料以最短的時間、最小的成本完成從供應端到需求端的實體流動過程。

汽車生產物流過程中，存在零部件供應商、入廠檢驗、倉庫和生產車間三個重要環境。零部件由零部件供應商整裝發運送到整車廠，在入廠檢查處進行卸貨，并對零部件的數量、質量以及批次和收貨單進行核對，核對無誤后運到倉庫進行存儲。倉庫根據先到期先出庫的原則，將收到的零部件送到適當的庫位上[23]。同時，將生產現場的空箱裝車后運回零部件供應商，從而形成了一個閉環，整個過程如圖1所示。這一環節的主要任務是如何在工作流暢的前提下降低成本。

圖1 汽車生產物流過程

汽車生產物流與其他生產物流相同，也與整個企業生產過程緊密相連。只有合理的組織生產物流活動才能夠發揮出最大的生產能力，否則再好的生產設備也不能順利的完成生產。汽車制造企業的生產活動主要是以裝配式生產為主，但其不同于其他類型企業的生產模式，其生產過程裝配流程長且工序繁多，故其生產物流有以下基本要求：

（1）連續性。汽車制造企業的生產連續進行，每道工序都按照生產工藝提前安排好，需要實現零部件在恰當的時間出現在恰當的地點，不延遲也不提前實現供貨。

（2）平衡性。汽車制造企業生產時一般都需要裝配半成品，每個半成品都需要多種零部件進行組合。所以在裝配生產時，需要將需要的零部件合理分配在對應工序上，因此需要各支流平行移動。

（3）節奏性。汽車生產物流各個流程是一定的，一般工序間不能跳躍進行。保證生產過程的節奏性是指在生產的各個階段，從零部件出庫到成品車入庫，要求在相同的時間間隔內，生產大致相同數量的部件或成品。

3.2 數學模型設計

汽車生產物流的調度直接影響汽車生產的進度和訂單的響應速度。當客戶訂單對一些工件需求較為集中時，就會造成生產線的堵塞甚至停工。針對如何合理分配生產設備、提高訂單的響應速度，本文設計了根據工序數、耗費時間及需求量提供優化的車間調度決策功能。

車間生產線可以描述為：有n個工作任務需要在m臺設備上生產，Oij表示工件i的第j道工序。每個工件的工序一定且已知，工序j在不同機器上加工，加工時間不同。除了操作內容的限制，生產車間生產線的加工過程還應滿足以下要求：

（1）一臺機器在一個時間點能且只能處理一個任務；

（2）在加工過程中，工件能且只能被一個機器加工；

（3）所有的工作都是同等優先級的；

（4）工序與工序之間轉移時間被忽略，僅運算加工時間；

（5）每道工序在不同機器上處理時間已知，且不變。

車間調度優化的任務是合理安排處理順序，在可行的機器上分配每個操作，以優化給定的目標。本文以每臺機器最大工作量最小化、單個工件最大完成時間最小化、總工作量最小化和最大提前或延遲時間最小化為四個目標。數學模型如下：

（1）設f1為工件完成的最大時間，其中Ci為工件i的完成時間，則有：

（2）設f2為機器最大工作量，其中Sij為工件i的第j道工序加工所用時間，則有：

（3）設f3為機器總工作量，則有：

（4）設f4為總延遲時間，其中[tei,tti]為工件i的交貨窗口，實際完成時間為Ci，當Ci ＜tei時，表示工件i提前完工，其懲罰值系數為hi；當Ci ＞tei時，表示工件i延期完成，其懲罰系數為wi，則有：

綜合上述四項，得出目標函數為：

本文比較當前較為流行的幾種算法，發現遺傳算法可以快速計算出最優解并可以很大限度的避開局部最優解；可以同時處理多個個體，易于實現并行化；具有自適應、自組織和自我學習的特性，符合本文系統基于智能工廠模式的大前提[24]。結合前面三點，因此本文提出的數學模型采用遺傳算法進行計算。

4 研究結果

4.1 編碼設計

傳統汽車配件生產工件與機器是一一對應的，每道工序都有對應的加工機器，多工件加工時，編碼只需要對不同工件之間的加工工序進行編碼，不需要對機器進行編碼。但隨著汽車生產機器的發展，生產設備不僅僅可以生產加工單一工件的某一道工序，傳統的僅對工序進行編碼已不能滿足生產調度的需求[21]?；谥悄芄S模式的生產調度編碼采用雙層編碼方式，一層是對不同的工序進行編碼，稱為操作順序編碼層；另一層對加工機器進行編碼，稱為機器編碼層。

操作順序編碼層是基于偏好加權進行編碼，每個染色體代表一個偏好。機器分配層的編碼采用整數編碼，整數表示機器的編號，每個操作選取的機器編號都是從可選機器編號集合中選取，從而解決機器限制問題。如表1 所示實例，表示的是由4 臺機器、3 個工件，每個工件由2-3 各工序組成的生產時間表。

表1 生產加工時間表

（1）基于工序的編碼。基于工序的編碼是基于偏好加權編碼，每個矩陣對應一條染色體，矩陣中的行代表工件，列代表工序，Oij表示工件i的第j道工序，元素Z表示所有待完成工序總數，工件中不存在的工序在矩陣中對應的元素值設為0。對于表1，有矩陣編碼E1，矩陣E1表示每個工序的先后，因工件3沒有第3道工序，所以E1的第三行第三列為0。

表1中工序的原始矩陣E為：

可以得出基于工序編碼的生產順序為：O11、O21、O31、O32、O12、O13、O22、O23。

（2）基于機器的編碼。矩陣E2中行代表工序，列代表機器數。其中行對應基于工序編碼的矩陣E1中的生產順序。將表1中的數據按照此規律排列，其中不能使用的機器矩陣元素設為-1，可得到矩陣E2：

矩陣E3中行代表機器，列代表工序。其中列對應基于工序編碼的矩陣E1中的生產順序。將表1中的數據按照此規律排列，其中不能使用的機器矩陣元素設為0，可得到矩陣E3：

對矩陣E2進行抽象，將選擇的機器設為1，其余未選擇的設為0，得到矩陣E4：

由第一行可以讀出O11由機器2 生產，第二行可以讀出O21由機器3 生產...；總的可以看出這八道工序的加工機器分別為：M2、M3、M2、M3、M1、M3、M4、M1。

4.2 解碼

（1）基于工序編碼的初始解。矩陣元素總數Z為待生產工件的總工序數，其中元素值為0的個數為P，則有非零元素個數Q=Z-P，首先在非零元素的位置上隨機放置1 ～Q 的自然數，再按從小到大的順序將每行元素排列就會得到初始解，其產生過程如下：

整理可得初始解E5：

（2）基于機器編碼的初始解。為了避免加工機器產生沖突，在矩陣進行抽象后要對不同工序間使用的機器是否在時間上存在沖突進行判斷。例如第道工序的開始時間為tis，加工時間為ti，在工序i后的第i+j道工序也要使用此機器，就需要判斷tis+ti≤t(i+j)是否成立，若成立則第i+j道工序可直接進行，否則將需要等待。

以上文所舉的例子，若要計算每道工序的加工時間，則矩陣E4×E3得到的矩陣E6的主對角線的數值即為工序所選加工機器所需加工時間。即第一道工序3.4h，第二道工序3.1h...以此類推。結合每道工序的開始時間可以得出總的加工時間。

4.3 交叉操作

交叉可以看作是遺傳算法的主干，它決定了整個算法的質量。為了避免產生不可行的解，我們設計了一種新的交叉方法，它由兩部分組成，一部分為基于工序的交叉方法，另一部分為基于機器的交叉方法。

結合上文提出的雙編碼方法。操作序列層的編碼基于偏好權編碼方法，每個基因代表一個偏好?？梢詫σ粋€生產車間由3個工件和4臺機器組成，每個工件由3 個工序，兩條染色體p1和p2的問題進行見表2的描述。

表2 雙層編碼例子

在進行偏好交叉時，我們改變了偏好的順序，每次操作的加工機器沒有改變，避免選擇不合適的機器，產生不可行的解。在基于工序的交叉方法中，首先選擇一個工序作為交叉工序，隨機選擇兩個染色體作為父母。然后，交換交叉工序的所有偏好，并對另一個工序的偏好進行統計分析，找出缺失的和重復的偏好號，用缺失的替換重復的。最后，從小到大重新安排每個工序的偏好。

例如，隨機確定兩條染色體的第二行為交叉行，交叉后P1會出現重復基因3和5，所以要用2代替第一行的5，8 代替第三行中的3，然后按照偏好大小進行排列，染色體P2給予同樣的處理，就可以得到子代C1和C2見表3。

表3 基于工序交叉后的后代

機器交叉時，保持操作工序不變，這里隨機選擇一個偏好數作為機器的交點，如果偏好數小于交點，且兩個父結點有相同的操作，交換加工機器。例如，隨機選擇偏好6作為機器的交點，操作偏好數要比6小，并且p1和p2的父母都是O11,O21,O31,O32，交換他們的加工機器，得到后代C3和C4，見表4。

表4 基于機器交叉后的后代

4.4 變異操作

為了保持種群的多樣性，防止早熟，本文在算法中引入了變異操作。由于采用了雙重編碼方法，因此采用了兩種類型的變異算子，即偏好變異算子和機器變異算子。

（1）突變的偏好。選擇一條染色體，交換兩個屬于不同工序的偏好，然后將每個工序的偏好從小到大重新排列。同時保持每一個操作的處理機器不變。

（2）機器突變。選擇一條染色體，隨機選擇它的一個偏好，然后用一個新的可行的染色體替換它的加工機器。

5 研究結果分析

5.1 汽車制造業生產方式分析

汽車制造企業屬于離散型企業，從細分生產模式分以按訂單設計、按訂單生產（裝配）和按庫存生產三種模式為主。

其中最普遍的是按庫存生產型（BTS）。全球汽車行業普遍存在產能過剩、產銷率明顯下降的問題。究其原因，一方面，市場趨于成熟，消費者趨于理性；另一方面消費者的要求更加個性化，單一的、大眾的商品已經無法滿足消費者的需求。傳統的面向庫存的預測推動的生產方式已經不能適應激烈的全球競爭。傳統生產方式將會形成如圖2 所示的惡性循環[26]。

圖2 BTS模式下的惡性循環

BTS模式基于“準確預測”的假設進行生產，但這個假設并不符合汽車市場的真實情況。當前，汽車制造企業面臨不斷變化的外部環境，顧客需求越來越細化。在市場全球化、技術更迭加速的背景下，競爭環境更加激烈?！耙钥蛻魹橹行摹钡钠髽I管理要求企業能夠對客戶的多元化需求做出快速響應，響應速度很大程度上決定了競爭優勢[27]。

隨著企業生產車間智能化、數據化轉型的加深，生產效益和對訂單的反應力由硬件設施轉向如何很好的利用硬件設施上。而生產模式的轉換不是一蹴而就的，需要逐漸過渡。面向庫存的生產模式要想向面向訂單的生產模式轉換，首先需實現商務與生產合同制，在最小庫存下有了生產訂單才進行生產、庫存系數研究，對安全庫存進行調整，逐步實現以客戶需求訂單拉動生產。

5.2 智能工廠生產物流管理新特性的思考

智能工廠相較于傳統的生產工廠已經結合了先進的通信技術、物聯網技術和控制技術，實現了生產全過程的信息化、產品全生命周期的智能化、標準化，具有自我信息更迭、優化、分析篩選的性能，傳統的生產物流管理已經不能滿足其生產需要，因為智能工廠的生產物流應具備以下幾點性能：

（1）生產數據的收集。傳統的制造業生產設備大都是數控機床，每個生產單元都是孤立的，但經過智能化升級改造后的智能工廠已經實現生產設備的智能化，將智能生產終端嵌入到生產現場中，并且利用物聯網技術實現各終端的互聯互通、智能感知。傳統的制造業生產物流沒有對生產數據進行利用，沒有感知生產參數，無法幫助智能工廠實現最大生產效益。

（2）物流數據的集成化。生產物流與整個生產過程緊密相連，生產物流數據的集成不僅僅包括現場生產原料的數據和倉庫存儲的數據，還應該包含生產各環節的物流數據，這樣才能真正實現物流的集成，使得物流模塊成為各個管理模塊的紐帶。

（3）生產數據的分析與反饋。智能工廠里的智能設備保證生產物流數據實時有效的更新、獲取、集成，還要對數據進行分析、處理，并將分析后的結果反饋給管理人員，使生產過程實現閉環控制，為生產管理者的決策提供參考。

5.3 改進遺傳算法執行流程延伸性思考

在針對單目標遺傳算法問題時，一般選擇最優解，但當涉及到多目標優化時幾個目標會出現沖突，很難說哪個更好，所以多目標問題的最優解是一個帕累托最優解集。當處理多目標優化問題時，想要得到帕累托最優解，首先需要先做非支配排序。傳統的一種非支配排序方法是在排序時一個解必須與所有解進行比較，該方法要進行大量計算，效率很低。為了快速高效地進行排序，本文設計了一種新的排序方法。

（1）設帕累托等級s=1。

（2）隨機選擇一個個體。

（3）將這個個體與整個群體進行比較，找出它的所有非支配解，支配解；在q1集中保留非支配解，q3集中保留支配解，q2集中保留其他解。

（4）如果q1不為空，從q1中隨機選擇一個個體，從第3 步執行；如果q1為空，對于q2中的每一個個體，在q2中尋找它的非支配解，如果在q1中找到這個個體，則將這個個體的帕累托等級設為s，并保持在q0中。

（5）如果q1和q2都為空，從第6 步執行，否則從第4步執行。

（6）s=s+1。

（7）從第2步執行到q1、q2和q3都為空。

6 結論

本文分析了汽車制造業生產物流的特征，得到基于智能工廠模式的汽車制造業生產物流管理系統的需求，并給出生產物流在倉儲上如何利用QR二維碼實現雙向定位；并針對工件需求較為集中時造成生產線堵塞甚至停工的情況給出綜合最小的最大完成時間、最小的單個設備工作量、最小總工作量的三個目標的數學模型?；诙嗄繕说膬灮玫脚晾弁薪饧?，設計了新的對比流程，可以快速求出最優解。