基于混合遺傳算法的混流混合車間協同調度問題

李修琳 魯建廈 柴國鐘 湯洪濤 蔣玲玲

浙江工業大學，杭州，310032

0 引言

在實際離散制造過程中，產品生產過程一般包括零件加工、部件裝配和產品總裝，其生產形式是作業車間和流水車間集成的混流混合車間模式。零件加工車間、部件裝配車間與產品總裝車間在計劃制定、物料供應和調度執行方面都緊密相關。生產調度及其執行過程中，優化多集中于單一車間而忽略與其他車間的關聯影響。如零件加工車間往往以產品切換費用、換模費用的最少等目標來安排生產，而部件裝配車間、產品總裝車間以生產周期最短等目標來安排生產，從而導致零件的加工進度跟后續的部件裝配或者產品總裝不相匹配，造成大量的緩沖區在制品庫存，拉長了產品的整個生產周期，影響了生產流程化，無法達到系統最優。在混流生產模式下，這種情況尤為嚴重。因此，對于具有自制件的混流裝配生產過程，必須從整體優化的角度出發，建立多車間的集成調度。

目前的研究主要針對零部件車間的加工調度或者零部件裝配車間的排序調度等單一車間展開，對作業車間和流水車間的集成研究較少。Lee等［1］研究了三機裝配型流水車間的調度問題，優化目標是最小化最大完工時間。文獻［2－3］以最小化最大完工時間為優化目標，研究了帶裝配操作的兩機流水車間調度問題。上述研究考慮的加工裝配車間過于簡單，只是將裝配車間看成一臺機器，研究的是單品種生產，且沒有考慮各個車間之間的緩沖區在制品庫存問題。王炳剛等［4－5］研究了帶有限緩沖區的流水車間集成調度問題，建立了帶并行機的流水部件線和單機流水總裝線的集成調度模型，有效彌補了上述研究的不足，但仍沒有關于作業車間與流水車間的混合模型。

1 問題描述

1.1 混流混合車間模型

本文所要研究的混流混合車間由三部分組成：第一部分為加工零件的作業車間，以批為單位進行生產；第二部分為裝配部件的流水車間，以個為單位進行裝配；第三部分為產品總裝的流水車間，以個為單位進行裝配。圖1所示為所要研究的混流混合車間簡化模型。

圖1 混流混合車間簡化模型

混流混合車間主要有以下特點：①混合車間生產不同品種的產品，且以混流生產方式組織生產；②零件加工車間、部件裝配車間、產品總裝車間之間由緩沖區連接；③零件加工車間為部件裝配車間和產品總裝車間提供物料，部件裝配車間為產品總裝車間提供物料；④各生產單元間通過物料約束關聯，適當的緩沖設置可在生產流暢的情況下減少生產運作成本；⑤同時具有作業車間調度和流水車間調度問題的各種約束條件；⑥加工零件的作業車間以批為單位進行生產，部件裝配、產品總裝的流水車間以個為單位進行生產。

1.2 混流混合車間調度模型的構建

在混流混合生產系統中，各生產單元是相對獨立的子系統，雖然具有不同的生產特征和優化目標，但仍相互依賴、相互制約。在生產調度過程中，各生產單元通常單獨制定調度方案，單方面進行各自生產單元的優化，雖然達到各自的生產目標，但卻以其他單元生產目標的弱化為代價，使生產內部不協調，經常出現需要的零部件未生產，而暫時不需要的零部件卻大量堆積，產生大量在制品庫存，嚴重影響了生產物流的流暢性，增加了企業生產、場地和資源的成本。因此，集成調度零件加工車間、部件裝配車間、產品總裝車間，并控制其之間的緩沖區在制品庫存具有非常重要的實際意義。針對混流混合車間調度問題，建立以最小化緩沖區在制品庫存成本為目標的優化模型。

混流混合車間調度問題可描述為，以零件加工車間、部件裝配車間和產品總裝車間組成的三段生產系統中，零件加工車間有m臺機器，加工n種零件，部件裝配車間有l1個裝配工位，生產r1種部件；產品總裝車間有l2個裝配工位，生產r2種產品，生產調度旨在安排各工件在各設備和工位上的生產順序，實現既定目標的優化。為了便于研究混流混合車間調度問題，給出以下假設條件：

（1）只對自制件在流水車間裝配的調度進行研究，外購外協件不在考慮范圍內。

