基于遍歷搜索與遺傳算法的生產線平衡優化

方景芳 徐艷凱

(蘭州理工大學機電工程學院 甘肅 蘭州 730050)

?

基于遍歷搜索與遺傳算法的生產線平衡優化

方景芳 徐艷凱

(蘭州理工大學機電工程學院 甘肅 蘭州 730050)

對L公司兩類生產線狀況進行分析，建立了描述生產線平衡的數學模型，以最小化生產線工作站數和最小負荷平滑指數為目標，對生產線進行優化。對于簡單的生產線，通過遍歷搜索算法, 首先找出所有可行的作業加工順序，然后求出最小的工作站數和最小平滑指數及相應的作業加工順序。對于復雜的生產線，利用遍歷搜索得到的結果作為遺傳算法的種群，應用遺傳算法，求出最小的工作站數和最小平滑指數及相應的作業加工順序。解決了該公司的生產線平衡問題，也說明了遍歷算法和遺傳算法在生產線優化中的有效性。

生產線平衡 工作站數 遍歷算法 遺傳算法 生產線優化

0 引 言

生產線平衡是調整生產線中各工作站的作業，以使各個工作站的作業時間盡可能和生產節拍相等或相近。因為當生產線中的各個工作站的加工時間不平衡時，那么總工作時間較長的工作站中必然存在制品嚴重積壓，而后續的工作站處于空閑狀態，從而使整條生產線不能順暢進行。對生產線平衡的優化，主要解決兩類問題[1]，第一類是在給定生產線工作量的情況下，確定生產節拍，對生產線中工作站的數量進行優化，使工作站的數量最小化；第二類是確定生產線的工作站數量，盡可能減小生產線的生產節拍，從而最大化生產線的加工能力。實踐中發現，對于個性化定制的產品，客戶總是會給出一個加工時間，這樣每類產品便有了固定的生產節拍。實際面臨一個準時交貨的問題，為了保證產品的交貨期，使得生產順利進行，就要進行各工作站時間的平衡，并且在進行系統優化的過程中，還要綜合考慮對作業人員進行動素分析、局部仿真，以及對物流路徑等進行分析。文獻[2]采用工業工程基本方法對生產線平衡進行了分析，并提出了優化方向。文獻[3-4]建立了混流生產線的仿真模型，對瓶頸問題、生產線平衡進行了研究。遺傳算法屬于啟發式優化方法，通過建立數學模型來尋找問題的最優解，文獻[5-7]在對生產線分析的基礎上，設計了遺傳算法，結果生產線平衡率得到了提高，解決了生產線的不平衡問題。文獻[8-10]在平衡優化的過程中采用改進遺傳算法，平衡優化效果明顯。本文選擇參加生產實踐的L公司生產線進行了第一類問題的實驗。對于公司A生產線，系統不太復雜，且工段數量不是很大，潛在的作業排序數量也是有限，若應用遺傳算法會造成大量重復迭代計算。為了合理解決這類問題，設計了遍歷搜索算法；而對于較復雜的平行生產線B生產線，用遍歷搜索效率就太低了，這時往往用遺傳算法求解，遺傳算法能處理群體中多個個體，具有良好的全局搜索性能。所以對L公司的生產線本文采用遍歷搜索和遺傳算法進行優化研究。

1 L公司A生產線問題的分析

L公司A生產線生產的下拼模塊，市場需求量大，并且生產過程中存在加工難度較大、加工效率低的狀況。本文選擇A生產線下拼模塊的6個工作站進行調查研究，并結合標準作業指導書來分析這6個工作站的作業要素。統計數據顯示，下拼模塊每天生產1件產品，每天生產7小時，所以該段生產線的生產節拍為7小時。而從整條生產線的情況來看，各工序段忙閑不等，各工序間聯系不夠緊密，嚴重影響了生產系統效率，需要進行生產線平衡的改善。表1表示該段生產線上各個工作站上的作業時間總和。

表1 各工作站作業時間表 min

按照下式計算該生產線的平衡率：

(1)

得到：

對這一條生產線而言，平衡率達到85%才算合格，平衡損失率應控制在15%以下。過低的平衡率，表明生產線有相當大的改善空間。這段生產線的平衡率僅為59%，遠遠達不到合格的水平。說明該生產線各工作站之間的作業負荷量很不均衡，平衡率有待提高。

