王炳剛

(河南城建學(xué)院 工商學(xué)院，河南省 平頂山 467036)

?

緩沖區(qū)容量約束下發(fā)動機(jī)混流裝配線排序研究

王炳剛

(河南城建學(xué)院 工商學(xué)院，河南省 平頂山 467036)

摘要：為解決緩沖區(qū)容量約束下發(fā)動機(jī)混流裝配排序問題，以關(guān)鍵部件消耗均勻化和最大完工時(shí)間最小化為目標(biāo)，建立了優(yōu)化數(shù)學(xué)模型，設(shè)計(jì)了一種多目標(biāo)遺傳算法，采用了混合交叉算子和啟發(fā)式變異方法，并設(shè)計(jì)了基于帕累托分級和共享函數(shù)的適應(yīng)度函數(shù)，將多目標(biāo)遺傳算法和多目標(biāo)模擬退火算法的優(yōu)化結(jié)果進(jìn)行了比較。研究結(jié)果表明，多目標(biāo)遺傳算法在滿意度和計(jì)算效率方面均優(yōu)于多目標(biāo)模擬退火算法，是一種有效的混流裝配線排序問題求解算法。

關(guān)鍵詞：排序； 發(fā)動機(jī)； 混流裝配線； 緩沖區(qū)； 多目標(biāo)遺傳算法

混流裝配線排序問題已成為學(xué)者研究的熱點(diǎn)。文獻(xiàn)[1]以最小化超載時(shí)間與空閑時(shí)間的費(fèi)用為目標(biāo)，采用免疫粒子群優(yōu)化算法求解，但該研究沒有考慮其他影響裝配線效率的因素；文獻(xiàn)[2]建立了以最小化超載時(shí)間、最小化調(diào)整時(shí)間和最小化產(chǎn)品變化率為目標(biāo)的優(yōu)化模型，利用混合群優(yōu)化算法求解，文獻(xiàn)[3]則對文獻(xiàn)[2]中的目標(biāo)通過遺傳算法進(jìn)行求解，這兩種算法對問題的求解都取得了一定的效果，但未對這三個(gè)目標(biāo)的沖突和競爭進(jìn)行分析；文獻(xiàn)[4]同時(shí)考慮零部件消耗速率均勻化和最小生產(chǎn)循環(huán)周期最短兩個(gè)目標(biāo)，采用加權(quán)和的方法把多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，設(shè)計(jì)了一種基于遺傳算法和模擬退火算法的混合求解方法；文獻(xiàn)[5]設(shè)計(jì)了改進(jìn)的離散群優(yōu)化算法求解以最小超載、空閑和調(diào)整時(shí)間的費(fèi)用為目標(biāo)的多目標(biāo)優(yōu)化模型；文獻(xiàn)[6]采用加權(quán)和的方法將以最小化調(diào)整時(shí)間和最小化超載時(shí)間與空閑時(shí)間為目標(biāo)的優(yōu)化問題轉(zhuǎn)化為單目標(biāo)問題，提出了一種混合人工蜂群算法；文獻(xiàn)[7]建立了以最小化工作站閑置/超載總成本、產(chǎn)品變化率和產(chǎn)品切換總時(shí)間為目標(biāo)的混流裝配線排序多目標(biāo)優(yōu)化模型，并設(shè)計(jì)了一種改進(jìn)多目標(biāo)貓群優(yōu)化算法進(jìn)行求解；文獻(xiàn)[8]同時(shí)考慮零部件消耗均勻化和最小生產(chǎn)循環(huán)周期最短兩個(gè)優(yōu)化目標(biāo)，提出了一種多目標(biāo)遺傳算法，該研究沒有考慮緩沖區(qū)容量的約束，而且只是將多目標(biāo)優(yōu)化的結(jié)果與標(biāo)準(zhǔn)遺傳算法單目標(biāo)優(yōu)化結(jié)果進(jìn)行了比較；其他有關(guān)混流裝配線排序問題的研究可參考綜述性文獻(xiàn)[9-10]。盡管裝配線排序問題研究較多，但是對緩沖區(qū)容量約束下，同時(shí)考慮關(guān)鍵部件消耗均勻化和完工時(shí)間最小目標(biāo)的混流裝配線排序問題研究甚少，因此，本文設(shè)計(jì)新的多目標(biāo)優(yōu)化算法對該問題進(jìn)行求解。

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

