劉建國(guó)　王廷梅　李?lèi)?ài)菊

摘要：混流生產(chǎn)在產(chǎn)品生產(chǎn)過(guò)程中有多個(gè)加工和裝配操作，優(yōu)化過(guò)程是如何在多個(gè)加工設(shè)備和裝配設(shè)備上進(jìn)行調(diào)度，使產(chǎn)品加工時(shí)間最短。本文建立了混流生產(chǎn)合作博弈調(diào)度優(yōu)化方法，通過(guò)對(duì)問(wèn)題的分解和agent間的合作博弈調(diào)度，采用實(shí)驗(yàn)對(duì)算法進(jìn)行驗(yàn)證，得到了滿意的效果。

關(guān)鍵詞：agent；混合流水生產(chǎn)；調(diào)度；合作博弈

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）13-0221-02

1 研究背景

混合流水生產(chǎn)包括零部件加工和產(chǎn)品裝配過(guò)程。一件產(chǎn)品通常都由多個(gè)零部件裝配完成，而零件可以在多套生產(chǎn)設(shè)備上加工完成，裝配過(guò)程也是在多套裝配設(shè)備上完成。對(duì)于擁有多個(gè)無(wú)差別的生產(chǎn)和裝配設(shè)備的工廠，如何縮短產(chǎn)品的生產(chǎn)時(shí)間一直是重要的研究方向。

2 問(wèn)題原型

如圖1所示的產(chǎn)品及結(jié)構(gòu)，需要經(jīng)過(guò)多個(gè)加工與裝配機(jī)器進(jìn)行生產(chǎn)，研究的目標(biāo)是怎樣把零件分配到不同機(jī)器上加工和裝配，可以邊加工邊裝配，達(dá)到產(chǎn)品的makespan時(shí)間最短。

3 復(fù)雜結(jié)構(gòu)的分解和簡(jiǎn)單結(jié)構(gòu)圖的調(diào)度

對(duì)于結(jié)構(gòu)復(fù)雜的產(chǎn)品，都可對(duì)其結(jié)構(gòu)圖進(jìn)行分解，獲得多個(gè)簡(jiǎn)單圖。簡(jiǎn)單圖滿足每個(gè)度大于1的節(jié)點(diǎn)不超過(guò)一個(gè)度大于1的子節(jié)點(diǎn)，也就是每層不超過(guò)一個(gè)裝配節(jié)點(diǎn)。對(duì)圖1中A3節(jié)點(diǎn)分解，得到根節(jié)點(diǎn)為A1，A2和p5的三個(gè)簡(jiǎn)單圖。如圖3所示。

每個(gè)簡(jiǎn)單圖的調(diào)度都使用一個(gè)agent代表。對(duì)簡(jiǎn)單圖可以通過(guò)合理的調(diào)度算法得到最優(yōu)結(jié)果。對(duì)于一個(gè)制造系統(tǒng)，假設(shè)有m臺(tái)加工機(jī)器和q臺(tái)裝配機(jī)器，可以采用底層優(yōu)先算法，獲得makespan最小的最優(yōu)結(jié)果。算法順序如下：

1）加工過(guò)程工序安排：按照樹(shù)的層數(shù)從底層開(kāi)始，由下往上，同一層的加工工序按照時(shí)間由大到小順序優(yōu)先安排到空閑的加工機(jī)器上；

2）裝配過(guò)程工序安排：由于簡(jiǎn)單圖每層最多只有一個(gè)裝配工序，在其子節(jié)點(diǎn)工序都完成情況下，按照樹(shù)的層數(shù)從底層開(kāi)始，由下往上的順序安排到空閑的裝配機(jī)器上。

4 多agent調(diào)度

每個(gè)簡(jiǎn)單圖的調(diào)度都是用一個(gè)agent來(lái)代理，每個(gè)agent的獨(dú)立調(diào)度通過(guò)底層優(yōu)先方法得到，但全部agent受到產(chǎn)品整體邏輯關(guān)系的制約，非簡(jiǎn)單線性關(guān)系，因此多個(gè)agent之間進(jìn)行的整體調(diào)度是問(wèn)題關(guān)鍵。