（2）若零件加工車間為部件裝配車間、產品總裝車間的裝配工位加工了一批零件，或者部件裝配車間為產品總裝車間的裝配工位加工了某種部件，而裝配工位不需要，即裝配工位已有的零部件能夠滿足裝配所需要的數量，或者已加工的零部件不是裝配工位所需要的類型，則將此批零件或者此種部件暫存在緩沖區，反之向相應工位配送，其中的配送時間假定為零。

（3）作業車間內零件的工序之間有工藝約束，不同零件之間不存在工藝約束。

（4）在零時刻，所有的零件都可以被加工。

（5）在零時刻，所有的機器及裝配工位都已經準備就緒。

（6）工序加工時間已經包含了工序的準備時間和搬運時間。

目標函數為最小化緩沖區在制品庫存成本，模型如下：

式中，Ai為一批自制零件i所占的面積；Ax為一個部件x所占的面積；Ci為單位面積的零件i在緩沖區存放單位時間所占用的成本；Cx為單位面積的部件x在緩沖區存放單位時間所占用的成本；Ti為一批零件i被加工出來的完工時刻；T′i為此批零件被下游領走的時刻；Tx為一個部件x被生產出來的完工時刻；T′x為此部件被下游領走的時刻。

1.2 模型約束

1.2.1 工藝順序約束

（1）零件加工車間約束。自制零件的前一道工序加工完成后，才能加工后一道工序，其約束表達式為

式中，Eij、Eih分別為零件Ni在機器Mj和Mh上加工的完工時刻；D是一個足夠大正數，作為對約束違背的懲罰系數；tij為一批自制零件Ni在機器Mj加工所需要的時間。

（2）部件裝配車間約束。部件的前一道工序裝配完成后，才能裝配后一道工序，其約束表達式為

式中，Exk、ExH分別為部件裝配流水車間中部件x在第k個裝配工位和第H個裝配工位上的完工時刻；txk為一個部件x在第k個裝配工位上裝配所需要的時間。

（3）產品總裝車間約束。產品的前一道工序裝配完成后，才能裝配后一道工序，其約束表達式為

式中，Eys、EyK分別為產品總裝流水車間產品y在第s個裝配工位和第K個裝配工位上的完工時刻；tys為一個產品y在第s個裝配工位上裝配所需要的時間。

1.2.2 資源約束

（1）零件加工作業車間約束。在同一臺機器上，一批零件的加工任務完成后，方能開始下一批加工，其約束表達式為

（2）部件裝配流水車間約束。在同一個裝配工位上，一個裝配任務完成后，方能開始下一個任務，其約束表達式為

（3）產品總裝流水車間約束。在同一個裝配工位上，一個裝配任務完成后，方能開始下一個任務，其約束表達式為

1.2.3 時間約束

（1）部件裝配完工時間等于該部件進入工位的時間與裝配操作時間以及在該工位的等待時間之和：

式中，Bxk為部件裝配流水車間中部件x在裝配工位k上可以開始裝配的時刻，即表示部件x已經完成前一道工序的裝配任務，裝配工位k已經完成前一個部件的裝配任務；Δxk為部件裝配車間部件x在裝配工位k上開始裝配的延遲時間（停工待料時間）；Qikt、Qikt′分別為t和t′時刻部件裝配車間的裝配工位k含有的自制零件i的數量；Oixk為t時刻部件裝配車間部件x在裝配工位k上裝配時需要的自制零件i的數量；txk為一個部件x在第k個裝配工位上裝配所需要的時間。

（2）總裝配件完工時間等于該產品進入工位的時間與裝配操作時間以及在該工位的等待時間之和：

式中，Bys為產品總裝流水車間產品y在裝配工位s上可以開始裝配的時刻，即表示產品y已經完成前一道工序的裝配任務，裝配工位s已經完成前一個產品的裝配任務；Δys為產品總裝流水車間產品y在裝配工位s上開始裝配的延遲時間（停工待料時間）；Qist為t時刻產品總裝車間裝配工位s含有自制零件i的數量；Qiys為產品總裝車間的產品y在裝配工位s進行裝配時需要的自制零件i的數量；Qxst為t時刻產品總裝車間裝配工位s含有部件x的數量（前面已經假設零部件從緩沖區配送到裝配工位的時間為零，此時的數量為裝配工位和緩沖區中數量的總和）；Qxys為產品總裝車間產品y在裝配工位s上進行裝配時需要部件x的數量；tys為一個產品y在第s個裝配工位上裝配所需要的時間。