1.1關(guān)鍵部件消耗均勻化

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

其中，xjk為裝配前k個(gè)產(chǎn)品消耗部件j的數(shù)量，Nj為裝配完所有產(chǎn)品消耗部件j的數(shù)量，di為產(chǎn)品i的訂單需求數(shù)量，ti是產(chǎn)品i的多余庫存量，如果產(chǎn)品i被安排在第k個(gè)位置進(jìn)行裝配，則hik為1，否則hik為0，yik表示前k個(gè)產(chǎn)品中產(chǎn)品i的數(shù)量，bij為一件產(chǎn)品i需要部件j的數(shù)量。如果部件j的消耗是均勻的，那么，當(dāng)完成第k件產(chǎn)品后，部件j消耗的數(shù)量應(yīng)該等于(k×Nj/K)。優(yōu)化目標(biāo)(式(1))就是盡可能使得當(dāng)完成第k件產(chǎn)品后，部件j實(shí)際消耗的數(shù)量xjk盡可能地與(k×Nj/K)接近。

1.2最長完工時(shí)間最小化

(7)

s.t.

(8)

(9)

(10)

(11)

其中，SP(K)M和AP(K)M分別為最后一件產(chǎn)品P(K)在最后一個(gè)工位M上開始裝配的時(shí)間和所需的裝配時(shí)間，Bm為工位m和工位m-1之間的緩沖區(qū)容量。

2多目標(biāo)遺傳算法(MOGA)

2.1算法步驟

S1: 產(chǎn)生初始種群P(0)，種群規(guī)模為Mg，令進(jìn)化代數(shù)g=0。

S2: 對P(g)中的個(gè)體進(jìn)行Pareto排序，將排序級別為1的個(gè)體加入非支配解集Gset中，非支配解集規(guī)模為Ng，初始為空，當(dāng)Gset中個(gè)體的數(shù)量超過Ng時(shí)，要對其進(jìn)行修剪。

S3: 計(jì)算P(g)中各個(gè)體的小生境計(jì)數(shù)。

S4: 計(jì)算P(g)中各個(gè)體的適應(yīng)度值。

S5: 進(jìn)行選擇、混合交叉和啟發(fā)式變異操作。

S6: 保留精英個(gè)體。

S7:g=g+1，如果g>G，則輸出Gset中所有的非支配解；否則，轉(zhuǎn)S2。

2.2關(guān)鍵步驟的實(shí)現(xiàn)

1)編碼：采用整數(shù)編碼的方式，每種產(chǎn)品用一個(gè)唯一的整數(shù)代替。

2)產(chǎn)生初始種群。

S1: 采用NEH方法[11]產(chǎn)生1個(gè)臨時(shí)裝配序列，其余(Mg-1)個(gè)臨時(shí)裝配序列隨機(jī)產(chǎn)生。

S2: 如果產(chǎn)品的多余庫存量多于臨時(shí)序列中該產(chǎn)品的計(jì)劃數(shù)量，則刪除所有該產(chǎn)品，否則，從前往后在臨時(shí)裝配序列中刪除與多余庫存量相同數(shù)量的該產(chǎn)品，則剩下的各產(chǎn)品型號的組合即為實(shí)際的裝配序列。

3)帕累托分級。

S1: 令級數(shù)r=1。

S2: 任選候選個(gè)體xc，如果xc不被P(g)中其他所有個(gè)體支配，則令其級數(shù)ran(xc)=r。重復(fù)此步驟，直到P(g)中個(gè)體都被選作候選個(gè)體為止。

