有兼容作業(yè)元素的混流裝配線平衡問題研究*

龔 軻，丁武學(xué)，王栓虎

（南京理工大學(xué)機(jī)械工程學(xué)院，南京 210094）

有兼容作業(yè)元素的混流裝配線平衡問題研究*

龔 軻，丁武學(xué)，王栓虎

（南京理工大學(xué)機(jī)械工程學(xué)院，南京 210094）

基于第Ⅰ類混流裝配線平衡問題，對(duì)作業(yè)元素之間的兼容性問題進(jìn)行了研究，即將那些需要使用到相同作業(yè)設(shè)備，或受某些工藝條件約束而需要在同一工作站上完成的兼容作業(yè)元素分配到同一工作站，以使企業(yè)在建立混流裝配線時(shí)，避免設(shè)備重復(fù)配置造成的成本浪費(fèi)，并以空閑時(shí)間最小、工作站之間負(fù)荷均衡和在裝配不同產(chǎn)品時(shí)，同一工作站內(nèi)負(fù)荷均衡為優(yōu)化目標(biāo)建立了多目標(biāo)優(yōu)化的數(shù)學(xué)模型，然后采用遺傳算法對(duì)該模型進(jìn)行求解，最后通過實(shí)例來分析驗(yàn)證所提方法的有效性。

兼容作業(yè)元素；混流裝配線；裝配線平衡；遺傳算法

0 引言

裝配線是由工作站、物流對(duì)象、作業(yè)元素和操作人員按一定的規(guī)則組成的生產(chǎn)系統(tǒng)，產(chǎn)品依次通過裝配線上的各個(gè)工作站逐漸成為成品下線［1-2］。裝配線平衡就是在工藝約束的條件下，將作業(yè)元素分配到各工作站，使各工作站負(fù)荷盡可能均衡，達(dá)到空閑和超載時(shí)間最少的目的［3］。自美國學(xué)者Bryton B第一次提出裝配線平衡問題以來，裝配線平衡就一直是裝配線設(shè)計(jì)領(lǐng)域研究的重點(diǎn)問題。隨著人們的需求逐漸變得多樣化，裝配線上生產(chǎn)的產(chǎn)品類型也逐漸從單品種生產(chǎn)向多品種混合生產(chǎn)轉(zhuǎn)變。與單品種裝配線平衡相比，混流裝配線平衡顯得更為困難，其原因在于［4］：①單品種裝配線上，各作業(yè)元素的作業(yè)時(shí)間是固定的，而混流裝配線上，在裝配不同產(chǎn)品時(shí)，同一作業(yè)元素其作業(yè)時(shí)間不盡相同，有時(shí)還相差很大；②在同步傳送的情況下，混流裝配線的生產(chǎn)節(jié)拍必須等于任意工作站上的最大作業(yè)時(shí)間，才能保證所有工位上的作業(yè)任務(wù)在該工位內(nèi)完成，這就會(huì)產(chǎn)生較大的空閑時(shí)間，使裝配線效率低下。

由于單品種裝配線的平衡相對(duì)簡單，所以自裝配線平衡問題提出來之后，關(guān)于單品種裝配線平衡的研究非常多，但關(guān)于混流裝配線平衡問題的研究一直進(jìn)展緩慢。直到1970年，ThomoPoulos NT首次運(yùn)用聯(lián)合作業(yè)優(yōu)先圖的概念，將混流裝配線平衡問題轉(zhuǎn)化為單品種裝配線平衡問題來處理，才使得混流裝配線平衡問題的研究有了突破性的進(jìn)展，目前關(guān)于混流裝配線的研究依然采用這種思路。由于裝配線平衡問題是典型的NP難題，無法通過解析法求得其精確解，所以目前對(duì)于混流裝配線平衡問題的研究主要側(cè)重于對(duì)特定問題的數(shù)學(xué)建模以及模型求解的研究，即針對(duì)具體問題建立相應(yīng)的數(shù)學(xué)模型，和尋找一種更有效的方法來求解數(shù)學(xué)模型。

在產(chǎn)品的裝配過程中，在完成某些作業(yè)元素時(shí)，需要使用到相同的作業(yè)設(shè)備，為了避免設(shè)備重復(fù)配置造成投資成本的浪費(fèi)，可將這些作業(yè)元素分配到同一工作站，還有一些作業(yè)元素，由于受工藝條件的約束也必須分配到同一工作站進(jìn)行作業(yè)，將這些需要分配到同一工作站的作業(yè)元素稱為兼容元素。目前有關(guān)裝配線平衡問題的研究雖然多，但涉及到作業(yè)元素兼容性的相關(guān)文獻(xiàn)卻非常的少。如文獻(xiàn)［5-8］都對(duì)特定問題進(jìn)行了研究，并建立了相應(yīng)的數(shù)學(xué)模型，提出了有效的求解方法，但這些文獻(xiàn)都沒有涉及到作業(yè)元素兼容性的問題。

