基于遍歷搜索與遺傳算法的生產(chǎn)線平衡優(yōu)化

方景芳 徐艷凱

(蘭州理工大學(xué)機(jī)電工程學(xué)院 甘肅 蘭州 730050)

?

基于遍歷搜索與遺傳算法的生產(chǎn)線平衡優(yōu)化

方景芳 徐艷凱

(蘭州理工大學(xué)機(jī)電工程學(xué)院 甘肅 蘭州 730050)

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

生產(chǎn)線平衡 工作站數(shù) 遍歷算法 遺傳算法 生產(chǎn)線優(yōu)化

0 引 言

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

1 L公司A生產(chǎn)線問題的分析

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

表1 各工作站作業(yè)時(shí)間表 min

按照下式計(jì)算該生產(chǎn)線的平衡率：

(1)

得到：

對(duì)這一條生產(chǎn)線而言，平衡率達(dá)到85%才算合格，平衡損失率應(yīng)控制在15%以下。過低的平衡率，表明生產(chǎn)線有相當(dāng)大的改善空間。這段生產(chǎn)線的平衡率僅為59%，遠(yuǎn)遠(yuǎn)達(dá)不到合格的水平。說明該生產(chǎn)線各工作站之間的作業(yè)負(fù)荷量很不均衡，平衡率有待提高。

2 數(shù)學(xué)模型的建立

數(shù)學(xué)理論與實(shí)際生產(chǎn)系統(tǒng)相結(jié)合，利用生產(chǎn)系統(tǒng)參數(shù)進(jìn)行數(shù)學(xué)建模，并提出高效的數(shù)值求解方法，是生產(chǎn)線平衡優(yōu)化的基本理論框架?？疾橐粭l生產(chǎn)線是否合理，不僅要看其工位的數(shù)目是否最小，還要看生產(chǎn)線的負(fù)荷是否均衡。以作業(yè)順序圖和節(jié)拍為基礎(chǔ)，尋求生產(chǎn)線工作地?cái)?shù)量最小的工作方案，可由式(2)和式(3)來描述：

(2)

minF1=αm+βF

(3)

式中，CT為生產(chǎn)節(jié)拍；Sk為第k個(gè)工作站的總加工時(shí)間；m表示工作站的數(shù)量；F表示生產(chǎn)線的平滑指數(shù)；F1表示目標(biāo)函數(shù)是工作站數(shù)和生產(chǎn)線平衡指數(shù)的線性組合，其中α和β用以分配工作站數(shù)和平滑指數(shù)在優(yōu)化目標(biāo)函數(shù)中占的比重。為了突出生產(chǎn)線平衡的重要性，本文選取α=0.3、β=0.7。

3 遍歷搜索算法求解

3.1 搜索可行的加工順序

L公司A生產(chǎn)線上工序之間的先后約束關(guān)系可由圖1來表示。圖的遍歷，是從圖中的任一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問一次且只訪問一次。訪問頂點(diǎn)所做的操作依賴于具體的工序之間的先后約束關(guān)系，利用具體實(shí)踐，通過C++編程，來達(dá)到遍歷各個(gè)工序節(jié)點(diǎn)的目的。

圖1 為A生產(chǎn)線的工序約束圖

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

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

在隊(duì)列中存儲(chǔ)工序j；否則返回。然后判斷隊(duì)列是否為空隊(duì)列。如果為空，退出搜索；否則，輸出隊(duì)首的工序，在M矩陣中刪除該工序?qū)?yīng)的行和列，工序數(shù)減少1。具體搜索過程如圖2所示。通過C++編程，對(duì)于A生產(chǎn)線，搜索出可行的加工順序共30種。

圖2 遍歷算法流程

3.2 把作業(yè)分配到工作站

在把作業(yè)分配到工作站時(shí)采用最大分配原則法。最大分配原則就是在分配作業(yè)元素到工作站時(shí)，保證該工作站的總工作時(shí)間不超過生產(chǎn)節(jié)拍的前提下，把盡可能多的作業(yè)元素分配給這個(gè)工作站。