S3: 刪除所有級數(shù)為r的個(gè)體。

S4: 如果P(g)中仍有尚未確定級數(shù)的個(gè)體，則令r=r+1，轉(zhuǎn)S2。

4)修剪：當(dāng)Gset的規(guī)模超過設(shè)定值Ng時(shí)，則計(jì)算個(gè)體的小生境計(jì)數(shù)，從Gset中刪除具有最大小生境計(jì)數(shù)的個(gè)體，如果多個(gè)個(gè)體的小生境計(jì)數(shù)相同時(shí)，則隨機(jī)刪除一個(gè)，重復(fù)此步驟，直至Gset的規(guī)模等于設(shè)定值Ng。

5)小生境計(jì)數(shù)。

S1: 按下式確定個(gè)體之間的距離

(12)

其中，f1(xa)、f2(xa)、f1(xb)、f2(xb)分別是個(gè)體xa和xb的目標(biāo)函數(shù)值。

S2: 按下式計(jì)算共享函數(shù)值

sh(fdab)=1-fdab/Os; fdab≤Os0, otherwise。{

(13)

其中，Os是共享參數(shù)。

S3: 按下式計(jì)算小生境計(jì)數(shù)

(14)

6)適應(yīng)度：因?yàn)榉N群中個(gè)體的帕累托級數(shù)值越小，則該個(gè)體的質(zhì)量越好，小生境計(jì)數(shù)越小，則種群中個(gè)體的分布性越好，所以為了使具有較小帕累托級數(shù)值和較小小生境計(jì)數(shù)的個(gè)體獲得較高的適應(yīng)度，按下式計(jì)算個(gè)體適應(yīng)度fit(xa)：

(15)

7)選擇。

S1: 按照適應(yīng)度值由高到低的順序，選擇Mg×Ps個(gè)優(yōu)良個(gè)體直接加入下一代種群，比例值Ps事先設(shè)定。

S2: 對于種群中每一個(gè)未被選中的個(gè)體，采用隨機(jī)的方式產(chǎn)生一個(gè)新個(gè)體，如果新個(gè)體支配該未被選中的個(gè)體，則將新個(gè)體加入下一代種群，如果在連續(xù)10次循環(huán)中仍不能找到該支配解，則也將該未被選中的個(gè)體直接加入下一代種群。

8)混合交叉。

對于每一對按照交叉概率Pc選擇的父本個(gè)體，隨機(jī)從LOX，PMX和modOX 3種交叉算子[12]中任選一種進(jìn)行交叉操作，然后根據(jù)個(gè)體適應(yīng)度值由高到低的順序從兩個(gè)子代個(gè)體和兩個(gè)父代個(gè)體中選擇兩個(gè)最優(yōu)個(gè)體代替種群中的2個(gè)父本個(gè)體。

9)啟發(fā)式變異。

S1:在每一個(gè)根據(jù)變異概率Pm選擇的進(jìn)行變異操作的個(gè)體中任選三個(gè)基因。

S2:任意交換3個(gè)基因的位置，產(chǎn)生6個(gè)鄰域個(gè)體。

S3:從6個(gè)鄰域個(gè)體中選擇適應(yīng)度值最大的個(gè)體作為變異結(jié)果。

10)精英策略。

S1: 根據(jù)適應(yīng)度值對臨時(shí)種群Pt(g)和Gset中的個(gè)體進(jìn)行降序排列。

S2: 選擇Gset中最優(yōu)的Q0個(gè)個(gè)體替換Pt(g)中最差的Q0個(gè)個(gè)體。

3多目標(biāo)模擬退火算法(MOSA)

3.1算法步驟

S1: 隨機(jī)產(chǎn)生初始種群Sset, 種群規(guī)模為Ms，令循環(huán)次數(shù)t=0，初始溫度Te=T0。

S2: 從Sset中隨機(jī)選取一個(gè)當(dāng)前個(gè)體。

