基于博弈粒子群算法的混流混合車間調度研究

魯建廈，胡海芬，董巧英

(浙江工業大學 機械工程學院，浙江 杭州 310014)

?

基于博弈粒子群算法的混流混合車間調度研究

魯建廈，胡海芬，董巧英

(浙江工業大學 機械工程學院，浙江 杭州 310014)

摘要：為了有效解決混流混合車間生產調度的全局優化問題，同時考慮部件車間、總裝車間的齊套及平順化要求，部件車間與零件車間緩存區存量控制要求，建立了以總裝車間部件平順化、部件車間齊套性和加工車間緩存區庫存最小為優化指標的多目標調度模型.同時為解決多目標調度目標之間的矛盾關系，運用博弈粒子群算法進行求解.算法通過PSO對各車間按不同優化指標進行搜索求解并加入博弈理論以解決陷入單目標局部最優的缺陷，從而獲得總生產系統全局最優.最后運用實例對模型和算法進行有效性驗證.

關鍵詞：混合車間；調度；齊套性；博弈；粒子群

車間調度問題是困擾學者的一類典型NP難題，由于其可以給企業帶來明顯的經濟效益，因此引起了企業界和學術界的廣泛關注.對于加工裝配型企業，產品由零件、部件最后總裝成成品.并且如今在多元化發展的趨勢下，企業為了順應時代的步伐更多的運用混流裝配方式進行產品的裝配.從之前的研究可知已有大量對于混流裝配線及作業車間的單獨調度研究，以及對混合車間的單目標整體研究.李平[1]研究在不確定條件下的混流裝配線和作業車間的結合調度問題，建立了存在確定性吸收的調度數學模型，并且在其主動預調度的前提下建立自適應性柔性車間擾動—反應模型.將貝葉斯理論引入到不確定調度系統中，建立模型，并與原有模型對比.胡恒[2]，施錦峰[3]就混流混合車間建立了模糊調度和魯棒調度模型，并就車間的模糊或不確定信息表現在模型中，最終利用智能算法求解模型.李修琳[4]將零件、部件、產品三部分綜合一起編碼，并運用模擬退火和遺傳算法的混合算法對在制品成本最小的目標進行計算.之前的研究雖然可以在一定程度上反應車間的情況，卻不能更完整的全局的映射混合車間的生產狀況.而在生產管理中，各車間都有其特點，因此進行全局考慮排產非常重要.筆者對混流混合車間進行全局的建模與優化，即可以顧及各車間的優化特點建立不同模型，又能全局的聯系整個生產及裝配車間.

多目標調度已有大量的研究文獻，但處理各目標關系更多采用經驗求權重計算方法，其局限于經驗者的主觀臆斷，優值則會因人而異.為了使結果更加客觀，運用博弈論[5]對各車間目標進行整合求解.國內外研究博弈論主要面向經濟學，在生產方面研究較少，并且也只運用在單機或單條流水線中[6].Calleja[7]提出了單客戶多任務及單任務多客戶的單機調度問題.由于博弈論是對幾個相互關聯、影響的決策者的理性決策，并且對這些決策結果進行均衡研究的理論，因此即可以避免決策者的主觀臆斷，又能對多目標進行求解.筆者運用博弈理論來平衡混流混合車間多目標之間的矛盾關系，并求解各車間之間的納什均衡作為最終的全局優化解.

1混流混合車間模型

混合車間一般由兩部分或兩部分以上不同車間組成.圖1為筆者所研究的混流混合車間模型.該模型由三部分組成：第一部分為零件作業車間，第二部分為部件裝配線，第三部分為總裝線，各部分之間存在緩存區.

圖1　混合車間模型Fig.1　Mixed-model and mixed-flow production

混合車間調度問題數學描述如下：

作業車間：有M=(m1，m2，…，mm)臺機器，其中mi表示第i個機器，i=(1，2，…，m)，加工r=(r1，r2，…，rr)批零件，同批零件加工工藝相同，不同批工藝由不同的事先規定的加工工藝決定；部件線：有一條具有個工位的部件線，加工個部件，每個部件需經過F道工序；總裝線：包括H=(h1,h2,…，hn)個訂單產品，表示第個訂單產品；經過D=(1，2，…，d)個工位對產品進行裝配，其中表示產品的第道工序.

混流混合車間具有的特點包括：

1) 總裝線和部件線裝配都是以混流的方式裝配.

2) 零件作業車間、部件線、總裝線之間設有緩沖區.

3) 上下游環節生產相互關聯，下游裝配受上游零部件加工影響.總裝線需要某零部件成套時才開始總裝，若裝配線所需要的零部件沒有及時供應，則將造成等待.

