曹守啟，朱雅雯

（上海海洋大學(xué) 工程學(xué)院，上海 201306）

0 引言

自從1913年福特公司開(kāi)發(fā)出了世界上第一條流水線(xiàn)起，流水線(xiàn)作業(yè)逐漸成為汽車(chē)行業(yè)生產(chǎn)的唯一生產(chǎn)方式。隨著而來(lái)的便是流水線(xiàn)的平衡問(wèn)題，這一問(wèn)題最早由B.Bryton于1954年在他的碩士論文中提出，而在1955年Salveson首先建立了單品種裝配流水線(xiàn)的數(shù)學(xué)模型，并給出了模型的解法[1]，而自從20世紀(jì)80年代起，主要應(yīng)用于飛機(jī)、汽車(chē)制造業(yè)的多品種的混合流水線(xiàn)得到了迅速發(fā)展[2]。這使得汽車(chē)行業(yè)從大批量、單一品種的生產(chǎn)方式，轉(zhuǎn)變?yōu)橹卸嗥贩N、小批量的精益生產(chǎn)方式。但由于混合流水線(xiàn)多品種的特點(diǎn)使得流水線(xiàn)平衡成為復(fù)雜的多目標(biāo)問(wèn)題。因此，流水線(xiàn)平衡成為混合流水線(xiàn)使用行業(yè)重要的關(guān)注點(diǎn)。流水線(xiàn)平衡系統(tǒng)由流水線(xiàn)平衡及流水線(xiàn)排產(chǎn)組成，用以協(xié)調(diào)各工位中不同型號(hào)車(chē)輛工藝數(shù)及各型號(hào)車(chē)輛投放順序來(lái)解決混合流水線(xiàn)效率問(wèn)題的主流方法。目前對(duì)于混合流水線(xiàn)平衡的研究多著重在于流水線(xiàn)平衡而忽視流水線(xiàn)排產(chǎn)，在完成各工作站的車(chē)輛工藝平衡后直接根據(jù)各型號(hào)汽車(chē)需求量排產(chǎn)。但平衡與排產(chǎn)問(wèn)題存在相互影響，單獨(dú)考慮平衡問(wèn)題會(huì)降低優(yōu)化效果。因此，目前對(duì)于平衡系統(tǒng)的研究多是獨(dú)立研究。而本文提出的合作性協(xié)同進(jìn)化算法是一種能夠體現(xiàn)子目標(biāo)間相互協(xié)作關(guān)系的多目標(biāo)問(wèn)題協(xié)同求解算法。其能夠有效，精確的解決如汽車(chē)混合流水線(xiàn)平衡系統(tǒng)這樣存在平衡與排產(chǎn)協(xié)作關(guān)系的多目標(biāo)問(wèn)題。

1 汽車(chē)混合流水線(xiàn)的多目標(biāo)平衡

隨著汽車(chē)行業(yè)競(jìng)爭(zhēng)與市場(chǎng)需求的變化，混合流水線(xiàn)的誕生時(shí)的流水線(xiàn)平衡問(wèn)題變得更加復(fù)雜化。半個(gè)多世紀(jì)以來(lái)，混合流水線(xiàn)在汽車(chē)領(lǐng)域的使用已普及開(kāi)來(lái)。但對(duì)于汽車(chē)混合流水線(xiàn)乃至所有混合流水線(xiàn)的設(shè)計(jì)，都將流水線(xiàn)的平衡與產(chǎn)品的投產(chǎn)排序分開(kāi)作為兩種單獨(dú)的問(wèn)題來(lái)考慮，但這樣的方式往往使得設(shè)計(jì)出現(xiàn)缺陷，無(wú)法得到最優(yōu)解。這導(dǎo)致了混合流水線(xiàn)的使用停滯不前。現(xiàn)今的解決方式是將平衡設(shè)計(jì)與排產(chǎn)設(shè)計(jì)進(jìn)行串聯(lián)考慮，在完成平衡設(shè)計(jì)后再參開(kāi)排序設(shè)計(jì)。但這種方式并不能完全解決缺陷，如要得到全局最優(yōu)解應(yīng)把兩種設(shè)計(jì)并行考慮，在平衡的同時(shí)考慮排產(chǎn)，即將平衡問(wèn)題看作多目標(biāo)的優(yōu)化問(wèn)題。

