面向整車混流裝配線客戶訂單的優化分配排序

李蘇珂 劉盛強 喻道遠 張三強 史登松 何世林

1．華中科技大學數字制造裝備與技術國家重點實驗室，武漢，430074 2．中國重型汽車集團有限公司，濟南，250022

0 引言

混流裝配線有時也特指混合車型組裝線，其特點是在一定時間內，在一條生產線上生產出多種不同型號的產品，產品的品種可以隨顧客需求的變化而變化［1－2］。作為當前離散制造業普遍采用的一種生產方式，混流裝配生產涉及不同的產品、復雜的裝配過程及品種繁多的物料，因而其計劃排序與執行管理問題比一般的流水生產更為復雜［3］。以往的研究主要集中在單一生產線混流裝配排產順序優化方面，常用的優化目標有兩個：基于生產負荷平衡的目標和基于物流平順化的目標［3］。隨著國內區域經濟的不平衡發展，經濟發達地區的制造型企業為了節約生產本，產品制造基地逐漸向經濟欠發達的地區轉移。而處于不同地域的產品制造基地的生產能力、人力和資源成本各不相同，這種跨地域的混流生產模式給制造型企業帶來了巨大的挑戰。因此，探索如何在充分利用產能的情況下，對訂單進行合理分配和排序，使處于不同地域擁有不同生產能力和特點的生產線制造出總成本最低的產品，具有很強的實際意義。

1 問題描述和數學模型

考慮一個大型的汽車制造集團在不同地方共設有M條生產線，能夠生產N種型號的汽車，但各條生產線能夠生產的汽車型號不盡相同，集團一共擁有K個客戶，所有的客戶訂單由企業的計劃部統一接收并分配到各條生產線，在這里為了保證訂單的完整性，所有訂單不做合并或者拆分處理。根據調研得到集團訂單的分配原則：

（1）考慮資源約束，在生產線產能得到充分利用的情況下，將每一計劃期內的訂單合理地分配到各條生產線，使得在銷售淡季時能夠將少量訂單集中在一條或幾條生產線生產，在銷售旺季時能夠發揮各條生產線的優勢，避免訂單流失，提升集團的市場占有率。

（2）由于各條生產線所在地域和構造存在差異，導致即使生產同種車型，其生產節拍、生產成本、物流成本、人力成本等都可能不一樣。因此在追求成本最低、交貨期最短的目標下，盡量將訂單分配給生產時間短、成本低的生產線。

（3）在生產訂單少、不能滿負荷生產的情況下，應該兼顧各條生產線的利益，盡量平衡工人間的收入。

（4）各條生產線的生產負荷盡可能達到均衡。

企業每隔一定周期發布生產計劃，每個計劃發布周期包含T個時間段，每個時間段內客戶的訂單需求都必須盡量得到滿足，如果超過交貨日期，企業將會付出相應的懲罰成本。因此，企業的優化目標是：在產能允許和產能得到充分利用的情況下，依照客戶需求，合理地安排客戶訂單的生產地點和上線順序，按時交貨，最終使產品制造總成本得到降低。綜上所述，對該問題建立如下數學模型：

目標函數1 制造總成本最低：

式中，Anm為生產線m生產車型n的約束；Pnmt為生產線m在t時間段內生產訂單n超期的罰金；Cnm為生產線m生產車型n的單位生產費用；Qnmt為生產線m在t時間段生產車型n的數量；Mnm為生產線m生產車型n的單位物料成本；Tnm為生產線m生產車型n的單位運輸費用；Lm為當前企業的生產負荷率；DLTn為車型n的訂單交貨期；Rnmt為生產線m在t時間段內生產車型n的實際生產能力；R′nmt為生產線m在t時間段內生產車型n的理論產能；Dnkt為在t時間段內客戶k對車型n的需求。

目標式（1）使所有訂單的懲罰費用、生產費用、物料成本、運輸費用之和最小；目標式（2）使各條生產線生產負荷盡可能均衡；約束式（3）使得生產量為非負，并且限制在生產線產能之內；約束式（4）表示準時制生產，生產量等于需求量；約束式（5）表示約束A是0或1的調整變量；約束式（6）表示訂單不可拆分。

2 求解算法

本文所求解的問題是一類典型的NP－har d難題，目前針對此類問題主要有以下三類算法［4］：①最優解算法，如分支定界法、整數規劃法、動態規劃法；②試探算法，如目標追隨法；③循環改進法，如模擬退火算法、遺傳算法等。其中，遺傳算法自其被提出以來已經在調度領域得到了廣泛的應用，但是它也存在容易陷入早熟、爬山能力差的弱點，所以許多學者提出了改進的遺傳算法，禁忌遺傳算法（TSGA）和遞階遺傳算法［5］就是其中兩種重要的方法。禁忌搜索能夠有效克服最優解陷入局部最優的問題，它主要針對遺傳算子進行改進，不需要改變編碼的結構，而遞階遺傳算法不對遺傳算子進行更改，它通過改善編碼結構來克服早熟的問題，所以二者存在較強的互補性。基于以上思想，本文采用禁忌 — 遞階遺傳算法［6］（THGA）來求解本文的問題。

2．1 編碼

THGA的染色體由控制基因（CG）和參數基因（PG）兩部分組成，其中基因是一串二進制數，控制基因中的1表示被其控制的基因處于激活狀態，0表示被其控制的基因處于失活狀態，它們分別模擬了生物進化過程中染色體上的顯性和隱形基因。在遺傳的過程中，顯性基因有可能成為隱形基因，而隱性基因亦有可能成為顯性基因。參數基因的有效性由控制基因決定。圖1為T HGA染色體編碼示意圖。

