基于柔性作業(yè)調(diào)度的離散制造車間布局優(yōu)化研究

薛冬娟，殷喜龍，潘 穎

（1.大連海洋大學(xué) 機(jī)械工程學(xué)院，大連 116023；2.大連海事大學(xué) 交通運(yùn)輸管理學(xué)院，大連 116023）

0 引言

離散制造業(yè)車間調(diào)度問題目前已從相對(duì)簡(jiǎn)單的經(jīng)典車間調(diào)度問題逐漸轉(zhuǎn)化為柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling ，F(xiàn)JSP），打破了經(jīng)典車間調(diào)度對(duì)某一產(chǎn)品的每個(gè)加工工序只能由一臺(tái)設(shè)備加工的約束，F(xiàn)JSP不僅要確定各產(chǎn)品加工工序的順序，而且要將各工序分配給不同的設(shè)備，從而保證所有產(chǎn)品的最大加工時(shí)間最短，屬于NP-hard難題。謝皓等[1]以最大完工時(shí)間最短為目標(biāo)，采用遺傳算法對(duì)一個(gè)8×8(8臺(tái)加工設(shè)備，8種工件)的問題進(jìn)行計(jì)算，并沒有考慮在實(shí)際生產(chǎn)中調(diào)度問題是典型的多目標(biāo)優(yōu)化問題。王碩、曹巖等[2,3]采用了一種改進(jìn)的蟻群算法對(duì)機(jī)器編碼,控制冗余解的數(shù)量，提高算法的計(jì)算速度，計(jì)算模型則是經(jīng)典的車間調(diào)度模型與實(shí)際生產(chǎn)有一定的差距。此外，有部分學(xué)者考慮了實(shí)際生產(chǎn)中車間調(diào)度問題屬于多目標(biāo)優(yōu)化問題，如劉烽等[4]針對(duì)混合流水車間多目標(biāo)調(diào)度問題，以最大流程時(shí)間和生產(chǎn)中所消耗的總能量最小為目標(biāo)函數(shù)，建立了混合整數(shù)規(guī)劃模型，采用NSGA2算法計(jì)算了12×8的調(diào)度問題。魏巍等[5,6]分別以加工成本、加工質(zhì)量、制造工期最短、設(shè)備利用率最大為目建立多目標(biāo)優(yōu)化模型，采用智能算法求解小規(guī)模的調(diào)度問題。曾強(qiáng)等[7,8]針對(duì)柔性作業(yè)車間調(diào)度問題中加工路徑的不確定性，以最長(zhǎng)完工時(shí)間最小和加工費(fèi)用最少以及設(shè)備利用率最高為目標(biāo)，建立多目標(biāo)調(diào)度問題模型。

綜合上述研究發(fā)現(xiàn)，現(xiàn)有的文獻(xiàn)主要存在兩點(diǎn)不足之處，一是在建立車間調(diào)度模型時(shí)沒有考慮足夠的約束和目標(biāo)，大多數(shù)研究目標(biāo)沒有考慮到在實(shí)際生產(chǎn)中應(yīng)當(dāng)盡量減少產(chǎn)品的搬運(yùn)距離/次數(shù)；二是在解決車間調(diào)度問題的同時(shí)并沒有考慮車間加工設(shè)備位置布局，造成車間內(nèi)的物料無效搬運(yùn)距離/次數(shù)增加。

針對(duì)上述不足，本文首先建立了以最大完工時(shí)間最小、總延期時(shí)間最小、總提前期時(shí)間最小、設(shè)備總負(fù)荷最小、單臺(tái)設(shè)備的最大負(fù)荷最小、總生產(chǎn)成本最低以及工件搬運(yùn)次數(shù)最少的多目標(biāo)車間生產(chǎn)優(yōu)化調(diào)度模型。然后，對(duì)于優(yōu)化的pareto解集采用AHP確定其最優(yōu)調(diào)度方案。再次，根據(jù)車間調(diào)度問題確定的產(chǎn)品加工工藝線路，以加工產(chǎn)品搬運(yùn)距離最少為目標(biāo)，對(duì)現(xiàn)有的車間設(shè)備布局進(jìn)行優(yōu)化，使車間無效的搬運(yùn)量最小。最后，以大連某空調(diào)生產(chǎn)車間為例，通過對(duì)一個(gè)10×10的車間調(diào)度進(jìn)行計(jì)算，驗(yàn)證了本文算法和模型的可行性。

