面向整車混流裝配線客戶訂單的優(yōu)化分配排序

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

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

0 引言

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

1 問題描述和數(shù)學模型

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

（1）考慮資源約束，在生產(chǎn)線產(chǎn)能得到充分利用的情況下，將每一計劃期內(nèi)的訂單合理地分配到各條生產(chǎn)線，使得在銷售淡季時能夠?qū)⑸倭坑唵渭性谝粭l或幾條生產(chǎn)線生產(chǎn)，在銷售旺季時能夠發(fā)揮各條生產(chǎn)線的優(yōu)勢，避免訂單流失，提升集團的市場占有率。

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

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

（4）各條生產(chǎn)線的生產(chǎn)負荷盡可能達到均衡。

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

目標函數(shù)1 制造總成本最低：

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

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

2 求解算法

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

2．1 編碼

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

圖1 THGA染色體編碼示意圖

2．2 適應度函數(shù)

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

2．3 選擇策略

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

2．4 禁忌遺傳算子

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

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

表1 某批訂單信息表

表2 某汽車制造企業(yè)4條生產(chǎn)線生產(chǎn)能力信息表

表3 某汽車制造企業(yè)4條生產(chǎn)線生產(chǎn)成本信息表

設初始序列為123412341，表示1～9號訂單分別分配給1、2、3、4、1、2、3、4、1號生產(chǎn)線，用序列編碼123412341表示。同時設計了兩級控制基因，第一級控制基因有9位，全部為1，處于激活狀態(tài)，第二級控制基因均為4位，可以取0或1，分別控制參數(shù)基因是否激活。仿真模型中算法的參數(shù)設置如下：初始種群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可以明顯看到，最優(yōu)解即是離坐標軸原點最近的那個點，即表4中序號為1的一組解。最優(yōu)解的詳細數(shù)據(jù)如表5所示，各條生產(chǎn)線負荷情況如圖5所示。從圖5中可以看出，在生產(chǎn)淡季時各條生產(chǎn)線負荷差距大一些，這是因為為了節(jié)約成本而將訂單集中為某一條或幾條生產(chǎn)線的結(jié)果，當訂單變多，到了生產(chǎn)的正常季節(jié)和旺季時，各條生產(chǎn)線的生產(chǎn)負荷率就變得趨于平均了。同時，從表5可以看出，經(jīng)過優(yōu)化的訂單分配原則與現(xiàn)有的訂單分配原則相比，在生產(chǎn)成本的控制和生產(chǎn)線負荷均衡度上均有了明顯的改觀，從而進一步驗證了算法的有效性。

表5 淡季、正常季、旺季最優(yōu)解

4 結(jié)語

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

圖5 各條生產(chǎn)線負荷圖

［1］ 趙偉，韓文秀，羅永泰．準時生產(chǎn)方式下混流裝配線的調(diào)度問題［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］ 黃剛．混流裝配生產(chǎn)的計劃排序及其執(zhí)行過程管理［D］．武漢：華中科技大學，2007．

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

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

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

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