2 數學模型的建立

數學理論與實際生產系統相結合，利用生產系統參數進行數學建模，并提出高效的數值求解方法，是生產線平衡優化的基本理論框架。考查一條生產線是否合理，不僅要看其工位的數目是否最小，還要看生產線的負荷是否均衡。以作業順序圖和節拍為基礎，尋求生產線工作地數量最小的工作方案，可由式(2)和式(3)來描述：

(2)

minF1=αm+βF

(3)

式中，CT為生產節拍；Sk為第k個工作站的總加工時間；m表示工作站的數量；F表示生產線的平滑指數；F1表示目標函數是工作站數和生產線平衡指數的線性組合，其中α和β用以分配工作站數和平滑指數在優化目標函數中占的比重。為了突出生產線平衡的重要性，本文選取α=0.3、β=0.7。

3 遍歷搜索算法求解

3.1 搜索可行的加工順序

L公司A生產線上工序之間的先后約束關系可由圖1來表示。圖的遍歷，是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。訪問頂點所做的操作依賴于具體的工序之間的先后約束關系，利用具體實踐，通過C++編程，來達到遍歷各個工序節點的目的。

圖1 為A生產線的工序約束圖

圖1中的節點表示工序，連接節點的箭頭線表示工序加工先后順序。從圖1中可知，該生產線可行的加工順序數量有限，直接采用遍歷搜索算法即可找出所有可行的加工順序。

開始搜索之前，先根據工序先后關系圖，建立該生產線的優先關系矩陣M。工序優先關系矩陣M=(Mij)n×n，如果第i道工序在第j道工序之前完成，則Mij=1，否則Mij=0。根據優先關系矩陣，搜索可行的加工順序。首先，判斷n是否大于0，如果是，則找出可以排在最前面(前面沒有其他工序)的工序，該工序滿足下列條件：

在隊列中存儲工序j；否則返回。然后判斷隊列是否為空隊列。如果為空，退出搜索；否則，輸出隊首的工序，在M矩陣中刪除該工序對應的行和列，工序數減少1。具體搜索過程如圖2所示。通過C++編程，對于A生產線，搜索出可行的加工順序共30種。

圖2 遍歷算法流程

3.2 把作業分配到工作站

在把作業分配到工作站時采用最大分配原則法。最大分配原則就是在分配作業元素到工作站時，保證該工作站的總工作時間不超過生產節拍的前提下，把盡可能多的作業元素分配給這個工作站。

根據各作業元素的加工時間(如表2所示)，分別對每種可行的加工順序，首先把每個作業先分配到工作站，記錄每個工作站的作業元素、計算工作的總加工時間，統計工作站的數量。最后再計算出每種加工順序對應的目標函數值，確定最優的加工順序。

表2 作業元素的加工時間 小時

3.3 運行結果

本文通過C++語言編寫算法程序，程序運行的結果顯示，A生產線共有30中可行的作業加工順序。最優的加工順序如圖3所示。優化后的工作站數量是4，較之前的6個工作站減少50%。

圖3 A生產線的最優作業先后關系圖

每個工作站中的作業元素，工作站的總加工時間見表3。結果表明，采用該模型可以大幅提高整個生產線的平衡性，從而降低了總加工時間。

表3 各工作站作業分配

優化后生產線的平滑性指數F=1.01，生產線的平衡率從59%提高到89%。

實踐表明：采用遍歷搜索算法來實現生產線中作業的重新排序，以及最小化工作站的數量，算法簡單、準確性高。對于作業數量較少，可行的作業順序數量有限的生產系統，可以用遍歷搜索算法得到生產線平衡的最優解。

4 L公司B生產線應用遺傳算法求解

L公司B生產線是公司連續梁生產線。因為連續梁是支座組裝的重要環節，且連續梁生產線存在效率低下、成本浪費等生產線不平衡現象，所以對連續梁的生產線平衡問題進行展開分析。利用式(1)計算可知，該生產線的平衡率為65%，平衡率比較低，需要改善提高。

對于復雜的平行生產線系統，如公司的B生產線是有25個工序、15個工作站的連續梁平行生產線，作業數量較大，可行的作業排序數量數以億計，用遍歷搜索效率太低，不宜采用完全遍歷算法。為了合理解決這類生產線的平衡問題，本文編制了遺傳算法。