S3: 如果終止條件(Tetmax)滿足，則對Sset中的個(gè)體進(jìn)行Pareto分級，輸出所有級別為1的非支配個(gè)體，否則執(zhí)行以下步驟。

S4: 循環(huán)以下步驟Ni次。

1)采用INV[12]算子，由當(dāng)前個(gè)體產(chǎn)生一個(gè)候選個(gè)體。

2)如果候選個(gè)體與Sset中的所有個(gè)體都不互相被支配，則將該候選個(gè)體作為新的當(dāng)前個(gè)體，同時(shí)將該候選個(gè)體加入Sset中，并對Sset進(jìn)行修剪；否則，如果該候選個(gè)體支配Sset中的一個(gè)或多個(gè)個(gè)體，則用該候選個(gè)體替換Sset中第一個(gè)找到的被支配個(gè)體，同時(shí)將該候選個(gè)體作為新的當(dāng)前個(gè)體；否則，如果Metropolis準(zhǔn)則是“真”，則用該候選個(gè)體作為新的當(dāng)前個(gè)體。

S5：Te=Te×Cr，t=t+1，轉(zhuǎn)S3。

3.2修剪

當(dāng)Sset的規(guī)模超過設(shè)定值Ns時(shí)，計(jì)算每個(gè)個(gè)體的小生境計(jì)數(shù)，刪除具有最大小生境計(jì)數(shù)的個(gè)體，如果多個(gè)個(gè)體的小生境計(jì)數(shù)相同時(shí)，則隨機(jī)刪除一個(gè)，重復(fù)此過程，直至Sset中規(guī)模等于設(shè)定值Ns。

3.3Metropolis準(zhǔn)則

Metropolis標(biāo)準(zhǔn)表明被支配個(gè)體被接受的概率，該概率值按下式計(jì)算：

(16)

式中，ΔE是候選個(gè)體與Sset中支配它的所有個(gè)體間的最小距離，Kb為Boltzman常數(shù)。對于被支配的候選個(gè)體，首先計(jì)算Pa，然后隨機(jī)產(chǎn)生u(0≤u≤1)，如果u

4優(yōu)化結(jié)果的比較

本文采用了滿意度函數(shù)的方法用于多目標(biāo)算法優(yōu)化結(jié)果的比較。非支配解集中的每個(gè)個(gè)體的滿意度按照下式計(jì)算。

(17)

其中，fn1和fn2分別是個(gè)體n的第一個(gè)和第二個(gè)目標(biāo)函數(shù)值，fb1和fb2分別是非支配解集中第一個(gè)目標(biāo)和第二個(gè)目標(biāo)的最大值。非支配解集的滿意度按下式計(jì)算，N是非支配解集中個(gè)體的總數(shù)。

(18)

5實(shí)例驗(yàn)證

以某汽車制造企業(yè)發(fā)動機(jī)裝配線的實(shí)際數(shù)據(jù)驗(yàn)證所設(shè)計(jì)多目標(biāo)優(yōu)化算法的優(yōu)化性能。該發(fā)動機(jī)裝配線共有70個(gè)工位，相鄰工位間緩沖區(qū)容量分別為：(1，2，1，2，1，1，3，1，2，1，1，1，2，1，2，1，1，3，1，2，1，1，1，2，1，2，1，1，3，1，2，1，1，1，2，1，2，1，1，3，1，2，1，1，1，2，1，2，1，1，3，1，2，1，1，1，2，1，2，1，1，3，1，2，1，1，2，1，2)，可混流生產(chǎn)5種型號的發(fā)動機(jī)，每臺發(fā)動機(jī)均需使用4種關(guān)鍵部件，即缸體、缸蓋、曲軸和凸輪軸，每種關(guān)鍵部件有多種型號。發(fā)動機(jī)訂單需求量分別為(60，70，40，80，40)，5種發(fā)動機(jī)的多余庫存分別為10臺，產(chǎn)品-部件矩陣如表1所示，作業(yè)時(shí)間如表2所示。從訂單需求量中減去每種發(fā)動機(jī)計(jì)劃期初多余庫存量，可以看出，最小生產(chǎn)循環(huán)為(5，6，3，7，3)，重復(fù)10次生產(chǎn)即可滿足訂單需求。