模型中，aihj、bigj、a′xHk、b′xgk、a′yKs、b′ygs為指示變量，aihj、a′xHk、a′yKs為0，表明該調度方案不符合工藝順序約束要求；bigj、b′xgk、b′ygs為0，表明該調度方案不符合資源約束要求。

2 混合遺傳算法求解調度模型

遺傳算法是求解組合優化問題的優秀算法，具有良好的全局搜索能力，針對混流混合車間調度解空間大的特征，具有較好的優化效果。目前，GA在裝配線和作業車間獨立優化問題上已取得良好的應用效果［6-8］，與模板退火算法結合的混合算法也取得了良好效果［9］。因此，將遺傳算法作為算法主流程。為提高局部搜索能力，在遺傳算法的流程中嵌入模擬退火算法，建立了一種混合算法。模擬退火算法可以對每一代種群中最好的部分個體執行退火操作，有效提高鄰域搜索效率，彌補遺傳算法在局部搜索方面的不足。

2.1 算法流程

圖2所示為混合算法的主要流程。相關說明如下：①算法包含5個基本參數（種群規模N、最大迭代次數M、初始溫度θ0、終止溫度θend、退溫系數λ），隨機產生規模為N的初始種群P（T），初始代數T＝0；②適應度計算，計算種群中每個個體的適應度值；③對種群進行選擇、交叉、變異操作，產生新一代種群P（T＋1），并將種群中具有最佳適應度值的個體集合作為P（x）；④對種群P（x）進行模擬退火操作；⑤判斷迭代條件，如果滿足則輸出最優解，并終止算法。

圖2 混合算法的主要流程

2.2 算法詳細設計

2.2.1 編碼

混流混合車間調度問題的編碼規則如下：根據給定的生產任務，先將產品級分解為部件級、零件級，然后根據各種零件的數量、比例和加工批量確定零件生產車間的零件生產批量；部件裝配車間和產品總裝車間是流水車間，取各產品數量的最大公約數，并通過各產品數量除以該值確定各部分的最小生產循環，對一個循環中的產品裝配工序進行編號；編碼分成三部分，其中，第一部分為零件加工車間零件的批量編號，第二部分為部件裝配車間的部件編號，第三部分是產品總裝車間的產品編號。為了修正操作運算后產生的非法解，分別對零件加工工序和裝配工序的對應編號從小到大進行重排序，從而保證產生的新種群都為合法解。

示例：產品總裝流水車間要生產10個A、10個B；裝配1個產品A需要1個部件U、1個零件a和1個零件b；裝配1個產品B需要1個部件V、1個零件a和1個零件c；裝配1個部件U需要1個零件d，裝配1個部件V需要1個零件e。其中，各零件加工批量為10。假定零件加工作業車間由4臺設備（M1、M2、M3、M4）組成，加工零件a、b、c、d、e。各零件工序作業時間及作業順序如表1所示。表1中，逗號左側的數字為加工時間（s），逗號右側的數字為加工工序的順序號。

由已知條件可以知道，生產10個產品A、10個產品B需要零件20個a、10個b、10個c、10個d、10個e，需要部件10個U、10個V，即零件加工作業車間需要加工2批a、1批b、1批c、1批d、1批e。零件序列為［a，a，b，c，d，e］，分別對各零件工序進行編號，如表2所示。表2中，a出現2次，表示零件a的2個不同批次；部件裝配流水車間需要裝配10個U、10個V，則部件裝配流水車間的最小生產循環為1個U、1個V，對其進行編號，如UV為1個最小生產循環；產品總裝流水車間的最小生產循環為1個產品A和1個產品B，如AB為一個最小生產循環。

表1 工序作業時間及作業順序表

表2 工序順序編號表

圖3所示為一條染色體編碼。染色體采用三段式的編碼方法，S1段為作業車間編碼，S2段為部件車間編碼，S3段為裝配車間編碼。其中，編號1～4的碼值為1，該碼值按照順序分別代表第一個工件即工件a的4個工序。采用該編碼方法可在交叉變異操作時避免非法染色體的產生。

2.2.2 適應度函數

由于優化目標為緩沖區在制品成本最小化，因此將目標函數適當改變作為適應度函數：

2.2.3 種群選擇

算法根據適應度函數值采用賭輪盤法選擇個體遺傳到下一代群體中。

2.2.4 交叉與變異

鑒于混流混合車間調度問題特點，零件加工車間、部件裝配車間、產品總裝車間的各段染色體編碼進行各自獨立的交叉和變異操作。交叉方法采用單點交叉；變異采用交換變異方法，即交換兩個隨機位置上的基因［10］。

2.2.5 模擬退火算法