4) 混合車間生產是零件作業車間以批為單位生產零件，部件及總裝線以件為單位進行混流裝配，因此前后生產批量不一致將導致庫存，增加成本.

2基于博弈的車間調度模型

為了客觀評價多目標調度問題，解決各車間目標函數之間的矛盾關系，將博弈理論運用到混合車間調度中，并且摒棄歷史研究中將加工方或者客戶作為博弈的參與者，而將加工/裝配區域分別抽象化為不同的局中人，并分開運算局部最優解，將最優策略以及次優策略抽象為局中人的策略空間，最優值抽象為收益函數.表1為車間調度中的元素與博弈中要素的一一映射關系.

表1　車間調度與博弈映射

2.1單條混流總裝線調度模型

混流生產線的優勢為減少零部件需求波動大的問題，因此零部件需求的平順化為其特殊優化目標.設置需求平順化即對總裝線的生產序列進行合理的規劃以使對零部件的需求盡量均衡，從而可以確保上游加工線中的零部件能均衡產出.根據文獻[8]并考慮零部件庫存，建立平順化優化模型為

(1)

s.t.qik∈{0,1}?i∈Ik=1,2,…,K

(2)

(3)

(4)

(5)

(6)

(7)

式中:qik用于判斷產品i的生產位置，是0，1變量；式(3,4)分別表示序列k的位置上只會排一個產品和需要裝配的產品i的數量；yik表示從1到k個產品中產品i的數量；xjk為裝配yik個產品需要前工位提供j的數量；Nj為所需部件j的總數量；hi為產品i的訂單需求數量；di是為i產品的庫存量；bij為一個產品i需要部件j的數量；Sj為緩沖區零部件j的庫存；目標函數式(1)表示最小化部件j的實際需求和平均需求的差的平方，目的盡可能使需求量與平均值相等.

2.2部件裝配線調度模型

0,1判斷式為

(8)

齊套系數為

(j=1,2,…，nh;1≤h≤H)

(9)

建立數學優化模型為

(10)

由于總裝線目標函數求最小值，為了一致性，將式(10)處理后也求解最小值，則數學模型改為

(11)

(12)

(13)

(14)

j,g∈[2,nh]i,h∈[1,H]

k=2,3,…，K

(15)

(16)

式(11)即為目標函數并且以成套訂單加權和的倒數表示；式(12)表示裝配序列中第一個部件在裝配線上的第一個工位的完成時間；式(13)代表第一個部件在裝配線其余工位的完成時間；式(14)代表序列中從第二個開始，其余部件在的第一工位完工時間；式(15)表示從序列二開始，其在部件線工位2及以后工位的完成時間.

2.3作業車間調度模型

作業車間調度問題具有工件在不同機器上加工和加工順序不同的特點，因此可以簡單描述成：存在n個零件和M臺機器，每個零件已知有Yx道工序，且每道工序對應的機器和時間都是定值，其調度就是如何安排零件生產順序和工序間隔，使調度目標最優.本節以準時制生產為目標，最小化上游零件完成時間和下游需求時間之差.

數學模型表示為

(17)

s.t. Cxtk-Cx(y-1)h≥txyk,1≤x≤n,

1≤y≤Yx,1≤k,h≤M

(18)

Chjk-Cgdk≥thjk,1≤h,g≤n,

1≤j,d≤Yx,1≤k≤M

(19)

Cxyk=max(C(x-1)gk,Cx(y-1)h)+txyk

1≤i≤n,g,j∈[1,Yx]，k,h∈[1,M]

(20)

式中:Cxyk表示零件x的第y道工序在機器k上的完成時間；txyk表示零件x的第y道工序在機器k上的加工時間；Cx為零件x被加工出來的完工時刻；Tx表示零件x被領走的下游工序的開始時刻；式(18)即表示工件x的加工時間約束，需要在第y-1道工序完工以后才可以加工第y道工序；式(19)表示機器k的資源約束，即在k上不能加工不同的工件，需要一個完成后才能加工.

3調度模型求解算法設計

多目標問題的解往往有多個，并且存在難以決策的情況.通常在實際問題上可以通過優化者對該問題的了解和偏好來選擇最優解，但存在主觀臆斷，結果并不理想.通過一個博弈理論將主觀因素量化為可計算、可分析因素，并將其融入普通粒子群算法中，設計了博弈粒子群算法用于求解多目標混合車間調度問題.

3.1基本粒子群算法

Vi,j(t+1)=ωVi,j(t)+c1×r1×[pbest(i,j)-xi,j(t)]+