1 模型建立

混流裝配線平衡問題主要可分為2類，第Ⅰ類裝配線平衡主要針對(duì)新裝配線的建立，即給定生產(chǎn)節(jié)拍，使工作站數(shù)量最少；第Ⅱ類裝配線平衡主要是對(duì)已建立的裝配線進(jìn)行優(yōu)化，即給定工作站數(shù)，使生產(chǎn)節(jié)拍最小。本文基于第Ⅰ類裝配線平衡，再綜合考慮作業(yè)元素的兼容性，建立如下數(shù)學(xué)模型：

式中，J1、J2、J3和J為優(yōu)化目標(biāo)，CT為生產(chǎn)線節(jié)拍，對(duì)于第Ⅰ類裝配線平衡問題，CT=計(jì)劃期內(nèi)有效工作時(shí)間/計(jì)劃總產(chǎn)量；qm為第m種產(chǎn)品在預(yù)期總產(chǎn)量中的比例，在計(jì)劃期內(nèi)qm=產(chǎn)品m的計(jì)劃產(chǎn)量/計(jì)劃總產(chǎn)量；tmk為第m種產(chǎn)品在工作站k的單件作業(yè)時(shí)間；S為工作站數(shù)；N為在混流裝配線上完成產(chǎn)品裝配的作業(yè)元素?cái)?shù)；xik為決策變量，如果xik=1則代表作業(yè)元素i被分配到工作站k，如果xik=0則代表第i項(xiàng)作業(yè)元素沒有被分配到工作站k；tim表示第m種產(chǎn)品在完成第i項(xiàng)作業(yè)元素時(shí)所需的作業(yè)時(shí)間，如果第m種產(chǎn)品不需要進(jìn)行第i項(xiàng)作業(yè)元素，則tim=0；Fi表示在作業(yè)優(yōu)先關(guān)系中，不能在作業(yè)元素i之前先完成的作業(yè)元素集；ZP為必須分配到同一工位的作業(yè)元素集合，即兼容元素集；w1、w2、w3為權(quán)重系數(shù)，其滿足w1+w2+w3=1，w1、w2、w3的大小由決策者根據(jù)其側(cè)重點(diǎn)選取。

式（1）、式（2）和式（3）分別為三個(gè)不同的優(yōu)化目標(biāo)。式（1）為空閑時(shí)間，在生產(chǎn)節(jié)拍給定的情況下，裝配線空閑時(shí)間最小，則意味著工作站數(shù)量最少，生產(chǎn)效率最高，因此J1可代表工作站數(shù)量最小化，通過這樣的轉(zhuǎn)換使工作站數(shù)最小化的優(yōu)化目標(biāo)與其他兩個(gè)優(yōu)化目標(biāo)統(tǒng)一于相同的數(shù)量級(jí)；式（2）為裝配線各工作站負(fù)荷的標(biāo)準(zhǔn)差，其值越小代表裝配線各工作站之間負(fù)荷越均勻；式（3）為工作站上不同產(chǎn)品作業(yè)時(shí)間的標(biāo)準(zhǔn)差的平均值，其值越小代表在同一工位上裝配不同產(chǎn)品時(shí)，該工位的作業(yè)時(shí)間波動(dòng)越小。J1、J2和J3通過加權(quán)求和得到綜合優(yōu)化目標(biāo)函數(shù)式（4）。

約束式（5）可以確保完成產(chǎn)品裝配的所有作業(yè)元素都只被分配到一個(gè)工作站；約束式（6）確保了作業(yè)元素的優(yōu)先約束關(guān)系；等式（7）是計(jì)算第m種產(chǎn)品在工作站k上完成單件產(chǎn)品所需的作業(yè)時(shí)間；約束式（8）是作業(yè)時(shí)間約束，它保證了所有工位上都不會(huì)出現(xiàn)超時(shí)現(xiàn)象；約束式（9）為兼容性約束條件，它可以確保兼容元素被分配到同一工作站；約束式（10）給出了決策變量的取值范圍。

2 模型求解

裝配線平衡問題是典型的NP難題，對(duì)于NP難題的求解，到目前為止仍然沒有找到一個(gè)多項(xiàng)式時(shí)間的有效算法，模擬生物進(jìn)化的遺傳算法由于其強(qiáng)大的搜索能力，能以很大的概率找到整體最優(yōu)解，因而在求解NP難題的研究中有著廣泛的應(yīng)用。本文將選用遺傳算法求解該模型。