根據(jù)各作業(yè)元素的加工時(shí)間(如表2所示)，分別對(duì)每種可行的加工順序，首先把每個(gè)作業(yè)先分配到工作站，記錄每個(gè)工作站的作業(yè)元素、計(jì)算工作的總加工時(shí)間，統(tǒng)計(jì)工作站的數(shù)量。最后再計(jì)算出每種加工順序?qū)?yīng)的目標(biāo)函數(shù)值，確定最優(yōu)的加工順序。

表2 作業(yè)元素的加工時(shí)間 小時(shí)

3.3 運(yùn)行結(jié)果

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

圖3 A生產(chǎn)線的最優(yōu)作業(yè)先后關(guān)系圖

每個(gè)工作站中的作業(yè)元素，工作站的總加工時(shí)間見表3。結(jié)果表明，采用該模型可以大幅提高整個(gè)生產(chǎn)線的平衡性，從而降低了總加工時(shí)間。

表3 各工作站作業(yè)分配

優(yōu)化后生產(chǎn)線的平滑性指數(shù)F=1.01，生產(chǎn)線的平衡率從59%提高到89%。

實(shí)踐表明：采用遍歷搜索算法來實(shí)現(xiàn)生產(chǎn)線中作業(yè)的重新排序，以及最小化工作站的數(shù)量，算法簡(jiǎn)單、準(zhǔn)確性高。對(duì)于作業(yè)數(shù)量較少，可行的作業(yè)順序數(shù)量有限的生產(chǎn)系統(tǒng)，可以用遍歷搜索算法得到生產(chǎn)線平衡的最優(yōu)解。

4 L公司B生產(chǎn)線應(yīng)用遺傳算法求解

L公司B生產(chǎn)線是公司連續(xù)梁生產(chǎn)線。因?yàn)檫B續(xù)梁是支座組裝的重要環(huán)節(jié)，且連續(xù)梁生產(chǎn)線存在效率低下、成本浪費(fèi)等生產(chǎn)線不平衡現(xiàn)象，所以對(duì)連續(xù)梁的生產(chǎn)線平衡問題進(jìn)行展開分析。利用式(1)計(jì)算可知，該生產(chǎn)線的平衡率為65%，平衡率比較低，需要改善提高。

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

遺傳算法本質(zhì)也是搜索算法。這種算法把每個(gè)潛在解當(dāng)作一個(gè)染色體個(gè)體，然后通過個(gè)體的交叉和變異，產(chǎn)生新的個(gè)體(潛在解)。使個(gè)體進(jìn)化到越來越好的區(qū)域，最后求得問題的最優(yōu)解。以下是遺傳算法的實(shí)現(xiàn)過程。

4.1 B生產(chǎn)線工序的編碼

B生產(chǎn)線各工序總時(shí)間24.2小時(shí)，生產(chǎn)節(jié)拍為2.5小時(shí)，該生產(chǎn)線的緊前工序和緊后工序可由工序約束圖4來表示。

圖4 B生產(chǎn)線的工序約束圖

上述每個(gè)作業(yè)元素對(duì)應(yīng)一個(gè)基因位。為了應(yīng)用遺傳算法，對(duì)作業(yè)元素進(jìn)行統(tǒng)一編碼。即對(duì)每一作業(yè)分配一個(gè)唯一從1到25的數(shù)字符號(hào)，對(duì)作業(yè)元素進(jìn)行標(biāo)識(shí)。

本文為數(shù)據(jù)元素定義了數(shù)據(jù)結(jié)構(gòu)。

struct Process

{

char Title[20];

int Num;

float Time;

};

其中，Title字段存儲(chǔ)作業(yè)的名稱，Num字段為作業(yè)的編號(hào)，Time字段為作業(yè)的加工時(shí)間。

4.2 初始種群選擇

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

4.3 個(gè)體交叉

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

