劉建國　王廷梅　李愛菊

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）13-0221-02

1 研究背景

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

2 問題原型

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

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

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

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

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

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

4 多agent調(diào)度

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

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

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

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

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

3） 一旦B中有agent進入A，就需對集合A，B，C更新。

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

5 實例分析

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

6 結(jié)論

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

參考文獻

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

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

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

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