劉冠權(quán) 奚 浩 王 越 王志遠(yuǎn)

(青島理工大學(xué)管理工程學(xué)院 山東 青島 266520)

0 引 言

互聯(lián)網(wǎng)、物聯(lián)網(wǎng)時(shí)代到來，顧客消費(fèi)需求升級，不再滿足于單一模板化，向個(gè)性定制化過渡發(fā)展，混流裝配線作為一種可以實(shí)現(xiàn)多品種產(chǎn)品的裝配線可以更好滿足顧客需求的多樣化。因此高魯棒性、高柔性混流裝配線的排序問題將成為制造業(yè)生產(chǎn)運(yùn)作優(yōu)化的重要問題。

Drexl等[1]對汽車投產(chǎn)排序問題提出了整數(shù)規(guī)劃(Integer Programming，IP)模型并進(jìn)行求解；Fliedner等[2]在此基礎(chǔ)上進(jìn)一步修改了目標(biāo)函數(shù)并采用分支定界法求解此類問題。鄭敏等[3]建立了涂裝切換成本和總裝車間人工成本最小化的兩個(gè)目標(biāo)函數(shù)模型，并用CPLEX數(shù)學(xué)規(guī)劃軟件對其進(jìn)行優(yōu)化求解。

當(dāng)混流裝配線排序問題規(guī)模比較小時(shí)，上述數(shù)學(xué)規(guī)劃方法雖然能夠得到較好的解,但對于大規(guī)模問題，短時(shí)間內(nèi)很難找到最優(yōu)解。因此，近年來大多數(shù)專家用啟發(fā)式算法以及現(xiàn)代智能優(yōu)化算法來解決這類問題。

鄭永前等[4]針對混裝線排序問題，從裝配線總閑置-超載成本最小化角度，建立了數(shù)學(xué)模型并設(shè)計(jì)粒子群算法進(jìn)行求解；黃健等[5]則在前者基礎(chǔ)之上，加入產(chǎn)品變化率、總切換時(shí)間的目標(biāo)，在離散系統(tǒng)仿真軟件Plant Simulation平臺進(jìn)行仿真，并結(jié)合總工時(shí)最小化目標(biāo)，采用遺傳算法得出一組滿意解，最后從混裝線平衡角度對得到的滿意解進(jìn)行分析,得到滿足目標(biāo)的最優(yōu)解。劉瓊等[6]同樣建立了以最小化工作站閑置/超載總成本、產(chǎn)品變化率和產(chǎn)品切換總時(shí)間為目標(biāo)的多目標(biāo)優(yōu)化模型，但設(shè)計(jì)了一種改進(jìn)多目標(biāo)貓群優(yōu)化算法對該問題進(jìn)行應(yīng)用。李修琳等[7]從串并行線與總裝線投產(chǎn)序列差異度最小和總裝物料消耗平順化角度，建立了多目標(biāo)關(guān)聯(lián)排序模型。江新利等[8]研究了某冷柜公司生產(chǎn)系統(tǒng)中具有有限緩沖的兩生產(chǎn)階段排序問題,并設(shè)計(jì)了一種庫存量計(jì)算算法來更好地計(jì)算空模數(shù)量與在制品庫存數(shù)量，通過改進(jìn)遺傳算法求解了兩個(gè)生產(chǎn)階段的排序問題。甘雅文等[9]建立了以工作站堵塞時(shí)間最小化與產(chǎn)品切換次數(shù)最小化為目標(biāo)的混裝線排序模型，首次引入主客觀優(yōu)化評價(jià)算法對模型進(jìn)行求解。Chutima等[10]則考慮了三個(gè)相互沖突的目標(biāo)，包括最小化油漆顏色變化的數(shù)量、最小化比率約束違規(guī)的總數(shù)、最小化效用工作，并提出了擴(kuò)展重合算法(COIN-E)求解該問題。