圖1 THGA染色體編碼示意圖

2．2 適應度函數

目標函數要通過標定來映射為適值函數，合適的標定可以防止早熟的發生，常用的標定方法有動態線性標定、冪率標定、對數標定等。本文使用正規化技術進行標定，它通過將目標函數f映射到（0，1）區間，從而抑制超級染色體。對于本文的最小化問題標定如下：

2．3 選擇策略

當完成個體的適應值計算后，將由選擇策略完成對這一代個體的選擇工作，賭輪法和排序法是最常用的兩種選擇方法，本文將兩種選擇方法結合起來使用。

2．4 禁忌遺傳算子

為了克服遺傳算法爬山能力弱的缺點，將禁忌搜索算法（TS）特有的記憶功能引入到普通的遺傳算法（GA）算子中，由此重新定義了禁忌交叉算子（TSCO）、禁忌變異算子（TSMO），使得T HGA擁有更強的爬山能力。禁忌交叉算子根據交叉概率Pc隨機地交換種群中兩個個體的部分基因，禁忌變異算子根據變異概率Pm隨機地改變父代染色體的某些基因位的值。顯性操作模擬自然界的二倍體現象，它能夠解決動態環境下復雜系統的優化問題，易于跟蹤環境的動態變化過程，它能保護所記憶的基因免受有害選擇運算的破壞［7］。禁忌遺傳算子中描述基因的字符集為｛0，1，10｝，其中1表示顯性的1，10表示隱性的1。具體映射關系如下所示：（0，0）→0；（10，0）→0；（1，0）→1；（0，10）→0；（10，10）→1；（1，10）→1；（0，1）→1；（10，1）→0；（1，1）→0。

3 應用舉例

為了驗證本模型及算法的實用性，本文分別選取了某汽車制造企業淡季、正常季、旺季三個時期的典型訂單來進行說明，如表1所示，所有訂單的交貨期為7天，如超期則每臺車罰金為3000元／天。企業信息如表2和表3所示。目前企業的訂單分配原則是：M1車分配給1、2號生產線生產，M2車分配給3號生產線生產，M3車分配給4號生產線生產。

表1 某批訂單信息表

表2 某汽車制造企業4條生產線生產能力信息表

表3 某汽車制造企業4條生產線生產成本信息表

設初始序列為123412341，表示1～9號訂單分別分配給1、2、3、4、1、2、3、4、1號生產線，用序列編碼123412341表示。同時設計了兩級控制基因，第一級控制基因有9位，全部為1，處于激活狀態，第二級控制基因均為4位，可以取0或1，分別控制參數基因是否激活。仿真模型中算法的參數設置如下：初始種群20，交叉概率Pc＝0．8，變異概率Pm＝0．1，運行8代，獲得20組Pareto解，如表4、圖2～圖4所示。

表4 淡季、正常季、旺季的20組Pareto解

圖2 淡季的20組Pareto解

圖3 正常的20組Pareto解

圖4 旺季的20組Pareto解

分析圖2～圖4可以明顯看到，最優解即是離坐標軸原點最近的那個點，即表4中序號為1的一組解。最優解的詳細數據如表5所示，各條生產線負荷情況如圖5所示。從圖5中可以看出，在生產淡季時各條生產線負荷差距大一些，這是因為為了節約成本而將訂單集中為某一條或幾條生產線的結果，當訂單變多，到了生產的正常季節和旺季時，各條生產線的生產負荷率就變得趨于平均了。同時，從表5可以看出，經過優化的訂單分配原則與現有的訂單分配原則相比，在生產成本的控制和生產線負荷均衡度上均有了明顯的改觀，從而進一步驗證了算法的有效性。

表5 淡季、正常季、旺季最優解

4 結語

針對某汽車企業的實際情況提出了以制造總成本最小和生產線負荷均衡為目標的數學模型，同時將禁忌—遞階遺傳算法應用到該模型，并且選取了3組較具代表性的分別反映銷售淡季、正常季和旺季的訂單，得出了比較滿意的結果。本文提出的模型和方法可以合理地優化配置處于不同地域不同生產線的生產任務，降低企業生產成本。該方法也可供其他整車制造型企業借鑒。

圖5 各條生產線負荷圖

［1］ 趙偉，韓文秀，羅永泰．準時生產方式下混流裝配線的調度問題［J］．管理科學學報，2000，3（4）：23－28．

［2］ Zhao Xiaobo，Zhou Zhaoying，Asres A．A Note on Toyota’s Goal of Sequencing Mixed Models on an Assembly Line［J］．Co mputers ＆ Industrial Engineering，1999，36：57－65．

［3］ 黃剛．混流裝配生產的計劃排序及其執行過程管理［D］．武漢：華中科技大學，2007．

［4］ 孫新宇，萬筱寧，孫林巖．蟻群算法在混流裝配線調度問題中的應用［J］．信息與控制，2002，32（6）：486－490．

［5］ 鄭丕諤，馬艷華．RBF神經網絡的遞階遺傳訓練新方法［J］．控制與決策，2000，15（2）：165－168．

［6］ 柯珂，張世英．禁忌－遞階遺傳算法研究［J］．控制與決策，2001，16（4）：480－483．

［7］ 汪定偉，王俊偉，王洪峰，等．智能優化方法［M］．北京：高等教育出版社，2007．