1.1 以工作站負(fù)荷為基礎(chǔ)的混合流水線(xiàn)平衡

混合流水線(xiàn)的平衡只要分為三類(lèi)：在流水線(xiàn)節(jié)拍已知的情況下，求得最少的線(xiàn)上工作站數(shù)；在已知不變的工作站數(shù)的條件下計(jì)算最小節(jié)拍；以及在節(jié)拍與工作站數(shù)都確定不變的基礎(chǔ)上均衡每個(gè)工作站的負(fù)荷。一般情況下，對(duì)于前兩類(lèi)的平衡計(jì)算較少，這是由于如需對(duì)前兩者進(jìn)行設(shè)計(jì)則設(shè)計(jì)投資、設(shè)備購(gòu)買(mǎi)、場(chǎng)地規(guī)劃等等問(wèn)題，屬于長(zhǎng)期決策，一般在流水線(xiàn)建造設(shè)計(jì)之初就已確定。因此，本文中我們對(duì)于流水線(xiàn)的平衡問(wèn)題主要考慮的是工作站的平均負(fù)荷，但汽車(chē)混合裝配流水線(xiàn)相較于普通生產(chǎn)單一產(chǎn)品的流水線(xiàn)，其平衡特點(diǎn)在于即使當(dāng)平均負(fù)荷未超出標(biāo)準(zhǔn)的情況下單個(gè)型號(hào)產(chǎn)品也會(huì)出現(xiàn)超節(jié)拍的情況。而對(duì)于流水線(xiàn)平衡問(wèn)題來(lái)說(shuō)，其工作就是合理分配工作站工序，并使得每個(gè)工作站作業(yè)時(shí)間最大限度接近平均節(jié)拍，同時(shí)又能減少工作站的閑置時(shí)間與超載時(shí)間。

其中K為流水線(xiàn)負(fù)荷系數(shù)，F(xiàn)表示流水線(xiàn)上有效作業(yè)時(shí)間的總和，N表示流水線(xiàn)中的工作站數(shù)，C表示流水線(xiàn)的節(jié)拍（即流水線(xiàn)上生產(chǎn)兩件產(chǎn)品間的時(shí)間間隔）。

以一個(gè)擁有N個(gè)工作站的汽車(chē)混合流水線(xiàn)為例，線(xiàn)上共生產(chǎn)M種產(chǎn)品，產(chǎn)品的生產(chǎn)總量為D，每種型號(hào)汽車(chē)的需求產(chǎn)量為dm（m=1,2,3,…,M），對(duì)于以?xún)?yōu)化汽車(chē)混合流水線(xiàn)工作站負(fù)荷為目標(biāo)的平衡工作來(lái)說(shuō)，在滿(mǎn)足流水線(xiàn)節(jié)拍的條件下，在完成分配后希望其空閑時(shí)間最小，即使用節(jié)拍計(jì)算得到的理論工作時(shí)間與實(shí)際有效作業(yè)時(shí)間的相對(duì)誤差，用算式表達(dá)為：

其中：

tmn為型號(hào)為m的產(chǎn)品在工作站n上的的作業(yè)時(shí)間；式(3)表示計(jì)算空閑時(shí)間的前提條件要求實(shí)際有效平均作業(yè)時(shí)間必定不能超過(guò)已定節(jié)拍值。

1.2 以工作站負(fù)荷為基礎(chǔ)的混合流水線(xiàn)排產(chǎn)