綜上所述，啟發(fā)式算法和現(xiàn)代智能優(yōu)化算法與數(shù)學(xué)規(guī)劃法相比較而言，能夠更好地解決該問題?；诖耍云嚮炝餮b配線為研究對象，從最優(yōu)化投產(chǎn)車型序列進(jìn)入各工位總等待裝配時(shí)間(一個(gè)最小生產(chǎn)循環(huán)周期)的角度，建立數(shù)學(xué)模型，并設(shè)計(jì)出一種改進(jìn)的遺傳算法進(jìn)行求解，得到了最優(yōu)車型排序。與標(biāo)準(zhǔn)遺傳算法進(jìn)行對比分析，體現(xiàn)了本文算法的優(yōu)越性。該算法改進(jìn)之處在于其“定長”實(shí)數(shù)編碼、“定序模式”改進(jìn)的自適應(yīng)單點(diǎn)交叉、交換變異算子的設(shè)計(jì)避免了不可行解的產(chǎn)生，同時(shí)在選擇操作還引入精英保留策略，保證最優(yōu)后代不被丟失，極大提高了算法的性能。最后通過Flexsim軟件分別對最優(yōu)車型排序和實(shí)際生產(chǎn)中的車型排序進(jìn)行了仿真與對比。

1 數(shù)學(xué)模型

1.1 問題描述

混流裝配線排序問題是根據(jù)產(chǎn)品訂單信息將不同類型產(chǎn)品排成一個(gè)投產(chǎn)序列，并以此投產(chǎn)序列來組織混流裝配線的生產(chǎn)[11]。

在汽車混流裝配線中，投產(chǎn)車型排序采用最小生產(chǎn)循環(huán)模式(Minimum Part Set，MPS)，即整個(gè)裝配順序由重復(fù)的MPS構(gòu)成。MPS由各車型的訂單需求數(shù)量比例構(gòu)成最小投產(chǎn)序列，只需將MPS進(jìn)行排序，并讓其結(jié)果循環(huán)N次，即可得到整個(gè)投產(chǎn)順序。

1.2 相關(guān)符號的定義

n表示混流裝配線的工位總數(shù)；d代表一個(gè)MPS循環(huán)中投產(chǎn)車輛數(shù)量；N表示每天循環(huán)總次數(shù)，即每天各車型訂單需求量的最大公約數(shù)；D表示某汽車企業(yè)mes系統(tǒng)中每天接到各車型訂單數(shù)量總數(shù)；i表示第i個(gè)投產(chǎn)車輛，i取1,2,…,d；j表示第j個(gè)工位，j取1,2,…,n；k表示第k種車型，k取1,2,…,K,其中K表示裝配線可生產(chǎn)的車型種類為K種;qk表示一次循環(huán)中各種車型的投產(chǎn)數(shù)量；Tij表示第i個(gè)投產(chǎn)車輛在第j個(gè)工位的等待時(shí)間；Bij表示第i個(gè)投產(chǎn)車輛在第j個(gè)工位開始裝配的時(shí)刻；Fij表示第i個(gè)投產(chǎn)車輛在第j個(gè)工位結(jié)束裝配的時(shí)刻；xik表示為第i個(gè)投產(chǎn)車輛是k型的，取值為 0 或 1；tkj表示k型車輛在第j個(gè)工位的作業(yè)時(shí)間；v表示車輛的投放速率(固定值)。

1.3 目標(biāo)函數(shù)及約束條件

建立的目標(biāo)函數(shù)及約束條件如下：

(1)

(2)

(3)

(4)

Bij=max(Fi(j-1),F(i-1)j)B11=0

(5)

Tij=max(0,F(i-1)j-Fi(j-1))i=2,3,…,d，j=2,3,…,n

(6)

(7)

(8)