c2×r2×[gbest(j)-xi,j(t)]

(21)

xi,j(t+1)=xi,j(t)+Vi,j(t+1)

(22)

式中ω為慣性權重，ω越大則全局搜索能力越強，時間也越長.如果設置的ω較小則局部搜索能力增強，時間減少.因此，可以引入動態慣性權值ω為

(23)

式中:ωmax為最大慣性權重，一般取0.9；ωmin為最小慣性權重，一般取0.4；kmax為最大迭代次數；k為當前迭代次數.c1，c2為粒子學習因子，用于調節粒子向個體及全局極值點方向飛行的最大步長，可以設置c1=c2=2.r1、r2為在(0,1)內變化的隨機數.對于粒子群算法中的速度V應設置其取值范圍[Vmin,Vmax]以防止粒子速度過大而超出粒子搜索范圍或速度過小而早期收斂，位置Xi的取值范圍為Xmin～Xmax.

3.2博弈粒子群算法

由第2節介紹可知：各車間優化目標之間會產生矛盾關系，只用普通PSO算法無法客觀求得整體調度最優解，而各車間之間的矛盾關系與博弈理論中不同局中人之間的博弈關系相似，因此筆者提出增加博弈理論的博弈粒子群算法(Gameparticleswarmoptimization，GPSO)來求解混流混合車間的最優排序問題.博弈粒子群算法是在普通PSO算法的基礎上，將每次迭代產生的粒子抽象為不同的策略，也代表不同解.每一次群體更新都會產生多個策略，在每一次迭代更新過程中，各個局中人都會希望將收益函數最高的策略保留下來.但各局中人之間都相互聯系和影響，因此，局中人A的最優策略可能會使局中人B產生較差的結果，即對于各局中人的不同決策，會產生不同的結果.而納什均衡即達到一個所有決策者都可接受的穩定的較優解，任何一個決策者不改變自己的決策，其他決策者只要改變就會造成收益的減少.

算法在每次種群更新的過程中都會產生各種群(局中人)的博弈，每個粒子代表博弈的純策略，各粒子在其策略空間內搜尋最優的策略，并將最優策略用于博弈.在重復博弈中，各局中人根據納什均衡特點對其策略進行調整以達到各局中人都滿意的解.在算法的每次迭代更新中，粒子群中各粒子會向納什均衡解的同伴粒子進行學習，通過學習，不同局中人中的粒子會調整各自的策略使粒子趨向最終納什均衡[11].

3.2.1編碼方案設計

參考遺傳編碼中的編碼方式，數字代表各工位.其中編碼方式分為兩種，對于總裝車間和部件車間的編碼方式可以根據產品數量比例確定生產循環后用最小生產循環的產品序列進行編號，其維度為產品數量.其中相同數字代表同種產品，其粒子xp=(x1,x2,…，xn)代表總裝線或部件線的產品排序.例如投產A，B，C種產品分別為2，1，2個，則其編碼為Xp=(1,1,2,3,3)對于零件車間粒子的策略(加工)信息可以用一個L維向量來表示，L=n×m，其中n和m分別表示工件和機器數量.xp=(x1,x2,…，xn×m)編號代表不同零件以及各零件的加工順序，比如編碼(1 1 2 3 3 2)代表先生產零件1的第一個工位和第二個工位再生產零件2的第一個工位和零件3的第一個工位，可知相同數字代表同種零件且按順序確定工位號.

由于尋優目標是工件的最優排序，因此需要粒子更新改變工件的順序，但是實際上PSO算法迭代更新的都是分量的值.因此需要加入一個位置向量Y=(Y1,Y2,…，Ym)每次以工件排序為初始值，經過迭代后所得結果即為位置向量，并將位置向量進行從小到大排序即為工件排序.

例如經過一次迭代結果見表2.

通過排序：1(1.8)<2(2.7)<1(3.3)<3(3.5)<3(3.9)<2(4.1)<2(5.2)<1(6.6)，這樣可以得到一個可行解.Xp={1,2,1,3,3,2,2,1}為了防止產生非法解，對迭代產生粒子的順序進行約束條件檢驗.對于違背約束的粒子進行位置修正.

表2　某粒子向量初始值及迭代值

3.2.2算法描述

Step 1給出粒子群規模N，速度Vmax，最大迭代次數Tmax，Pareto解集上限2，ωmax，ωmin.并初始化每個粒子的位置X和速度V.

Step 2根據之前的編碼方法對各分量進行排序，生成有序的調度可行方案.