表1　產(chǎn)品-部件消耗矩陣

表2　作業(yè)時(shí)間

算法采用Matlab編程實(shí)現(xiàn)，在PC機(jī)(Pentium (R) 4, CPU 2.80 GHz, 2G)上運(yùn)行，針對不同的算法參數(shù)組合經(jīng)過大量的計(jì)算實(shí)驗(yàn)，選擇的MOGA算法參數(shù)：Mg=50，G=50，Pc=0.85，Pm=0.20，Ng=10，Os=20，Q0=2，Ps=0.20；MOSA算法參數(shù)：T0=50，Ts=1，Co=0.95，kmax=50，Ni=30，Ms=50，Ns=10，Os=20，Kb=0.005。

多目標(biāo)遺傳算法的優(yōu)化結(jié)果和個(gè)體滿意度如表3所示，計(jì)算時(shí)間642 s，多目標(biāo)模擬退火算法的優(yōu)化結(jié)果和個(gè)體滿意度如表4所示，計(jì)算時(shí)間723 s。

表3　MOGA算法優(yōu)化結(jié)果

表4　MOSA算法優(yōu)化結(jié)果

從表3和表4可以看出：1) MOGA找到的非支配解的個(gè)數(shù)多于MOSA找到的非支配解的個(gè)數(shù)；2) 根據(jù)公式(18)計(jì)算兩種算法優(yōu)化所得的非支配解集的滿意度值，結(jié)果分別為0.6501和0.5059，說明MOGA優(yōu)化結(jié)果的滿意度要高于MOSA優(yōu)化結(jié)果的滿意度；3) MOGA的CPU耗時(shí)要短于MOSA，說明MOGA的優(yōu)化效率更高。

6結(jié)論

1)以關(guān)鍵部件消耗均勻化和最大完工時(shí)間最小化為目標(biāo)，建立了緩沖區(qū)容量約束下發(fā)動機(jī)混流裝配排序問題數(shù)學(xué)模型，設(shè)計(jì)了兩種多目標(biāo)優(yōu)化算法用于問題的求解。

2)結(jié)合實(shí)例，比較了兩種算法的優(yōu)化結(jié)果，發(fā)現(xiàn)在解的數(shù)量、滿意度和計(jì)算效率3個(gè)方面，多目標(biāo)遺傳算法均具有優(yōu)勢。

參考文獻(xiàn)：

[1]鄭永前，王永生. 免疫粒子群算法在混流裝配線排序中的應(yīng)用[J]．工業(yè)工程與管理，2011, 16(4)：16-20.

ZHENG Yongqian, WANG Yongsheng. An immunity particle swarm sequencing algorithm for mixed-model assembly lines[J]. Industrial Engineering and Management, 2011, 16(4): 16-20.

[2]HYUN C J, KIM Y, KIM Y K. A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines[J]. Computers & Operations Research, 1998, 25(7/8): 675-690.

[3]劉煒琪，劉瓊，張超勇，等．基于混合粒子群算法求解多目標(biāo)混流裝配線排序[J]．計(jì)算機(jī)集成制造系統(tǒng)，2011，17(12)：2590-2598.

LIU Weiqi, LIU Qiong, ZHANG Chaoyong, et al. Hybrid particle swarm optimization for multi-objective sequencing problem in mixed model assembly lines[J]. Computer Integrated Manufacturing Systems, 2011, 17(12): 2590-2598.

[4]蘇平，于兆勤. 基于混合遺傳算法的混合裝配線排序問題研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2008, 14(5): 1001-1007.

SU Ping, YU Zhaoqin. Hybrid genetic algorithms for sequencing problems in mixed model assembly lines[J]. Computer Integrated Manufacturing Systems, 2008, 14(5): 1001-1007.