圖3 染色體編碼

為提高精英群體的質量，算法采用變溫度的模擬退火算法對每代最優的群體P（x）執行模擬退火操作SA。最優解x操作后得到的新解x′＝SA（x）。如果x′優于x則保留新解，否則以概率exp（－Δθ′/θ）接受新解，其中，θ為當前溫度，Δθ′為原解與新解的適應度差。新解的產生通過交換變異的方法，分別對三段編碼各自進行交叉，防止不同類調度工件的串碼，從而保證染色體的合法性。算法進程由初始溫度θ0、終止溫度θend、退溫系數λ控制。模擬退火算法增強了個體的局部搜索能力，但增加了時間和計算成本，為平衡算法效率，算法采用變溫度的溫度適應算法，其中，當前溫度為

式中，T為當前迭代代數；ceil（＊）表示對括號中內容向下取整。

為保證迭代末期的有效溫度，設定θ′e不小于1。在變溫度的支持下，算法初期可提高算法的全局尋優能力，算法后期可加快算法的收斂速度，從總體上提高了算法的執行效率。

2.2.6 終止準則

以預先設定的最大進化代數M為終止條件。

3 實例驗證

混流混合車間在生產中應用廣泛，現以某冰箱制造企業為例對模型和算法進行驗證。該生產系統由零件加工車間、部件裝配車間和一條總裝配線組成。零件加工車間的主要任務為生產8種自制零件。自制件集合為｛N1，N2，…，N8｝，作業車間機器集合為｛M1，M2，…，M10｝。自制件在各機器上的加工以批為單位，工藝順序及加工時間如表3所示。

表3 自制件工藝順序及加工時間

部件裝配車間主要負責門體A、B的裝配，其裝配工藝與時間如表4所示。

表4 部件裝配工序的作業時間 s

產品總裝流水車間共有33個裝配工位，流轉產品 Q1、Q2、Q3、Q4，對應的裝配工序作業時間如表5所示。

表5 總裝裝配工序的作業時間 s

表6為零部件對應的產品需求矩陣，對應值為所需數量。

表6 產品需求矩陣

表7 各零部件滯留單位成本 元/（d·m2）

圖4 零件加工調度甘特圖

4 結語

混流混合車間是離散生產中常見的生產組織方式，本文描述了混流混合車間調度問題的特點，建立了混流混合車間緩沖區在制品成本最小優化模型，給出了集成模擬退火算法的混合遺傳算法，并對模型進行求解，最后通過某冰箱企業混流混合車間調度問題的實例研究，驗證了所建模型和算法的有效性。文中僅針對混流混合車間做了初步的集成調度研究，但混流混合車間作為一種混合生產系統，影響因素多，并涉及多個優化目標，后續研究應發掘影響生產系統的瓶頸因素，實現各子系統的多目標協調調度。

［1］Lee C Y，Cheng T C E，Lin B M T.Minimizing the Makespan in the 3－Machine Assembly－type Flow Shop Scheduling Problem［J］.Management Science，1993，39（5）：616－625.

［2］Cheng T C E，Wang G.Scheduling the Fabrication and Assembly of Components in a Two－machine Flow Shop［J］.IIE Transactions，1999，31（2）：135－143.

［3］Lin B M T，Cheng T C E.Fabrication and Assembly Scheduling in a Two－machine Flow Shop［J］.IIE Transactions，2002，34（11）：1015－1020.

［4］王炳剛，饒運清，邵新宇，等.基于多目標遺傳算法的混流加工/裝配系統排序問題研究［J］.中國機械工程，2009，20（12）：1434－1438.

［5］王炳剛.混流加工/裝配系統集成優化研究［J］.機械工程學報，2010，46（17）：114－122.

［6］蘇平，于兆勤.基于混合遺傳算法的混合裝配線排序問題研究［J］.計算機集成制造系統，2008，14（5）：1001－1007.

［7］Chul J H，Kim Y.A Genetic Algorithm for Multiple Objective Sequencing Problems in Mixed Model Assembly Lines［J］.Computers and Research，1998，25（7）：675－690.

［8］袁坤，朱劍英.一種求解多目標柔性Job Shop調度的改進遺傳算法［J］.中國機械工程，2007，18（2）：156－160.

［9］魯建廈，蔣玲玲，李修琳.基于混合粒子群算法求解裝配線第二類平衡問題［J］.中國機械工程，2010，21（4）：420－424.

［10］劉民，吳澄.制造過程智能優化調度算法及其應用［M］.北京：國防工業出版社，2008.