Step 3對調度方案進行解碼，計算粒子適應度值，比較第一次迭代產生的適應值確定最好的為全局最優值gbest，具研究的目標函數來看，最優值為最小值；第一次迭代的各粒子適應值分別為其局部最優值pbest.具體解碼過程以總裝線為例表述如下：

1) 給每個粒子分別設置向量：Tk,Nj,n,Naverage.從粒子向量中順序讀取第K個產品，查找產品零部件j的需求，記錄入Nj，同時根據加工時間確定第k個產品需要部件j的時刻并查找庫存在Tk時刻的部件j的數量sj再與Naverage相減，將平方差值錄入N.順序讀取下一個產品，將各零件所需的值和緩存區該零件的值與平均值的平方差再加入到N中直到最后一個產品處理結束.N即為該粒子的適應值.

2) 計算所有粒子適應值，N最小為當前最優粒子，將最優粒子與全局最優值比較，若小則替換gbest，并置換Pareto解集中的解；若大則保持原gbest，如果相等則作為Pareto解集中的一個解保留下來.如果此代粒子Pareto解集中只有一個解則在粒子群中查找次優粒子備用.

根據不同目標函數對部件線和零件作業車間按相同方法解碼并獲得全局最優和局部最優，再將總裝線、部件線和零件線作為博弈對象進行三人博弈，并用劃線法求得納什均衡解分別賦值于gbest，pbest.

Step 4根據公式(21～23)進行迭代以及速度和位置的更新.

Step 5確定是否到達迭代次數Tmax，沒達到則繼續Step 2，直到迭代第Tmax次，輸出全局最優值.

其中可以將博弈的偽碼描述如下：

定義變量：

COUNT(組合策略)//COUNT表示博弈比較中該組合較優的次數

N//表示總比較次數

INPUT：各局中人的不同策略相互組合所得的每個局中人的收益值；策略組合數

OUTPUT：納什均衡解//各車間全局極值

Begin：

For1toN

總策略數中取兩種策略組合進行對比

If<所對比策略組合中的策略有且只有一個不同>then

比較不同策略所對應的收益值的大小

元素收益值小者所在的COUNT(組合策略):=COUNT(組合策略)+1

End

End

取COUNT(組合策略)值最大的策略組合為納什均衡解

End

4實例驗證

為了驗證博弈粒子群算法對混流混合車間多目標調度問題求解有效性，選擇以多產品加工企業的混合車間為例進行調度運算.

實例為加工A,B,C三種產品且加工量分別為2，4，2臺.其中A產品需要一個零件a和一個部件M；B產品需要一個零件b和一個部件R；C產品需要一個零件c和一個部件W；一個部件M需要一個零件d；一個部件R需要一個零件e；一個部件W需要一個零件f.表3為產品所需零部件對應表.

表3　產品所需零部件對應表

表4,5為總裝產品A，B，C對應的工藝及作業時間和部件M，R，W的裝配工藝及時間.其中總裝線工序1時分別需要零件a，b，c，工序3時分別需要部件M，R，W；部件線工序2時需要零件d，e，f.

表4　總裝裝配工序及時間

表5　部件裝配工藝及時間

自制件在機器上的加工以2個為一批進行加工，表6為其工藝順序、加工時間和所對應機器.

表6　零件加工工位及對應時間

表7為按3.2.1編碼方案進行的編碼，數字1代表a零件，2和3代表b零件以此類推.根據已知條件A，B，C的產量分別為2，4，2臺，其最小生產循環為1︰2︰1，因此可以對其進行初始化為(12 13 13 14 12 13 13 14).根據已知條件同時可以知道部件線所需部件M，R和W分別為2，4，2個，則其最小生產循環為1︰2︰1，可以初始化為(9 10 10 11 9 10 10 11).零件區域所需a，b，c，d，e，f零件分別為2，4，2，2，4，2 個.按批量為2來生產零件，則其零件最小循環為1︰2︰1︰1︰2︰1.按照之前的編碼標準進行編碼并運用PHP語言對目標及算法進行編程計算.設置初始值分別為種群大小20，迭代次數100次，最大速度為10.根據給定條件運行博弈粒子群算法求得零件、部件和總裝調度方案分別為{5 6 8 5 1 6 5 1 2 7 8 6 5 2 1 8 6 7 1 7 8 2 4 3 4 2 7 3 4 4 3 3}；{9 9 10 10 11 11 10 10}；{12 12 13 13 14 14 13 13}.其總完工時間為360，圖2為用Matlab畫出零件甘特圖.

表7　實例中的工序編號

圖2　零件甘特圖Fig.2　Parts Gantt