目標(biāo)函數(shù)式(1)的含義為一個(gè)最小生產(chǎn)循環(huán)周期內(nèi)各車型經(jīng)過n個(gè)工位等待裝配時(shí)間最短；式(2)可保證每個(gè)工位只能同時(shí)裝配一個(gè)車型；式(3)表示一個(gè)最小生產(chǎn)循環(huán)周期投產(chǎn)車輛數(shù)量是由訂單總量與各車型需求量的最大公約數(shù)確定的，且等于一個(gè)周期內(nèi)每個(gè)車型投產(chǎn)數(shù)量總和；式(4)表示第j工位上的第i個(gè)投產(chǎn)車輛的裝配完成時(shí)刻與開始裝配時(shí)刻的關(guān)系約束；式(5)表示第j工位上的第i個(gè)投產(chǎn)車輛裝配開始時(shí)刻是取第i個(gè)投產(chǎn)車輛在第j-1工位上完成時(shí)刻與第i-1個(gè)投產(chǎn)車輛在第j工位完成時(shí)刻的最大值，第1個(gè)車輛在第1個(gè)工位開始時(shí)刻為0時(shí)刻，后面車輛的投放以此為基準(zhǔn)時(shí)刻；式(6)表示第i個(gè)投產(chǎn)車輛在第j個(gè)工位上的等待時(shí)間，即如果前一個(gè)投產(chǎn)車輛在該工位的完成時(shí)刻大于該投產(chǎn)車輛在前工位的差值，則等待時(shí)間為兩者之差，反之，即在該投產(chǎn)車輛前工位完成裝配之后立即去到下工位進(jìn)行裝配，等待時(shí)間為0；式(7)表示當(dāng)為第1個(gè)投產(chǎn)車輛進(jìn)入裝配線的每個(gè)工位都不需要等待，則值為0；式(8)表示從第二個(gè)投產(chǎn)車輛開始，在一個(gè)最小循環(huán)投產(chǎn)周期內(nèi)，各車型進(jìn)入第1個(gè)工位進(jìn)行裝配的總等待時(shí)間。

2 改進(jìn)遺傳算法設(shè)計(jì)

在標(biāo)準(zhǔn)遺傳算法(Simple Genetic Algorithm，SGA)基礎(chǔ)上提出了一種改進(jìn)遺傳算法(Improved Genetic Algorithm，IGA)。從編碼上，根據(jù)車型字符串特征及MPS約束，設(shè)計(jì)了特有的“定長”實(shí)數(shù)編碼，并且提出一種基于“定序模式”的改進(jìn)自適應(yīng)單點(diǎn)交叉算子以及交換變異算子，避免了不可行解的產(chǎn)生，同時(shí)選擇策略改進(jìn)方面在標(biāo)準(zhǔn)遺傳算法輪盤賭選擇的基礎(chǔ)上引入精英保留策略，保證經(jīng)過遺傳操作優(yōu)秀個(gè)體不被破壞。

2.1 編 碼

編碼依據(jù)混流車型種類為字符串的特點(diǎn)，設(shè)計(jì)了字符與實(shí)數(shù)編碼轉(zhuǎn)換的“定長”實(shí)數(shù)編碼方式。如圖1所示，MPS為20，四種車型A、B、C、D數(shù)量分別為7、6、3、4。即車型A為1-7的定長實(shí)數(shù)范圍，車型B為8-13的定長實(shí)數(shù)范圍，車型C為14-16的定長實(shí)數(shù)范圍，車型D為17-20的定長實(shí)數(shù)范圍。通過隨機(jī)數(shù)產(chǎn)生一排序列與字車型相對應(yīng)。

圖1 “定長”實(shí)數(shù)編碼示意圖

2.2 初始化種群

初始種群的產(chǎn)生好壞不僅會直接決定進(jìn)化的優(yōu)劣，而且優(yōu)良的初始種群將提高算法的運(yùn)行效率。初始種群產(chǎn)生的步驟如下：

Step1生成一個(gè)實(shí)數(shù)編碼車型排序序列，設(shè)置合理的初始種群數(shù)量、最小循環(huán)周期車型數(shù)量(序列長度)參數(shù)。