[5]董巧英，闞樹林，桂元坤，等．基于改進(jìn)離散微粒群優(yōu)化算法的混流裝配線多目標(biāo)排序[J]. 系統(tǒng)仿真學(xué)報(bào)，2009, 21(22)：7103-7108.

DONG Qiaoying, KAN Shulin, GUI Yuankun, et al. Mixed model assembly line multi-objective sequencing based on modified discrete particle swarm optimization algorithm[J]. Journal of System Simulation, 2009, 21(22): 7103-7108.

[6]魯建廈，翁耀煒，李修琳，等. 混合人工蜂群算法在混流裝配線排序中的應(yīng)用[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2014，20(1)：121-127.

LU Jiansha, WENG Yaowei, LI Xiulin, et al. Application of hybrid artificial bee colony algorithm in mixed assembly lines sequencing[J]. Computer Integrated Manufacturing Systems, 2014, 20(1): 121-127.

[7]劉瓊，范正偉，張超勇，等. 基于多目標(biāo)貓群算法的混流裝配線排序問題[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2014，20(2)：333-342.

LIU Qiong, FAN Zhengwei, ZHANG Chaoyong, et al. Mixed model assembly line sequencing problem based on multi-objective cat swarm optimization[J]. Computer Integrated Manufacturing Systems, 2014, 20(2): 333-342.

[8]YU J F, YIN Y H, CHEN Z N. Scheduling of an assembly line with a multi-objective genetic algorithm[J]. International Journal of Advanced Manufacturing Technology, 2006, 28(5): 551-555.

[9]BOYSEN N, FLIEDNER M, SCHOLL A. Sequencing mixed-model assembly lines: survey, classification and model critique[J]. European Journal of Operational Research, 2009, 192(2): 349-373.

[10]JIMENEZ P. Survey on assembly sequencing: a combinatorial and geometrical perspective[J]. Journal of Intelligent Manufacturing, 2013, 24(2): 235-250.

[11]WANG L, ZHANG L, ZHENG D Z.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers[J], Computers & Operations Research, 2006, 33(10): 2960-2971.

[12]WANG L, ZHENG D Z. An effective hybrid heuristic for flow shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2003, 21(1): 38-44.

Sequencing Engine Mixed-Model Assembly Lines under Buffer Size Constraints

WANG Binggang

(Business School of Henan University of Urban Construction，Pingdingshan 467036，China)

Abstract：Two optimization objectives, minimizing the variation in crucial parts consumption and the makespan, are simultaneously considered to study the sequencing problems in car engine mixed-model assembly lines under limited intermediate buffer size constraints. The mathematical models are presented. Since the problem addressed is NP-hard, a multi-objective genetic algorithm is proposed, in which hybrid crossover operators and a heuristic mutation method are adopted, and the Pareto ranking method and the sharing function method are employed to evaluate the individuals′ fitness. The optimization result of the multi-objective genetic algorithm is compared with that of a multi-objective annealing algorithm. The comparison result illustrates that the multi-objective genetic algorithm proposed outperforms the multi-objective annealing algorithm in respect of the solutions′ desirability and also the computation efficiency. The multi-objective genetic algorithm is an efficient algorithm for solving the sequencing problem in mixed-model assembly lines under buffer size constraints.

Key words：sequencing; engine; mixed-model assembly line; buffer; multi-objective genetic algorithm

中圖分類號：TH16

文獻(xiàn)標(biāo)志碼：A

文章編號：1007-7375(2016)01- 0081- 05

doi:10.3969/j.issn.1007- 7375.2016.01.012

作者簡介：王炳剛(1974-)，男，河南省人，副教授,博士，主要研究方向?yàn)樯a(chǎn)調(diào)度、智能算法.

基金項(xiàng)目：河南省軟科學(xué)計(jì)劃資助項(xiàng)目(152400410476)；河南城建學(xué)院博士基金資助項(xiàng)目(2012JBS007)

收稿日期：2014- 10- 29