通過順序求解各車間最優序列以對比筆者算法的優越性，并求得零件、部件和總裝調度方案分別為{1 5 6 2 1 6 1 5 8 2 6 2 4 6 5 1 8 4 2 8 5 7 3 3 8 4 7 3 4 7 3 7}；{10 10 9 11 9 11 10 10}；{13 13 12 14 13 13 12 14}.其總完工時間為386.

分別用博弈粒子群算法與順序求解粒子群法，求得零件、部件和總裝生產最大完工時間對比仿真結果，如表8所示.GPSO求解與順序PSO求解所得結果的偏差為

通過表8對比結果可以看出：順序PSO在零件部分和部件部分可以得到比GPSO算法更優，但在總裝部分沒有GPSO算法優.通過對結果的分析，得出GPSO可以對總體進行一個尋優，而作為混流混合車間更需要整體的協調和求整體較優解.

5結論

以總裝車間平順化、部件車間齊套性和零件車間緩存區最小為調度模型，極大的考慮了各車間的不同生產特點.在求解算法選擇上，以基本粒子群算法分別迭代各車間，同時運用博弈論對各車間迭代結果進行評價選擇.博弈粒子群算法即具有粒子群算法的規則簡單優點又克服了其陷于局部最優的缺點.最后通過一個實際算例來驗證算法與模型的有效性.所研究的混流混合車間調度問題極大的貼近現實生產，所設多目標優化比各學者歷史研究更能體現混流混合車間特性.實例中使用的PHP腳本語言計算為之后混流混合車間調度在bs架構下的原型系統設立奠定基礎.

參考文獻：

[1]李平.不確定條件下混裝和作業車間調度問題研究[D].武漢:武漢科技大學,2013.

[2]胡恒，魯建廈，李英德，等.基于多群體并行遺傳算法的混流混合車間模糊調度研究[J].浙江工業大學學報,2012,40(5):554-558.

[3]魯建廈,施錦峰,李修琳，等.一類已知概率分布下的混合車間魯棒調度問題研究[J].中國機械工程,2012,21(19):2328-2333.

[4]李修琳,魯建廈,柴國鐘,等.基于混合遺傳算法的混流混合車間協同調度問題[J].中國機械工程,2012,23(8):935-940.

[5]TIJS S, DEIESSEN T, Game theory and cost allocation problems [J]. Management Science,1986,32(8):1015-1028.

[6]周艷平.基于博弈理論的多目標生產調度問題研究[D].上海:華東理工大學,2012.

[7]CALLEJA P, ESTEVEZ-FERNANDEZ A, BORMP. Job scheduling cooperation and control[J].Operations Research Letters,2006,34(1):22.

[8]王炳剛.混流加工/裝配系統集成優化研究[J].機械工程學報,2010,46(17)：114-121.

[9]周水銀，陳榮球.單機加權成套訂單數遺傳算法研究[J].系統工程.2005,23(5)：22-24.

[10]韓冬梅,王麗萍,吳秋花. 基于模糊偏好的多目標粒子群算法在庫存控制中的應用[J]. 浙江工業大學學報,2012,40(3):348-351.

[11]李曉,金壽松,馮定忠，等. 基于合作博弈托盤租賃聯盟收益分配的研究[J]. 浙江工業大學學報,2012,40(1):84-87.

(責任編輯：陳石平)

Game theory and particle swarm optimization for mixed-model

hybrid-shop scheduling problem

LU Jiansha, HU Haifen, DONG Qiaoying

(College of Mechanical Engineering, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:The paper focused on solving the scheduling global optimization problem for mixed-model hybrid-shop, which consider the request of complete kit part consumption and the inventory control of buffer zone between job shop and Flow shop，then three objectives are given: minimizing the total variation in parts consumption in the assembly line, complete kitting of parts in the part line and minimizing buffer in the job shop. Then the GPSO algorithm is used to solve the problem of contradiction among the multi-objective scheduling objectives. The algorithm can use PSO to search local optimum of each part then the game-theory try to solve the problem to get the global optimum. Finally, an example was given to test the model and algorithm, and the results prove the method is effective and excellent.

Keywords:hybrid-shop; scheduling; complete kit; game theory; PSO

文章編號：1006-4303(2015)04-0398-07

中圖分類號：TP301

文獻標志碼：A

作者簡介：魯建廈(1963—)，男，浙江余姚人，教授，博導，研究方向為精益生產、生產調度和制造業信息化，E-mail：ljs@zjut.edu.cn.

基金項目：浙江省自然科學基金資助項目(LQ14E050004, LY12E05021)

收稿日期：2015-03-05