王炳剛

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

?

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

王炳剛

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

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

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

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

1數(shù)學模型

1.1關鍵部件消耗均勻化

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

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

1.2最長完工時間最小化

(7)

s.t.

(8)

(9)

(10)

(11)

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

2多目標遺傳算法(MOGA)

2.1算法步驟

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

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

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

S4: 計算P(g)中各個體的適應度值。

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

S6: 保留精英個體。

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

2.2關鍵步驟的實現(xiàn)

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

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

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

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

3)帕累托分級。

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

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

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

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

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

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

S1: 按下式確定個體之間的距離

(12)

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

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

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

(13)

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

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

(14)

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

(15)

7)選擇。

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

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

8)混合交叉。

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

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

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

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

S3:從6個鄰域個體中選擇適應度值最大的個體作為變異結果。

10)精英策略。

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

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

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

3.1算法步驟

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

S2: 從Sset中隨機選取一個當前個體。

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

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

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

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

S5：Te=Te×Cr，t=t+1，轉S3。

3.2修剪

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

3.3Metropolis準則

Metropolis標準表明被支配個體被接受的概率，該概率值按下式計算：

(16)

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

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

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

(17)

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

(18)

5實例驗證

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

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

表2　作業(yè)時間

算法采用Matlab編程實現(xiàn)，在PC機(Pentium (R) 4, CPU 2.80 GHz, 2G)上運行，針對不同的算法參數(shù)組合經(jīng)過大量的計算實驗，選擇的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。

多目標遺傳算法的優(yōu)化結果和個體滿意度如表3所示，計算時間642 s，多目標模擬退火算法的優(yōu)化結果和個體滿意度如表4所示，計算時間723 s。

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

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

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

6結論

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

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

參考文獻：

[1]鄭永前，王永生. 免疫粒子群算法在混流裝配線排序中的應用[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]劉煒琪，劉瓊，張超勇，等．基于混合粒子群算法求解多目標混流裝配線排序[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]. 計算機集成制造系統(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]董巧英，闞樹林，桂元坤，等．基于改進離散微粒群優(yōu)化算法的混流裝配線多目標排序[J]. 系統(tǒng)仿真學報，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]魯建廈，翁耀煒，李修琳，等. 混合人工蜂群算法在混流裝配線排序中的應用[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]劉瓊，范正偉，張超勇，等. 基于多目標貓群算法的混流裝配線排序問題[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

文獻標志碼：A

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

doi:10.3969/j.issn.1007- 7375.2016.01.012

作者簡介：王炳剛(1974-)，男，河南省人，副教授,博士，主要研究方向為生產(chǎn)調度、智能算法.

基金項目：河南省軟科學計劃資助項目(152400410476)；河南城建學院博士基金資助項目(2012JBS007)

收稿日期：2014- 10- 29