Step2將車型排序序列中每個(gè)編碼的車型用隨機(jī)數(shù)進(jìn)行隨機(jī)排序生成新的序列，序列個(gè)數(shù)(即初始化種群個(gè)數(shù))由初始種群數(shù)量決定。

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)的數(shù)值大小體現(xiàn)了個(gè)體優(yōu)劣的程度。本文適應(yīng)度函數(shù)設(shè)計(jì)為f(x)=T-g(x)，其中g(shù)(x)為目標(biāo)函數(shù)，T為固定值，這里取值為一天有效工作時(shí)間。目標(biāo)函數(shù)越小，則適應(yīng)度函數(shù)值越大，那么說明個(gè)體越優(yōu)良。

2.4 選擇算子和精英保留

在標(biāo)準(zhǔn)遺傳算法輪盤賭選擇算子的基礎(chǔ)上，引入精英保留策略。因?yàn)槿绻援a(chǎn)生的子代作為父代進(jìn)行交叉、變異等操作產(chǎn)生新個(gè)體時(shí)，會丟失很多優(yōu)良的基因，所以采用精英保留(Elitism)策略能夠更好地保存較優(yōu)個(gè)體而不被丟失，其原理是將當(dāng)前最優(yōu)解復(fù)制到新個(gè)體中，即算法的任何時(shí)刻最優(yōu)解都能被保留。

2.5 交 叉

交叉算子在傳統(tǒng)單點(diǎn)交叉基礎(chǔ)上，提出了一種“定序模式”的改進(jìn)自適應(yīng)單點(diǎn)交叉，其步驟如下：先用隨機(jī)數(shù)確定交叉的位置，即根據(jù)此位置點(diǎn)可以把父代1分為兩個(gè)部分Part1和Part2，在進(jìn)行交叉時(shí)找到要交叉的父代2個(gè)體里與Part1相同的部分，以及與其不相同的車型以外的部分，保持序列順序不變依次替換Part2，形成新一代子代1，而相同的車型部分保持序列順序不變，用父代1的Part1部分依次替換，如圖2所示。

圖2 “定序模式”的單點(diǎn)交叉示意圖

2.6 變 異

變異操作采用交換變異。同樣都采用隨機(jī)函數(shù)的方法確定兩個(gè)變異點(diǎn)point1和point2，最后將對應(yīng)位置的兩個(gè)車型進(jìn)行相互交換，具體操作如圖3所示。

圖3 交換變異操作示意圖

綜上所述，本文設(shè)計(jì)的改進(jìn)遺傳算法思路如圖4所示。

圖4 改進(jìn)遺傳算法的流程圖

3 實(shí)例分析

3.1 混流裝配線現(xiàn)狀

總裝車間是整車廠的重要組成部分，其工藝最為復(fù)雜。它是將汽車零件在經(jīng)過沖壓、焊接、涂裝三大工序后的空車身進(jìn)行裝配。以國內(nèi)某車企的現(xiàn)總裝車間裝配線上的L-CAR、SRV、SGM12及SGM18這四種車型作為分析對象，分別用A、B、C、D字母依次進(jìn)行編號，該混流裝配線上現(xiàn)用投產(chǎn)車型排序以AAAA AAACCCDDDDBBBBBB進(jìn)入裝配線。主要工藝流程及工序內(nèi)容對應(yīng)的編號如圖5所示。

圖5 總裝車間裝配主要工藝流程與工序內(nèi)容

3.2 基礎(chǔ)數(shù)據(jù)

由企業(yè)MES系統(tǒng)獲取訂單信息，可得4種類型產(chǎn)品每天產(chǎn)量分別是126、108、54、72臺，共計(jì)360臺?？傻靡粋€(gè)MPS循環(huán)內(nèi)4種產(chǎn)品比例為7 ∶6 ∶3 ∶4。分早、中2班生產(chǎn)，每班的實(shí)際生產(chǎn)時(shí)間為7.6小時(shí)。根據(jù)上述工藝流程及實(shí)際企業(yè)工廠布局，把30道工序劃分為8個(gè)工位,相關(guān)數(shù)據(jù)如表1所示。

