基于柔性作業調度的離散制造車間布局優化研究

薛冬娟，殷喜龍，潘 穎

（1.大連海洋大學 機械工程學院，大連 116023；2.大連海事大學 交通運輸管理學院，大連 116023）

0 引言

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

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

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

1 離散車間多目標調度數學模型

1.1 問題描述

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

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

1.2 目標函數

1）最大完工時間最?。?/p>

2）總延期時間最?。?/p>

3）總提前期時間最小：

4）總生產成本最低：

5）設備總負荷最?。?/p>

6）單臺設備的最大負荷最小：

7）工件搬運次數最少：

約束條件如下：

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

2 算法設計

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

2.1 染色體編碼

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

2.2 適應度函數

本文把適應度函數與目標函數的轉化關系式定義如下：

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

本文對適應度函數采用線性尺度轉換方法，轉換公式如下：

其中，F為原適應度函數，F'為轉換后的適應度函數，a，b為轉換系數，一般c的取值范圍是1.2～2，本文取1.15，為所有個體適應度的平均值，Fmax為所有個體中適應度最高個體的適應度值。

2.3 選擇操作

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

2.4 交叉操作

種群中的個體通過按一定的交叉概率，將染色體上的基因隨機的交叉，得到新的個體，增加了種群基因的多樣性。隨機從種群中選擇兩個染色體，根據染色體編碼的方法，先取出染色體的前半部分，其長度為，采用雙點交叉的方法，隨機的設定兩個交叉點進行交叉操作。交叉后會出現某些工件的工序多余，某些工件的工序缺失，因此，需要按照原有基因將交叉后的基因對應的設備順序進行調整。

2.5 變異操作

2.6 解碼操作以及終止代數的確定

本文采用的染色體解碼方法是全自動動解碼方法。對于給定的一個染色體S而言，先計算其基因個數，然后取其基因的前半部分，根據解碼公式進行解碼。例如染色體S[3214132423431224]，共有16個基因，因為采用的是基于加工工序和加工設備的兩層編碼方式，所以取其基因的前半部分，共有8個基因分別為[32141324]。從上述基因中可以看出有4種工件，工序總數為8，分別根據下面程序進行解碼。

2.7 改進遺傳算法

傳統的遺傳算法采用的是隱性精英解保留策略，雖然保證了種群個體基因的完整性，但是在求解多目標問題的時候，可能會使Pareto解集出現過早收斂的現象。本文對Pareto解集采用改進的是三層評判標準的選擇策略，首先通過計算序值，其次計算擁擠距離，最后根據各目標的模糊評價決策得到的綜合評價指標進行排序，選擇最優的Pareto解集。改進的遺傳算法流程圖如圖1所示。

圖1 改進的遺傳算法流程圖

3 實例分析

本文以大連市某企業空調制造車間為例，該車間某一時刻的10個工件需要在10臺設備上加工，每個工件都要經過6道加工工序，具體數據如表1～表5所示：

表1 工序可選設備表

表2 工序加工時間表

表3 工件的原材費用表

表4 工件交貨日期表

表5 設備單位時間加工費用表

本文的遺傳算法參數為：種群中個體數目500，種群進化代數500，種群代溝0.8，交叉概率0.6，變異概率0.1。

經計算所得，傳統遺傳算法得到的pareto解集中最優解對應的最小加工時間為60分鐘。

采用基于最優保存策略、序值排序、擁擠距離計算、綜合指標排序、適應度函數轉化以及工件加工工序和設備的兩層編碼方式的改進遺傳算法的實例測試如圖2和圖3所示。

圖2 采用改進遺傳算法的種群解的變化

圖3 采用改進遺傳算法的零件加工甘特圖

由于篇幅有限，本文只摘取6組比較優越的pareto解，如表6所示，然后通過AHP綜合評價選擇最佳的調度方案。各子目標的權重為：ω=（0.358， 0.2003，0.0872，0.2396，0.0461，0.0257，0.0431）T，最終選擇調度方案3。

表6 pareto解集

經計算所得的，改進遺傳算法得到的pareto解集中最優解對應的最小加工時間為53分鐘。根據計算結果可知，改進后的遺傳算法的綜合評價指標比改進前的優越。所以本文的調度方案更加適應解決離散車間多目標調度問題。

本文對車間的設備進行環形布局優化，建立如下數學優化模型。

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

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

4 結束語

本文首先采用傳統的遺傳算法對空調制造車間10×10的案例進行求解，然后采用本文所提出的改進的遺傳算法對上述給定的案例進行求解，通過對比兩個方案的綜合評價指標，可以證明本文提出的改進的遺傳算法在求解同一車間調度問題中的優越性。最后根據車間調度確定的工件加工工藝路線，實現了對現有車間制造設備進行環形布局優化。

圖4 加工設備環形布局圖

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

[2]王碩,顧幸生.基于改進蟻群算法的作業車間調度[J].青島科技大學學報,2012,10(5):489-494.

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

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

[5]楊開兵,劉曉冰.流水車間成組工件調度問題的多目標優化算法[J].計算機應用,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]曾強,沈玲,楊育,宋紅娜.多目標等量分批柔性作業車間調度集成優化方法[J].計算機工程與應用,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.