考慮到各agent之間的關(guān)系，首先是競(jìng)爭(zhēng)的，但同時(shí)也必須進(jìn)行合作。因?yàn)橘Y源有限，各agent都以自己代理的任務(wù)盡快盡早結(jié)束為目標(biāo)；同時(shí)，受限于產(chǎn)品結(jié)構(gòu)，不是所有agent都可以不受約束在任何時(shí)間點(diǎn)開(kāi)始生產(chǎn)，有的必須等別的agent生產(chǎn)結(jié)束后才可上線生產(chǎn)，因此agent間也必須存在合作，各自都要服從在機(jī)器上時(shí)序的安排，最終達(dá)到目標(biāo)的整體最優(yōu)。

對(duì)于多agent的調(diào)度是研究的重點(diǎn)，本文采用多agent合作博弈的方法，具體算法如下：

1） 將所有agent分成三個(gè)集合：A是已參加博弈集，B是可選集，C是不可選集?？蛇x集表示其前期工序已完成；不可選集表示受產(chǎn)品結(jié)構(gòu)制約，其前期工序未完成，暫時(shí)不可進(jìn)行調(diào)度。

2） 在調(diào)度過(guò)程中，依次增加進(jìn)入A集合的agent個(gè)數(shù)，每次迭代過(guò)程只允許增加一個(gè)，直至全部agent都進(jìn)入A集中。在最初，A是空集， B是能夠直接加工無(wú)其他前序工序約束的所有agent集，調(diào)度開(kāi)始后，依次對(duì)B中的每一個(gè)agent單獨(dú)進(jìn)行調(diào)度，選擇B中makespan所需最長(zhǎng)的那個(gè)agent加人A集中，然后更新集合A，B和C。以后每次迭代過(guò)程中，都是從B集中挑選一個(gè)agent加入A集。方法是將B集中的每個(gè)agent與A集中的agent分別合在一起做調(diào)度，在A中已存在的順序不變情況下，將B中agent安排在A后面再調(diào)度即可，聯(lián)合調(diào)度所需時(shí)間最長(zhǎng)的agent的進(jìn)入A。

3） 一旦B中有agent進(jìn)入A，就需對(duì)集合A，B，C更新。

4） 在集合A內(nèi)部的博弈也是個(gè)反復(fù)的過(guò)程，經(jīng)過(guò)多次迭代優(yōu)化，如果結(jié)果穩(wěn)定就繼續(xù)從B集中挑選一個(gè)合適的agent加入A集。一旦B集為空，則整個(gè)調(diào)度過(guò)程結(jié)束。

5 實(shí)例分析

對(duì)如圖4產(chǎn)品結(jié)構(gòu)先進(jìn)行分解，得到多個(gè)agent，然后再進(jìn)行優(yōu)化調(diào)度。設(shè)定生產(chǎn)設(shè)備和裝配機(jī)器都是2臺(tái)，得到如圖5調(diào)度結(jié)果，可以得到問(wèn)題的最優(yōu)調(diào)度，且機(jī)器的工作負(fù)載均衡。利用本方法對(duì)多種產(chǎn)品結(jié)構(gòu)進(jìn)行調(diào)度，都能夠獲得滿意結(jié)果，對(duì)于產(chǎn)品結(jié)構(gòu)更復(fù)雜，機(jī)器數(shù)設(shè)置更多的情況，可以判斷出至少得到次優(yōu)結(jié)果。

6 結(jié)論

在混合流水生產(chǎn)過(guò)程中，要經(jīng)過(guò)多道加工工序和裝配工序的復(fù)雜產(chǎn)品的生產(chǎn)，其調(diào)度具有多目標(biāo)特征，本文采用合作博弈的方法基本可以較好的解決makespan最優(yōu)的調(diào)度問(wèn)題，實(shí)驗(yàn)結(jié)果也驗(yàn)證了本方法的有效性。同時(shí)，也可以采用本文提出的調(diào)度方法來(lái)解決類(lèi)似于機(jī)器負(fù)荷均衡、裝配件消耗均衡等其他問(wèn)題。

參考文獻(xiàn)

[1]徐俊剛，戴國(guó)忠，王宏安.生產(chǎn)調(diào)度理論和方法研究綜述[J].計(jì)算機(jī)研究與發(fā)展.2004，41（2）：257-267.

[2]唐立新，吳亞萍.混合流水車(chē)間調(diào)度的遺傳下降算法[J].自動(dòng)化學(xué)報(bào).2002，28（4）：637-641.

[3]任明，王成道.基于聯(lián)邦結(jié)構(gòu)的多agent協(xié)作[J].華東理工大學(xué)學(xué)報(bào).2004，30（3）：311-314.

[4] 羅伯特·吉本斯. 博弈論基礎(chǔ)[M]. 中國(guó)社會(huì)科學(xué)出版社.1999.3