汽車(chē)混合裝配線(xiàn)的排產(chǎn)排序是屬于平衡系統(tǒng)的重要組成部分，隨著投產(chǎn)順序的改變，每種型號(hào)產(chǎn)品在同一工作站的節(jié)拍不盡相同，時(shí)常導(dǎo)致工作站中出現(xiàn)閑置或者超載的情況發(fā)生。而汽車(chē)混合裝配線(xiàn)的排產(chǎn)設(shè)計(jì)是基于流水線(xiàn)平衡的重要步驟，其決定了不同型號(hào)的產(chǎn)品在同一流水線(xiàn)上的投放順序，目的是保證產(chǎn)品的均衡化。對(duì)于汽車(chē)混合流水線(xiàn)排產(chǎn)，簡(jiǎn)單的說(shuō)來(lái)就是把各種型號(hào)的產(chǎn)品按照合理排序投送到流水線(xiàn)上，用算式可以這樣表達(dá)：在與平衡設(shè)計(jì)相同條件下，假設(shè)a為各型號(hào)產(chǎn)品生產(chǎn)dm的最大公約數(shù)，使得即M種類(lèi)型產(chǎn)品在單次循環(huán)中每種類(lèi)型產(chǎn)品的投產(chǎn)數(shù)量，一般情況下，對(duì)于流水線(xiàn)的排產(chǎn)就是對(duì)這單次循環(huán)中F個(gè)產(chǎn)品的排序。這樣循環(huán)a次，便是一條混合流水線(xiàn)的的排產(chǎn)結(jié)果。而在單次循環(huán)中的m種產(chǎn)品排序就要根據(jù)工作站最少空閑與超載的原則來(lái)計(jì)算。假設(shè)一條汽車(chē)混合流水線(xiàn)的移動(dòng)速度為v，工作站n（n=1,2,…,N）的流水線(xiàn)長(zhǎng)度為L(zhǎng)n，產(chǎn)品投產(chǎn)間隔為e，假設(shè)單次循環(huán)中第f位置的產(chǎn)品為m，m在工作站n的的工作時(shí)間tmnf流水線(xiàn)小于投產(chǎn)間隔則可能出現(xiàn)空閑狀態(tài)，考慮操作者走動(dòng)速度vp，則空閑時(shí)間為：，假設(shè)混合流水線(xiàn)上第一輛汽車(chē)的起始位置為lml0=0，則第f位置車(chē)輛在工作站n上的位置為，考慮操作人員走動(dòng)時(shí)間后的超載時(shí)間為：。則可用閑置與超載費(fèi)用來(lái)體現(xiàn)排產(chǎn)效果，即目標(biāo)函數(shù)為：

從上述模型公式中可以看到，汽車(chē)混合流水線(xiàn)的排產(chǎn)是基于產(chǎn)品在工作站中的工作時(shí)間進(jìn)行計(jì)算的，即tmnf。而tmnf是根據(jù)流水線(xiàn)的平衡決定的各型號(hào)車(chē)輛在工作單元的作業(yè)要素決定的。因此，在一定程度上，流水線(xiàn)的平衡結(jié)果決定了排產(chǎn)結(jié)果。

2 汽車(chē)混合流水線(xiàn)平衡系統(tǒng)算法

2.1 汽車(chē)混合流水線(xiàn)獨(dú)立優(yōu)化算法

汽車(chē)混合流水線(xiàn)平衡系統(tǒng)的兩個(gè)子目標(biāo)為流水線(xiàn)平衡與流水線(xiàn)排產(chǎn)，兩者之間存在一定影響，一個(gè)子目標(biāo)的改善會(huì)引起另一個(gè)子目標(biāo)的變化。在一定程度上，流水線(xiàn)的平衡結(jié)果決定了排產(chǎn)結(jié)果，同時(shí)不同車(chē)型有著不同生產(chǎn)工藝，投產(chǎn)排序的不同會(huì)影響工作站上的工作時(shí)間，從而影響平衡效果，反之亦然。這樣的相互影響使得兩個(gè)子目標(biāo)無(wú)法同時(shí)達(dá)到最優(yōu)，只能協(xié)調(diào)子目標(biāo)達(dá)到盡可能的最優(yōu)化[3]，因此這是典型的多目標(biāo)問(wèn)題。

解決多目標(biāo)問(wèn)題的傳統(tǒng)方法有一個(gè)共同特征，即將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題進(jìn)行求解，常見(jiàn)的化多目標(biāo)為單目標(biāo)的方法有加權(quán)和法、目標(biāo)規(guī)劃法、E-約束法、目標(biāo)滿(mǎn)意法等[4]。但多目標(biāo)問(wèn)題很難簡(jiǎn)化為單目標(biāo)問(wèn)題，在簡(jiǎn)化過(guò)程中難免收到主觀因素影響，這會(huì)大大影響優(yōu)化結(jié)果。