1 離散車間多目標(biāo)調(diào)度數(shù)學(xué)模型

1.1 問題描述

多目標(biāo)FJSP是指在m臺(tái)設(shè)備（M={mk|1,2,…,m,k=1,2,…,m}）上加工n個(gè)工件（J={ji|j1,j2,…,jn,i=1,2,…,n），每個(gè)工件包含Ni個(gè)事先確定加工順序的工序，每個(gè)工序可以在多臺(tái)設(shè)備上加工，mij表示工件ji的第j道工序可使用的加工設(shè)備集合。Sijk為工件ji的第j道工序在設(shè)備k上開始加工時(shí)間，Eijk為工件ji的第j道工序在設(shè)備k上結(jié)束加工的時(shí)間，工件ji的第j道工序在設(shè)備k上的加工時(shí)間為tijk，Ti表示工件ji的最后一道工序的完工時(shí)間，Di表示工件ji的交貨時(shí)間，α表示單位時(shí)間延期交貨費(fèi)用為。工件ji的原材料費(fèi)用為Ci，不同設(shè)備單位時(shí)間的加工費(fèi)用用pk表示，單位時(shí)間的調(diào)整費(fèi)用為sk，用wijk表示工件ji的第j道工序在設(shè)備k上的調(diào)整時(shí)間。Xijk為決策變量，當(dāng)工件ji的第j道工序在設(shè)備k上加工時(shí)，取值為1，否則為0；Yikk為決策變量，當(dāng)工件ji的第j道工序與第j-1道工序都在設(shè)備k上加工時(shí)，取值1，否則為0；車間調(diào)度的目的是在有限的資源條件下，將各個(gè)工序分配到相匹配的設(shè)備上，從而達(dá)到車間生產(chǎn)的多個(gè)目標(biāo)組合最優(yōu)。

根據(jù)上述描述，本文作如下假設(shè)：1）一臺(tái)設(shè)備同一時(shí)刻只能加工一個(gè)工件；2）若某一工件加工的上一道工序加工完畢后，對(duì)應(yīng)的設(shè)備處于空閑狀態(tài)，則立即開始加工下一道工序；3）工件在每臺(tái)設(shè)備上的加工時(shí)間、裝卸時(shí)間都確定，并都作為加工時(shí)間計(jì)算；4）工序在每臺(tái)設(shè)備上的調(diào)整時(shí)間已知；5）工件加工一旦開始，就不能中斷，除非設(shè)備出現(xiàn)故障；6）所有設(shè)備一開始均處于正常狀態(tài)，即最初不存在故障設(shè)備；7）設(shè)備的故障率是通過長(zhǎng)時(shí)間對(duì)設(shè)備的觀測(cè)和維護(hù)所到的統(tǒng)計(jì)值，數(shù)據(jù)真實(shí)可靠；8）同一個(gè)工件，只有在上一道加工工序結(jié)束后才能進(jìn)行下一道工序；9）工件的加工順序不能改變。

1.2 目標(biāo)函數(shù)

1）最大完工時(shí)間最?。?/p>

2）總延期時(shí)間最?。?/p>

3）總提前期時(shí)間最小：

4）總生產(chǎn)成本最低：

5）設(shè)備總負(fù)荷最?。?/p>

6）單臺(tái)設(shè)備的最大負(fù)荷最?。?/p>

7）工件搬運(yùn)次數(shù)最少：

約束條件如下：

其中，式(8)表示：在同一時(shí)刻任意工件的某一工序只能由一臺(tái)設(shè)備加工；式(9)表示：同一工件的下一道工序的開工時(shí)間必須大于或等于該工件上一道工序的結(jié)束時(shí)間；式(10)表示：任意工件的結(jié)束時(shí)間大于等于該工件的開始時(shí)間、加工時(shí)間以及調(diào)整時(shí)間之和；式(11)表示：任意設(shè)備上新任務(wù)的開始必須在上一任務(wù)結(jié)束之后；式(12)工件的最后完工時(shí)間的；式(13)同一工件前后加工工序在同一設(shè)備的約束。

2 算法設(shè)計(jì)

由于車間調(diào)度問題屬于NP-hard難題，每個(gè)目標(biāo)之間存在復(fù)雜的關(guān)系，而且屬于非線性優(yōu)化模型，傳統(tǒng)優(yōu)化方法計(jì)算難度較大，因此本文采用一種基于雙層（加工工序和加工設(shè)備）編碼的改進(jìn)遺傳算法求解該問題。與傳統(tǒng)遺傳算法相比，確保染色體包含信息的全面性和完整性，同時(shí)采用最優(yōu)保存策略、錦標(biāo)賽選擇、序值以及擁擠距離選擇的方法，選擇種群個(gè)體中適應(yīng)度較高的遺傳給下一代。交叉和變異操作均采用隨機(jī)的兩點(diǎn)交叉和變異。為了保證下一代種群中個(gè)體的多樣性和防止搜索解陷入局部最優(yōu)解的循環(huán)中，本文將適應(yīng)度函數(shù)通過線性尺度轉(zhuǎn)換方法。

2.1 染色體編碼

本文采用基于加工工序和加工設(shè)備的兩層編碼的方式對(duì)染色體進(jìn)行編，確保染色體包含信息的全面性和完整性。染色體編碼采用整數(shù)編碼，每個(gè)染色體長(zhǎng)度為（n表示加工工件數(shù)，Ni表示第i個(gè)工件的工序數(shù)）。染色體分為兩部，前半部分表示工件的加工工序，后半部分表示加工工件的加工工序所對(duì)應(yīng)的加工設(shè)備順序。

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

本文把適應(yīng)度函數(shù)與目標(biāo)函數(shù)的轉(zhuǎn)化關(guān)系式定義如下：

在傳統(tǒng)遺傳算法的實(shí)際操作中會(huì)出現(xiàn)某一代中有一部分個(gè)體的適應(yīng)度值很高，是到目前為止所有種群中適應(yīng)度最高的個(gè)體，但是這些個(gè)體未必就是待優(yōu)化問題的最優(yōu)解或者近似最優(yōu)解，而可能是解空間中的局部最優(yōu)解。當(dāng)出現(xiàn)這種情況時(shí)，如果仍然按照原種群中個(gè)體適應(yīng)度函數(shù)來確定個(gè)體是否遺傳到下一代中，就會(huì)出現(xiàn)從下一代開始，以后各代的個(gè)體幾乎都不會(huì)改變。因?yàn)閺纳弦淮_始，在進(jìn)行選擇操作時(shí)，由于種群中適應(yīng)度較高的個(gè)體會(huì)排斥適應(yīng)度較低的個(gè)體，所以，以后每一代種群中適應(yīng)度較高的那些個(gè)體占據(jù)種群的絕大部分。根據(jù)個(gè)體進(jìn)化規(guī)則和選擇操作中最優(yōu)保存策略，這些適應(yīng)度較高的個(gè)體直接遺傳給下一代。所以，這種個(gè)體進(jìn)化會(huì)使種群基因的多樣性減小，甚至?xí)霈F(xiàn)上一代和下一代個(gè)體完全重合，這樣就會(huì)使搜索解停留在某一局部最優(yōu)點(diǎn)上。本文對(duì)某些適應(yīng)度較高的個(gè)體進(jìn)行人為的修訂，降低其適應(yīng)度，減小與其他個(gè)體適應(yīng)度的差異，限制這些個(gè)體的遺傳代數(shù)，增加適應(yīng)度較小的個(gè)體被選擇遺傳的概率，從而增加種群基因的多樣性，來避免這一現(xiàn)象的發(fā)生，達(dá)到使搜索解跳出局部最優(yōu)點(diǎn)的約束。