遺傳算法本質也是搜索算法。這種算法把每個潛在解當作一個染色體個體，然后通過個體的交叉和變異，產生新的個體(潛在解)。使個體進化到越來越好的區域，最后求得問題的最優解。以下是遺傳算法的實現過程。

4.1 B生產線工序的編碼

B生產線各工序總時間24.2小時，生產節拍為2.5小時，該生產線的緊前工序和緊后工序可由工序約束圖4來表示。

圖4 B生產線的工序約束圖

上述每個作業元素對應一個基因位。為了應用遺傳算法，對作業元素進行統一編碼。即對每一作業分配一個唯一從1到25的數字符號，對作業元素進行標識。

本文為數據元素定義了數據結構。

struct Process

{

char Title[20];

int Num;

float Time;

};

其中，Title字段存儲作業的名稱，Num字段為作業的編號，Time字段為作業的加工時間。

4.2 初始種群選擇

首先根據生產線的工序約束圖建立工序優先關系矩陣M=(Mij)n×n。借助于遍歷搜索算法，搜索出部分可行的加工順序。把搜索的加工順序數量設置為2千萬個，程序運行了1.5小時。從搜索出的加工順序中，隨機取出一部分，作為一個初始種群。

4.3 個體交叉

交叉是將種群中的個體染色體搭配成對，并以一定的方式交換它們之間的基因位，得到新的個體。在進行交叉操作時本文采用了兩種方法，第一種方法采用固定點操作法，任意選擇兩個適宜的個體作為交叉對象(父個體)，兩個個體在固定的基因位置進行交叉基因碼操作，形成兩個新個體；第二種方法是隨機點交叉法，即使用固定長度的二進制符號串來確定要交叉操作的基因位置。為了簡單說明兩種交叉操作過程，本文采用只有8個工序的生產線為例進行說明。生產線中作業的先后順序如圖5所示。

圖5 某生產線的工序約束圖

對于兩個個體，如果在奇數點進行固定點交叉。子個體1中偶數點位基因繼承父個體1中相應位置的基因，奇數點位置的基因按照在父個體2中順序保留。按照相同的方式得到子個體2。結果如表4所示。

父代1：

父代2：

子代1：

子代2：

表4 工序圖個體

如果按照隨機點交叉方式操作，在交叉前需要隨機生成一個長度等于基因數量的二進制數。在子個體1在二進制數為1的點位上繼承父個體1的基因，其他位置的基因按照在父個體2中的順序繼承。子個體2按照相同的方式得到。結果如表5所示。

二進制串：

父代1：

父代2：

子代1：

子代2：

表5 個體交叉示意圖

4.4 個體變異

為了擴大遺傳算法的搜索空間，避免得到局部最優解，需要進行變異操作。變異是將強行改變個體染色體中的某些基因位上的值而形成新的個體。由于每一個作業對應一個編碼，因此實際操作中可隨機交換兩個基因得到新的個體。由于生產線中作業加工順序的限制，變異后的個體可能不符合實際生產要求，因此需要對變異后的個體進行檢驗，判斷其是否滿足優先關系矩陣的邏輯關系，并且只有當變異的新個體優于舊個體時，才能把其更新為新的個體。變異操作仍以圖5為例來說明，如果在2和3位置交換基因，變異的結果如圖6所示。

圖6 個體變異示意圖

4.5 B生產線工序的譯碼

染色體個體中每個基因對應著一個工序，每個個體對應一種作業加工順序。已知該生產線的生產節拍2.5小時，對每種加工順序，根據作業的加工時間，采用最大分配原則的方法把各個作業元素分配到每個工作站，然后計算目標函數值。為此，本文定義了工作站數據結構，存儲每個工作站的信息。

struct Station //定義工作站數據結構

{

int work[N];

int p;

float time;

};

其中，work字段存儲作業的編號，p字段指示作業的個數，time字段存放該工作站的總加工時間。

4.6 B生產線優化結果

由于采用搜索算法得到了部分可行的作業加工順序，從這些加工順序中選出部分作為初始種群，因此本文的初始種群的規模可以調控。

在程序運行前，設置染色體的交叉概率為0.9，變異概率為0.1，設置種群的規模從50逐漸到20 000，遺傳的代數從5 000逐步增加到50 000代；比較了各種運行結果，驗證了遺傳算法有很好的收斂性。最終優化結果如表6，最優的作業加工順序如圖7所示。