2.1編碼和解碼

編碼方式對(duì)遺傳算子，尤其是對(duì)雜交和變異算子的功能和設(shè)計(jì)有很大的影響，最終會(huì)影響到遺傳算法的收斂速度和解的質(zhì)量。Gen M［9］已經(jīng)證明了在工程優(yōu)化問題中，實(shí)數(shù)編碼是一種較好的編碼方式。本文采用一串長度等于作業(yè)元素?cái)?shù)的數(shù)字串作為編碼基因，每個(gè)基因位代表一個(gè)作業(yè)元素，作業(yè)元素按其編號(hào)順序依次排列在基因位上，每一個(gè)基因值代表該處作業(yè)元素被分配到的工位。圖1為基因的編碼和解碼示例。

圖1 基因的編碼和解碼示例

2.2 適應(yīng)度函數(shù)

由于數(shù)學(xué)模型的優(yōu)化目標(biāo)是使目標(biāo)函數(shù)最小化，而在生物進(jìn)化的過程中，總是希望個(gè)體的適應(yīng)度越大越好，故適應(yīng)度函數(shù)可設(shè)計(jì)為：

式中，J為目標(biāo)函數(shù)，u為適應(yīng)度函數(shù)參數(shù)，其值等于當(dāng)前種群中目標(biāo)函數(shù)J的最大值。

2.3 遺傳算子

2.3.1 選擇

由于隨機(jī)聯(lián)賽選擇不僅能有效地避免超級(jí)個(gè)體的影響，還能在一定程度上避免早熟，因此本文采用隨機(jī)聯(lián)賽選擇，隨機(jī)的從當(dāng)前種群中選取一定數(shù)量的個(gè)體，然后選擇其中適應(yīng)度最大的個(gè)體作為下一代的父代，重復(fù)該過程，直至完成個(gè)體的選取。

2.3.2 交叉