本文對(duì)適應(yīng)度函數(shù)采用線性尺度轉(zhuǎn)換方法，轉(zhuǎn)換公式如下：

其中，F(xiàn)為原適應(yīng)度函數(shù)，F(xiàn)'為轉(zhuǎn)換后的適應(yīng)度函數(shù)，a，b為轉(zhuǎn)換系數(shù)，一般c的取值范圍是1.2～2，本文取1.15，為所有個(gè)體適應(yīng)度的平均值，F(xiàn)max為所有個(gè)體中適應(yīng)度最高個(gè)體的適應(yīng)度值。

2.3 選擇操作

本文采用MATLAB工具箱中的錦標(biāo)賽選擇函數(shù)（Selection tournament），采用最優(yōu)保存策略，通過計(jì)算個(gè)體的序值和擁擠距離，選擇種群中序值較小的個(gè)體遺傳給下一代，當(dāng)種群中兩個(gè)個(gè)體的序值相同時(shí)，為了保持種群個(gè)體基因的多樣性，選擇擁擠距離大的個(gè)體遺傳給下一代。當(dāng)種群中個(gè)體的序值和擁擠距離都相等時(shí)，選擇子目標(biāo)中權(quán)系數(shù)較大的個(gè)體。通過多層次的比較、分析逐步對(duì)個(gè)體進(jìn)行適應(yīng)度排序，淘汰適應(yīng)度小的個(gè)體，選擇種群個(gè)體中適應(yīng)度較高的遺傳給下一代。