表6 各工作站作業分配表

圖7 B生產線的最優作業順序圖

根據實驗結果分析可知，平衡優化后B生產線的部分工序得到了重新分配，工作站的數量由15個減少到12個，各工作站實際操作的時間越來越趨于相等，生產線平衡損失率由原來的59%提高到80%，解決了生產線工序分配不合理的情況，平滑指數F為0.23，優化效果明顯。B生產線的生產線平衡問題通過遺傳算法優化得到了明顯的改善。

5 結 語

本文針對L公司A和B生產線存在的問題進行了分析，應用C++程序語言分別編制遍歷搜索算法與遺傳算法，對L公司的兩條不同的生產線進行了優化。實踐表明，對于簡單的生產線，可行的作業加工順序較少，應用遍歷算法能夠快速準確地對生產線進行優化；對于復雜的生產線，由于可行的作業加工數量數目巨大，不可能進行完全遍歷，而把遍歷搜索的有限作業加工順序作為種群，應用遺傳算法能夠快速地得到優化結果。通過對公司A和B生產線的平衡優化，也表明了遍歷算法和遺傳算法相結合的優化方法在生產流程優化方面的有效性和精準性。

[1] Becker C,Scholl A.A survey on problems and methods in generalized assembly line balancing[J].European Journal of Operational Research,2006,168(3):694-715.

[2] 邵仁玉.基于工業工程的生產線平衡與優化[J].機械設計與制造工程,2014(48):66-68.

[3] 邱伊健,涂海寧.基于Flexsim與遺傳算法的混流生產線仿真與優化研究[J].組合機床與自動化加工技術,2015(8):119-123.

[4] 袁小蘭,徐子奇,舒帆.基于遺傳算法的發動機裝配線平衡問題仿真及優化[J].物流工程與管理,2015,37(7):213-216.

[5] 劉環宇,夏吉慶,施燦璨,等.基于遺傳算法對A公司生產線平衡的分析[J].物流技術,2014,33(9):367-370.

[6] 余曉光,嚴洪森.基于禁忌搜索遺傳混合算法的裝配線平衡[J].計算機技術與發展,2010,20(5):5-8.

[7] 范維博,周俊,許正良.應用遺傳算法求解第一類裝配線平衡問題[J].計算機技術與發展,2010,20(2):194-196.

[8] 扈靜,蔣增強,葛茂根.基于改進遺傳算法的混合裝配生產線平衡問題研究[J].合肥工業大學學報,2010,33(7):1006-1009.

[9] 楊威,孟冠軍,曹文鋼,等.基于改進遺傳算法的裝配序列優化[J].機械傳動,2016(9):67-70.

[10] 張子凱,唐秋華,張利平,等.改進遺傳算法求解大規模混流U型裝配線問題[J].機械設計與制造,2016(1):137-139.

[11] 吳偉云,樂天.遺傳算法中選擇算子的述評[J].福建電腦,2012(17):43-44.

[12] 徐學軍,陸德謀,李文嬌,等.生產線平衡與企業利潤關系的研究[J].工業工程,2009,12(4):41-45.

OPTIMIZATIONOFPRODUCTIONLINEEQUILIBRIUMBASEDONTRAVERSALSEARCHALGORITHMANDGENETICALGORITHM

Fang Jingfang Xu Yankai
(SchoolofMechanicandElectronicalEngineering,LanzhouUniversityofTechnology,Lanzhou730050,Gansu,China)

Two kinds of production line of L Company were analyzed and the mathematical model of the each production line was established. The production line was optimized with the aim of minimizing the number of workstations and the load smoothing index. For the simple production line, all the possible job processing orders were found by traversing algorithm, and then the processing order with minimum number of workstations and minimum smoothing index was decided. For the complex production line, the genetic algorithm was used to find the best processing order, with the population from the traversal search algorithm. So the problem of production line balance in the L Company was solved. It is proved that the traversal algorithm and the genetic algorithm are very effective during the optimization of the production line.

Line balance Workstation number Traversal algorithm Genetic algorithm Production line optimization

2016-11-23。甘肅省科技支撐計劃項目(1604GKCA020)。方景芳，教授，主研領域：生產流程優化，物流與供應鏈管理，系統建模與仿真。徐艷凱，碩士生。

TP311.11

A

10.3969/j.issn.1000-386x.2017.08.049