而在20世紀(jì)50年代末，出現(xiàn)了一種進(jìn)化算法，以模擬自然界的生物進(jìn)化過(guò)程來(lái)進(jìn)行優(yōu)化的方法，之后在20世紀(jì)90年代中期得到迅速發(fā)展，是相較于傳統(tǒng)算法更為優(yōu)秀的優(yōu)化算法。其主要原理為，從隨機(jī)生成的種群出發(fā)，通過(guò)選擇、交叉、變異等進(jìn)化來(lái)提高個(gè)體適應(yīng)度。以此逐步逼近多目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解集[3]。相較于傳統(tǒng)多目標(biāo)優(yōu)化方法，多目標(biāo)進(jìn)化算法在運(yùn)行效率、精確度、分布型等方面都有了大大的提高，在工業(yè)、工程、科學(xué)等領(lǐng)域都有了大量的運(yùn)用。但多目標(biāo)進(jìn)化算法無(wú)法完全滿(mǎn)足汽車(chē)混合流水線(xiàn)平衡系統(tǒng)的優(yōu)化要求，由于平衡系統(tǒng)由兩個(gè)子系統(tǒng)組成，多目標(biāo)進(jìn)化算法無(wú)法體現(xiàn)兩個(gè)子系統(tǒng)之間的相互作用，單獨(dú)求解或者串行求解都無(wú)法得到系統(tǒng)整體最優(yōu)解集。因此，考慮一種協(xié)同進(jìn)化的算法，利用子系統(tǒng)間的系統(tǒng)關(guān)系進(jìn)行并行求解。

2.2 汽車(chē)混合流水線(xiàn)協(xié)同優(yōu)化算法

在1996年，Ehrlich和Raven在其發(fā)表的有關(guān)植物和昆蟲(chóng)之間的協(xié)同進(jìn)化時(shí)首次提出了協(xié)同進(jìn)化遺傳算法(Coevolutionary Genetic Alorithm, CGA)[5]的概念。其將大型復(fù)雜問(wèn)題分解，以子問(wèn)題的形式存在，這些子問(wèn)題存在協(xié)同關(guān)系，并行計(jì)算求解。這種算法模擬實(shí)際生態(tài)環(huán)境，各物種的進(jìn)化過(guò)程具有一定關(guān)聯(lián)性而非獨(dú)立，物種間的進(jìn)化相互影響，存在共生關(guān)系或者競(jìng)爭(zhēng)關(guān)系，以這種角度考慮生物進(jìn)化過(guò)程，即協(xié)同進(jìn)化[6]。協(xié)同進(jìn)化算法特點(diǎn)在于子系統(tǒng)間在相互作用下求得最優(yōu)解，而汽車(chē)混合流水線(xiàn)的平衡系統(tǒng)是由流水線(xiàn)平衡與流水線(xiàn)排產(chǎn)共同組成，兩者相互影響，同時(shí)考慮才能得到最優(yōu)解，因此適合使用協(xié)同進(jìn)化算法進(jìn)行求解。而協(xié)同進(jìn)化算法又因?yàn)樽臃N群間的不同協(xié)同關(guān)系分為基于生物間相互共生的合作型協(xié)同進(jìn)化算法和基于種群間競(jìng)爭(zhēng)的競(jìng)爭(zhēng)型協(xié)同進(jìn)化算法。其中競(jìng)爭(zhēng)型系統(tǒng)優(yōu)化算法體現(xiàn)了種群之間的對(duì)抗關(guān)系，以競(jìng)賽的形式迫使種群進(jìn)化；而合作型協(xié)同進(jìn)化算法是模擬了種群之間的共生關(guān)系，即一方的進(jìn)化需要另一方的幫助，這符合汽車(chē)混合流水線(xiàn)的平衡系統(tǒng)的實(shí)際情況。圖1為合作型協(xié)同進(jìn)化基本框架。

圖1 合作型協(xié)同進(jìn)化基本框架