交叉是為了將原有的優(yōu)良基因遺傳給下一代，并產(chǎn)生包含新的基因信息的新個(gè)體。本文選用兩點(diǎn)交叉的方式進(jìn)行交叉重組，由于在本數(shù)學(xué)模型中，個(gè)體受到作業(yè)時(shí)間和作業(yè)優(yōu)先順序等多種約束，交叉之后的個(gè)體不一定是有效個(gè)體，對(duì)于這種無效個(gè)體，應(yīng)進(jìn)行適當(dāng)?shù)恼{(diào)整使其滿足約束要求。

2.3.3 變異

本文采用均勻性變異，在父代個(gè)體中隨機(jī)選擇一個(gè)基因位，然后以其取值范圍內(nèi)一個(gè)均勻分布的隨機(jī)數(shù)取代該基因位的當(dāng)前值。變異也會(huì)產(chǎn)生無效個(gè)體，因此需要對(duì)變異后的個(gè)體進(jìn)行檢驗(yàn)，若變異之后的個(gè)體無效，則重新選擇父代個(gè)體進(jìn)行變異。

2.3.4 確定交叉和變異概率

交叉概率和變異概率的選擇影響著遺傳算法的行為和性能。為提高交叉和變異質(zhì)量，防止早熟和收斂速度過慢，交叉概率和變異概率均采用自適應(yīng)方式，使交叉概率和變異概率與進(jìn)化程度相關(guān)聯(lián)。交叉概率Pc和變異概率Pm的具體表達(dá)式為

式中k1、k2、k3和k4為常數(shù)，其取值為（0，1）；fmax和favg分別為上代種群中最大適應(yīng)值和平均適應(yīng)值；fc為要交叉的兩個(gè)體中較大的適應(yīng)值；fm為需要變異個(gè)體的適應(yīng)值。

3 實(shí)例分析

現(xiàn)通過算例分析文中所提方法的有效性。設(shè)在同一裝配線上需裝配A、B、C三種產(chǎn)品，三種產(chǎn)品的綜合作業(yè)優(yōu)先順序圖如圖2所示，各作業(yè)元素的作業(yè)時(shí)間如表1所示，其中作業(yè)元素11與12、17與19均需要使用到相同的工具，即它們是兼容的作業(yè)元素。一個(gè)工作日內(nèi)三種產(chǎn)品的計(jì)劃產(chǎn)量分別為DA=400件，DB=200件，DC=300件，一個(gè)工作日8小時(shí)，則按生產(chǎn)節(jié)拍的計(jì)算公式可確定裝配線節(jié)拍為32s。

圖2 綜合作業(yè)優(yōu)先順序圖

表1 A、B、C三種產(chǎn)品各作業(yè)元素的標(biāo)準(zhǔn)工時(shí)

按本文所建數(shù)學(xué)模型，取權(quán)重系數(shù)w1、w2和w3均為1/3，用MATLAB按本文所提遺傳算法編寫程序（其中k1=0.6，k2=0.9，k3=0.1，k4=0.1），經(jīng)過100代進(jìn)化后，獲得最優(yōu)個(gè)體，最優(yōu)個(gè)體的解碼結(jié)果如表2所示。結(jié)果表明本文所提方法不僅能將兼容元素分配到相同的工作站，還能使裝配線有較高的利用率。

表2 運(yùn)算結(jié)果

4 總結(jié)

本文在有關(guān)第Ⅰ類混流裝配線平衡研究的基礎(chǔ)上，對(duì)第Ⅰ類混流裝配線平衡問題進(jìn)行了進(jìn)一步的研究，在考慮裝配線空閑時(shí)間、工作站之間負(fù)荷均衡，以及同一工作站上裝配不同產(chǎn)品時(shí)的負(fù)荷均衡等問題的同時(shí)，還考慮了作業(yè)元素之間的兼容性，即將需要使用到相同作業(yè)工具的作業(yè)元素，或因其他工藝約束而必須在同一工位上進(jìn)行作業(yè)的作業(yè)元素，分配到同一工位，這能使企業(yè)在投資建立裝配線時(shí)，避免因設(shè)備重復(fù)配置而造成的成本浪費(fèi)。文章最后的實(shí)例分析驗(yàn)證了本文所提方法的有效性。

［1］胡羅克，陳勇，唐任仲.混流裝配線平衡分析與算法設(shè)計(jì)［J］.現(xiàn)代制造工程，2011（9）：1-4，9.

［2］X Delorme，O Batta?a，A Dolgui.Multi-objective Approaches for Design of Assembly Lines［J］.Applications of Multi-Criteria and Game Theory Approaches，2014：31-56.

［3］周小麗，曹振新.混流裝配線的規(guī)劃設(shè)計(jì)與仿真研究［J］.機(jī)床與液壓，2008，36（4）：344-348.

［4］于兆勤，蘇平.基于遺傳算法和仿真分析的混合裝配線平衡問題研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（6）：1120-1129.

［5］苑明海，李東波，于敏建.面向大規(guī)模定制的混流裝配線平衡研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（1）：79-83，131.

［6］Yazgan H R，Beypinar I，Boran S，et al.A new algorithm and multi-response Taguchi method to solve line balancing problem in an automotive industry［J］.The International Journal of Advanced Manufacturing Technology，2011，57：379-392.

［7］ügur?zcan，Bilal Toklu.Balancing of mixed-model two-sided assembly lines［J］.Computers&Industrial Engineering，2009，57（1）：217-227.

［8］Cemalettin?，Semra T，Brahim Hnich M，et al.Balancing and scheduling of flexible mixed model assembly lines［J］.Constraints，2013，18：434-469.

［9］Gen M，Cheng R.Genetic Algorithms and Engineering Optimization［M］.Toronto：John Wiley&Sons，Inc，2000.

（編輯 趙蓉）

Mixed-model Assembly Line Balancing Problem with Compatible Tasks Research

GONG Ke，DING Wu-xue，WANG Shuan-hu
（School of Mechanical Engineering，Nanjing University of Science and Technology，Nanjing 210094，China）

The compatible tasks problem based on MMALBP-Ⅰwas researched to make compatible tasks used the same equipment or constrained by some process conditions in the same work station，and the enterprise could reduce the amount of equipment and cost for it.A mathematical programming model was built for it and it had three objectives，such as minimize idle time of workstation，balancing workload between stations and balancing workload assembling different model in the same station and a genetic algorithm was used to solve it.Finally an example was showed to prove the efficiency of the approach.

compatible tasks；mixed-model assembly line；assembly line balancing；genetic algorithm

TH166；TG65

A

1001-2265（2015）06-0134-03 DOI：10.13462/j.cnki.mmtamt.2015.06.036

2014-10-12；

2014-10-31

江蘇省產(chǎn)學(xué)研前瞻性聯(lián)合研究項(xiàng)目（BY2014004-02）

龔軻（1988—），男，湖南婁底人，南京理工大學(xué)碩士研究生，研究方向?yàn)榛炝餮b配線的規(guī)劃與設(shè)計(jì)，（E-mail）gongke0613@163.com。