圖5 某生產(chǎn)線的工序約束圖

對(duì)于兩個(gè)個(gè)體，如果在奇數(shù)點(diǎn)進(jìn)行固定點(diǎn)交叉。子個(gè)體1中偶數(shù)點(diǎn)位基因繼承父?jìng)€(gè)體1中相應(yīng)位置的基因，奇數(shù)點(diǎn)位置的基因按照在父?jìng)€(gè)體2中順序保留。按照相同的方式得到子個(gè)體2。結(jié)果如表4所示。

父代1：

父代2：

子代1：

子代2：

表4 工序圖個(gè)體

如果按照隨機(jī)點(diǎn)交叉方式操作，在交叉前需要隨機(jī)生成一個(gè)長(zhǎng)度等于基因數(shù)量的二進(jìn)制數(shù)。在子個(gè)體1在二進(jìn)制數(shù)為1的點(diǎn)位上繼承父?jìng)€(gè)體1的基因，其他位置的基因按照在父?jìng)€(gè)體2中的順序繼承。子個(gè)體2按照相同的方式得到。結(jié)果如表5所示。

二進(jìn)制串：

父代1：

父代2：

子代1：

子代2：

表5 個(gè)體交叉示意圖

4.4 個(gè)體變異

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

圖6 個(gè)體變異示意圖

4.5 B生產(chǎn)線工序的譯碼

染色體個(gè)體中每個(gè)基因?qū)?yīng)著一個(gè)工序，每個(gè)個(gè)體對(duì)應(yīng)一種作業(yè)加工順序。已知該生產(chǎn)線的生產(chǎn)節(jié)拍2.5小時(shí)，對(duì)每種加工順序，根據(jù)作業(yè)的加工時(shí)間，采用最大分配原則的方法把各個(gè)作業(yè)元素分配到每個(gè)工作站，然后計(jì)算目標(biāo)函數(shù)值。為此，本文定義了工作站數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)每個(gè)工作站的信息。

struct Station //定義工作站數(shù)據(jù)結(jié)構(gòu)

{

int work[N];

int p;

float time;

};

其中，work字段存儲(chǔ)作業(yè)的編號(hào)，p字段指示作業(yè)的個(gè)數(shù)，time字段存放該工作站的總加工時(shí)間。

4.6 B生產(chǎn)線優(yōu)化結(jié)果

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

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

表6 各工作站作業(yè)分配表

圖7 B生產(chǎn)線的最優(yōu)作業(yè)順序圖

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

5 結(jié) 語

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

[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] 邵仁玉.基于工業(yè)工程的生產(chǎn)線平衡與優(yōu)化[J].機(jī)械設(shè)計(jì)與制造工程,2014(48):66-68.

[3] 邱伊健,涂海寧.基于Flexsim與遺傳算法的混流生產(chǎn)線仿真與優(yōu)化研究[J].組合機(jī)床與自動(dòng)化加工技術(shù),2015(8):119-123.

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

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

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

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

[8] 扈靜,蔣增強(qiáng),葛茂根.基于改進(jìn)遺傳算法的混合裝配生產(chǎn)線平衡問題研究[J].合肥工業(yè)大學(xué)學(xué)報(bào),2010,33(7):1006-1009.

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

[10] 張子凱,唐秋華,張利平,等.改進(jìn)遺傳算法求解大規(guī)?；炝鱑型裝配線問題[J].機(jī)械設(shè)計(jì)與制造,2016(1):137-139.

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

[12] 徐學(xué)軍,陸德謀,李文嬌,等.生產(chǎn)線平衡與企業(yè)利潤(rùn)關(guān)系的研究[J].工業(yè)工程,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。甘肅省科技支撐計(jì)劃項(xiàng)目(1604GKCA020)。方景芳，教授，主研領(lǐng)域：生產(chǎn)流程優(yōu)化，物流與供應(yīng)鏈管理，系統(tǒng)建模與仿真。徐艷凱，碩士生。

TP311.11

A

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