2.4 交叉操作

種群中的個(gè)體通過按一定的交叉概率，將染色體上的基因隨機(jī)的交叉，得到新的個(gè)體，增加了種群基因的多樣性。隨機(jī)從種群中選擇兩個(gè)染色體，根據(jù)染色體編碼的方法，先取出染色體的前半部分，其長(zhǎng)度為，采用雙點(diǎn)交叉的方法，隨機(jī)的設(shè)定兩個(gè)交叉點(diǎn)進(jìn)行交叉操作。交叉后會(huì)出現(xiàn)某些工件的工序多余，某些工件的工序缺失，因此，需要按照原有基因?qū)⒔徊婧蟮幕驅(qū)?yīng)的設(shè)備順序進(jìn)行調(diào)整。

2.5 變異操作

2.6 解碼操作以及終止代數(shù)的確定

本文采用的染色體解碼方法是全自動(dòng)動(dòng)解碼方法。對(duì)于給定的一個(gè)染色體S而言，先計(jì)算其基因個(gè)數(shù)，然后取其基因的前半部分，根據(jù)解碼公式進(jìn)行解碼。例如染色體S[3214132423431224]，共有16個(gè)基因，因?yàn)椴捎玫氖腔诩庸すば蚝图庸ぴO(shè)備的兩層編碼方式，所以取其基因的前半部分，共有8個(gè)基因分別為[32141324]。從上述基因中可以看出有4種工件，工序總數(shù)為8，分別根據(jù)下面程序進(jìn)行解碼。

2.7 改進(jìn)遺傳算法

傳統(tǒng)的遺傳算法采用的是隱性精英解保留策略，雖然保證了種群個(gè)體基因的完整性，但是在求解多目標(biāo)問題的時(shí)候，可能會(huì)使Pareto解集出現(xiàn)過早收斂的現(xiàn)象。本文對(duì)Pareto解集采用改進(jìn)的是三層評(píng)判標(biāo)準(zhǔn)的選擇策略，首先通過計(jì)算序值，其次計(jì)算擁擠距離，最后根據(jù)各目標(biāo)的模糊評(píng)價(jià)決策得到的綜合評(píng)價(jià)指標(biāo)進(jìn)行排序，選擇最優(yōu)的Pareto解集。改進(jìn)的遺傳算法流程圖如圖1所示。

圖1 改進(jìn)的遺傳算法流程圖

3 實(shí)例分析

本文以大連市某企業(yè)空調(diào)制造車間為例，該車間某一時(shí)刻的10個(gè)工件需要在10臺(tái)設(shè)備上加工，每個(gè)工件都要經(jīng)過6道加工工序，具體數(shù)據(jù)如表1～表5所示：

表1 工序可選設(shè)備表

表2 工序加工時(shí)間表

表3 工件的原材費(fèi)用表

表4 工件交貨日期表

表5 設(shè)備單位時(shí)間加工費(fèi)用表

本文的遺傳算法參數(shù)為：種群中個(gè)體數(shù)目500，種群進(jìn)化代數(shù)500，種群代溝0.8，交叉概率0.6，變異概率0.1。

經(jīng)計(jì)算所得，傳統(tǒng)遺傳算法得到的pareto解集中最優(yōu)解對(duì)應(yīng)的最小加工時(shí)間為60分鐘。

采用基于最優(yōu)保存策略、序值排序、擁擠距離計(jì)算、綜合指標(biāo)排序、適應(yīng)度函數(shù)轉(zhuǎn)化以及工件加工工序和設(shè)備的兩層編碼方式的改進(jìn)遺傳算法的實(shí)例測(cè)試如圖2和圖3所示。

圖2 采用改進(jìn)遺傳算法的種群解的變化

圖3 采用改進(jìn)遺傳算法的零件加工甘特圖