1994年P(guān)otter等提出了合作型協(xié)同進(jìn)化算法，用來(lái)解決函數(shù)優(yōu)化問(wèn)題。由于該算法是以遺傳算法為基礎(chǔ),所以稱(chēng)其為合作型-協(xié)同遺傳算法[7](Cooperative Coevolutionary Genetic Algorithm, CCGA)。汽車(chē)混合流梳線(xiàn)使用合作型協(xié)同進(jìn)化的核心思想是子群體間的協(xié)同合作關(guān)系，即將系統(tǒng)分解為2個(gè)變量組成的2個(gè)子群體，將一個(gè)子群體中的個(gè)體與另一個(gè)子群體中的代表體組成完整解，根據(jù)解的優(yōu)劣評(píng)價(jià)個(gè)體與另一子群體的協(xié)同合作能力，如圖2所示。

圖2 合作型協(xié)同進(jìn)化圖

2004年Kuntinee Maneeratana[8]及AntonyW Iorio[9]等人將合作型協(xié)同進(jìn)化算法引入已有的包括MOGA、NPGA、NSGA、CNSGA、NSGA -Ⅱ的多目標(biāo)優(yōu)化進(jìn)化算法中。研究發(fā)現(xiàn)，使用合作型協(xié)同進(jìn)化算法可以提高普通進(jìn)化算法在多目標(biāo)問(wèn)題中的搜索效率。

3 結(jié)束語(yǔ)

隨著市場(chǎng)的需求變化，汽車(chē)混合流水線(xiàn)的應(yīng)用變得迫切起來(lái)，混合流水線(xiàn)的平衡優(yōu)化問(wèn)題一直是其廣泛運(yùn)用的困難之一。傳統(tǒng)的單獨(dú)對(duì)流水線(xiàn)進(jìn)行平衡而忽略排產(chǎn)問(wèn)題的算法存在一定問(wèn)題。混合流水線(xiàn)排產(chǎn)與平衡是相互影響的兩部分，單獨(dú)考慮其中之一或串行的求解方式難以得到真正的最優(yōu)解集。本文考慮將兩者進(jìn)行并行求解，使用合作型協(xié)同進(jìn)化算法對(duì)混合流水線(xiàn)這一多目標(biāo)優(yōu)化問(wèn)題，為解決這一復(fù)雜優(yōu)化問(wèn)題提供了一個(gè)解決途徑。

[1] Kroo I Altus S,Braun R,eta.l Multidisciplinary optimization methods for aircraft preliminary design[R].AIAA,1994,94-4325-CP.

[2] Gokcen H,Erel E.A Goal Programming Approach to Mixed Model Assembly Line Balancing Problem[J].International Journal of Production Economics,24 January 1997,48(2)：177-185.

[3] 肖曉偉,肖迪,林錦國(guó),肖玉峰.多目標(biāo)優(yōu)化問(wèn)題研究概述[J].計(jì)算機(jī)應(yīng)用研究,2011,3：28(3)805-808,827.

[4] Deb K,Agrawal S, Pratap A and Meyarivan T.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization： NSGA II.[A].Parallel Problem Solving from Nature[C].(PPSN VI),Berlin,2000.

[5] Ehrlieh P R,Raven P H. Butterflies and plants：a study in coevolution[J].Evolution,1964,18(4)：586-608.

[6] 王磊.并行與雙系統(tǒng)協(xié)同差異進(jìn)化算法及其應(yīng)用[D].大連理工大學(xué),2011.12.

[7] Potter M, De Jong K. A cooperative co evolutionary approach to function optimization[J].Lecture Notes in Computer Science, 1994,866(1994)：249-257.

[8] Kuntinee Maneeratana, Kittipong Boonlong and Nachol Chaiyaratana. Multi- objective Optimization by Co-operative Co-evolution[A].In Xin Yao eta.l editors, Parallel Problem Solving from Nature-PPSN VIII,Springer-Verlag, Lecture Notes in Computer Science[C].Birmingham, UK,September 2004,3242：772-781.

[9] AntonyW Iorio and Xiaodong Li A Cooperative Co evolutionary Multiobjective Algorithm Using non-dominated Sorting[A].In Kalyanmoy Deb eta.l editors,Proceedings of the Genetic and Evolutionary Computation Conference, Part I,Springer-Verlag, Lecture Notes in Computer Science[C].Seattle,Washington,USA, June 2004,3102：537-548.