表1 裝配線各工位及四種車型不同工位的裝配時(shí)間

3.3 MATLAB對模型求解

將SGA和IGA分別在通用計(jì)算軟件MATLAB R2012a上運(yùn)算，初始化參數(shù)設(shè)置如下：種群數(shù)量為100，交叉概率Pc=0.9，變異概率Pm=0.05，進(jìn)化的最大代數(shù)為100，得到的適應(yīng)度進(jìn)化曲線如圖6所示。前者得到最優(yōu)排序?yàn)?、7、8、9、13、3、4、19、15、10、16、2、6、20、17、11、14、5、18、12，解碼得AABBBAADCBCAADDBCADB，適應(yīng)度函數(shù)值為54 036，目標(biāo)函數(shù)最小值684；而后者得到的最優(yōu)排序?yàn)?、1、4、6、13、10、9、17、12、18、20、2、8、16、15、5、7、14、19、11，解碼得為AAAABBBDBDDABCCAACDB，此時(shí)，適應(yīng)度函數(shù)值為54 311，目標(biāo)函數(shù)最小值為409?；谏鲜鰯?shù)據(jù)對比分析可得，本文提出的IGA在該問題的優(yōu)化上比SGA更有效。

圖6 適應(yīng)度進(jìn)化曲線

4 汽車混流裝配線的Flexsim仿真

4.1 Flexsim仿真軟件

Flexsim仿真軟件是美國 Flexsim公司開發(fā)的一款三維的通用物流仿真軟件，采用C++語言開發(fā)，支持離散系統(tǒng)和連續(xù)流體系統(tǒng)的建模。文獻(xiàn)[12]運(yùn)用Flexsim仿真軟件，可以較容易建立上述各工位仿真三維模型，并通過設(shè)置各實(shí)體(即工位)具體參數(shù)，運(yùn)行模型得出有效的仿真數(shù)據(jù)，最終優(yōu)化設(shè)計(jì)或改造方案。因此，采用Flexsim軟件建立該裝配線仿真模型，這里使用的版本為Flexsim 2018。

4.2 仿真元素定義

仿真模型里的實(shí)體代表著實(shí)際生產(chǎn)中的生產(chǎn)元素，具體定義如表2所示。

表2 仿真元素定義

4.3 基于Flexsim的汽車混流裝配線仿真模型

1) 建立混流裝配線的Flexsim仿真模型。

根據(jù)所劃分的8個(gè)工位，同時(shí)為了更好模擬投產(chǎn)車型等待裝配的狀態(tài)，在兩個(gè)工位之前都加入一個(gè)暫存區(qū)，依次生成所有實(shí)體并修改每個(gè)實(shí)體的名稱以匹配8個(gè)工位內(nèi)容，并進(jìn)行“A”連接，模型如圖7所示。

圖7 汽車混流裝配線的Flexsim仿真

2) 各實(shí)體的參數(shù)設(shè)置。

(1) 對發(fā)生器進(jìn)行參數(shù)設(shè)置。該仿真模型以固定投產(chǎn)方式投產(chǎn)，故在發(fā)生器的到達(dá)方式選項(xiàng)卡下選擇“到達(dá)時(shí)間表”，并在ArrivalTime列每隔145 s設(shè)置一個(gè)到達(dá)時(shí)刻。同時(shí)按照MATLAB求解的投產(chǎn)序列進(jìn)行設(shè)置，具體ItemType列的1、2、3、4分別對應(yīng)A、B、C、D種車型，即某車企L-CAR、SRV、SGM12及SGM18這四種車型。MPS為20，Arrivals設(shè)置為21，最后1行參數(shù)設(shè)置主要是保證其按照一個(gè)MPS進(jìn)行循環(huán)，其數(shù)量Quantity設(shè)置為0，ItemType設(shè)置為一個(gè)MPS中的第一個(gè)車輛類型，即設(shè)置為1。同時(shí)在發(fā)生器離開觸發(fā)里添加代碼，將4種類型的顏色分別設(shè)置為藍(lán)色、黃色、綠色、黑色。根據(jù)每天訂單數(shù)為360臺，設(shè)置關(guān)閉和打開端口，其條件為getoutput(current)==359，發(fā)生器到達(dá)時(shí)間表部分參數(shù)設(shè)置如圖8所示。