由于篇幅有限，本文只摘取6組比較優(yōu)越的pareto解，如表6所示，然后通過AHP綜合評(píng)價(jià)選擇最佳的調(diào)度方案。各子目標(biāo)的權(quán)重為：ω=（0.358， 0.2003，0.0872，0.2396，0.0461，0.0257，0.0431）T，最終選擇調(diào)度方案3。

表6 pareto解集

經(jīng)計(jì)算所得的，改進(jìn)遺傳算法得到的pareto解集中最優(yōu)解對(duì)應(yīng)的最小加工時(shí)間為53分鐘。根據(jù)計(jì)算結(jié)果可知，改進(jìn)后的遺傳算法的綜合評(píng)價(jià)指標(biāo)比改進(jìn)前的優(yōu)越。所以本文的調(diào)度方案更加適應(yīng)解決離散車間多目標(biāo)調(diào)度問題。

本文對(duì)車間的設(shè)備進(jìn)行環(huán)形布局優(yōu)化，建立如下數(shù)學(xué)優(yōu)化模型。

其中，wij為設(shè)備i到設(shè)備j的當(dāng)量物流量，是根據(jù)工件加工工藝線路轉(zhuǎn)化的，例如，工件1的加工工藝路線為3-1-2-7-8-5，則 w31= w12= w27= w78=w85=1。xij為0,1變量，如果設(shè)備i在生產(chǎn)線上的位置排在設(shè)備j前，取值為1，否則為0。目標(biāo)函數(shù)(19)在保證所有工件加工完的前提下，使整個(gè)車間的逆向搬運(yùn)物流量最?。患s束(20)設(shè)備相對(duì)位置的約束，約束(21)確保設(shè)備位置在傳遞過程中不出現(xiàn)矛盾。

經(jīng)計(jì)算得到圖4加工設(shè)備環(huán)形布局圖，其中(1)和(2)兩個(gè)方案工件總的逆向搬運(yùn)物流量都為17，總的無效搬運(yùn)量都為237。與優(yōu)化前的車間布局（設(shè)備擺放位置為1-2-3-4-5-6-7-8-9-10）相比，總的無效搬運(yùn)量從270減為237。

4 結(jié)束語

本文首先采用傳統(tǒng)的遺傳算法對(duì)空調(diào)制造車間10×10的案例進(jìn)行求解，然后采用本文所提出的改進(jìn)的遺傳算法對(duì)上述給定的案例進(jìn)行求解，通過對(duì)比兩個(gè)方案的綜合評(píng)價(jià)指標(biāo)，可以證明本文提出的改進(jìn)的遺傳算法在求解同一車間調(diào)度問題中的優(yōu)越性。最后根據(jù)車間調(diào)度確定的工件加工工藝路線，實(shí)現(xiàn)了對(duì)現(xiàn)有車間制造設(shè)備進(jìn)行環(huán)形布局優(yōu)化。

圖4 加工設(shè)備環(huán)形布局圖

[1]謝皓,應(yīng)保勝,袁波.基于遺傳算法的路徑柔性作業(yè)車間調(diào)度優(yōu)化[J].武漢科技大學(xué)學(xué)報(bào),2012,35(6):465-468.

[2]王碩,顧幸生.基于改進(jìn)蟻群算法的作業(yè)車間調(diào)度[J].青島科技大學(xué)學(xué)報(bào),2012,10(5):489-494.

[3]曹巖,雷蕾,房亞東.蟻群算法在離散型車間派工中的應(yīng)用[J].西安工業(yè)大學(xué)學(xué)報(bào),2011,12(7):611-615,643.

[4]劉烽,游海,丁一鈞,楊濤,聶電開.基于NSGA2算法的混合流水車間多目標(biāo)調(diào)度問題研究[J].電腦編程技巧與維護(hù),2012,(24):86-87.

[5]楊開兵,劉曉冰.流水車間成組工件調(diào)度問題的多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2012,12(12):3343-3346.

[6]Rubiyah Y,Marzuki K,Gan T H.Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm[J].Applied Soft Computing,2013,11(8):5782-5792.

[7]曾強(qiáng),沈玲,楊育,宋紅娜.多目標(biāo)等量分批柔性作業(yè)車間調(diào)度集成優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(16):237-243.

[8]Cowling P I,Johansson M.Using real-time information for effective dynamic scheduling[J].European Journal of Operational Research,2012,139(2):230-244.