圖8 發(fā)生器到達(dá)時(shí)間表部分參數(shù)設(shè)置

(2) 設(shè)置處理器的參數(shù)。對8個(gè)工位處理器實(shí)體的加工時(shí)間分別進(jìn)行設(shè)置，具體參數(shù)的設(shè)置，根據(jù)表1的四種不同車型裝配時(shí)間不同，設(shè)置4個(gè)case，每個(gè)case分別對應(yīng)一個(gè)車型裝配時(shí)間。

(3) 設(shè)置傳送帶的參數(shù)。根據(jù)實(shí)際生產(chǎn)中全天訂單完成數(shù)量進(jìn)行設(shè)置，即當(dāng)傳送帶送走359臺車輛，模型自動停止仿真，代碼設(shè)置為if(getoutput(current)==359)stop；

(4) 設(shè)置統(tǒng)計(jì)數(shù)據(jù)，使用Flexsim中Dashboards的停留時(shí)間模塊，并選擇按類型統(tǒng)計(jì)停留時(shí)間進(jìn)行仿真分析，分別選中每個(gè)暫存區(qū)，將類型標(biāo)簽設(shè)置為ItemType，值數(shù)據(jù)類型設(shè)為number。

4.4 模型的運(yùn)行

按照上述步驟建立的仿真模型，點(diǎn)擊“運(yùn)行”按鈕運(yùn)行該模型，仿真模型運(yùn)行完成之后，點(diǎn)擊設(shè)置的統(tǒng)計(jì)數(shù)據(jù)中Dashboards的按類型統(tǒng)計(jì)停留時(shí)間模塊，從高級選項(xiàng)卡的查看表中記錄數(shù)據(jù)，并計(jì)算得出完成全天訂單總等待時(shí)間。同理按照上述操作再對SGA得出的投產(chǎn)排序及該企業(yè)實(shí)際生產(chǎn)線上現(xiàn)有汽車車型投產(chǎn)排序進(jìn)行仿真。三種不同的車型投產(chǎn)順序仿真實(shí)驗(yàn)結(jié)果如表3所示。

表3 仿真實(shí)驗(yàn)結(jié)果

5 結(jié) 語

針對汽車混流總裝線投產(chǎn)排序問題，建立了以一個(gè)循環(huán)周期內(nèi)的車型經(jīng)過各工位等待裝配的總時(shí)間最短為目標(biāo)的數(shù)學(xué)模型。通過對某企業(yè)混流總裝線的工藝流程、車間布局等進(jìn)行分析，把劃分的工位以及每個(gè)工位的標(biāo)準(zhǔn)工時(shí)作為數(shù)據(jù)基礎(chǔ)。基于MATLAB平臺開發(fā)了算法程序求解該模型，并將標(biāo)準(zhǔn)遺傳算法與本文改進(jìn)的遺傳算法進(jìn)行了對比分析，發(fā)現(xiàn)所提出的IGA更有效。最后運(yùn)用Flexsim軟件分別對原投產(chǎn)排序、SGA與IGA得出的排序進(jìn)行了仿真，發(fā)現(xiàn)IGA得出的最優(yōu)排序完成全天訂單總等時(shí)間最短，驗(yàn)證了該算法的有效性。

本文研究對制造企業(yè)實(shí)施JIT，做好均衡化生產(chǎn)，確保產(chǎn)品投產(chǎn)排序的有效性和可行性，順利推進(jìn)混流生產(chǎn)以滿足顧客多樣化需求具有指導(dǎo)性意義。