張守京,杜昊天,侯天天

(1. 西安工程大學 機電工程學院,西安 710600; 2. 西安工程大學 西安市現代智能紡織裝備重點實驗室,西安 710048)

車間調度是智能制造管理和決策的基礎。柔性作業(yè)車間調度 (Flexible job scheduling problem,FJSP)作為傳統作業(yè)車間調度形式之一[1-3],已被證明是強NP-hard問題。目前大多數的FJSP調度模型僅考慮到機器設備的約束,但在各類復雜人機系統中,大約有60%～90%的失效是由于人員操作失誤引起的[4]。因此,對人機雙資源柔性車間調度(Dual resource constrained flexible job shop scheduling problem,DRCFJSP)的研究具有更加重要的理論意義和實際價值。

雙資源柔性車間調度因為生產實際需求而被廣大學者研究。Cao等將遺傳算法和免疫算法相結合,使設備資源和員工資源進行了合理的分配,并達到了最大完工時間的最優(yōu)[5];Li等運用分支種群遺傳算法對雙資源約束問題進行求解,采用精英進化算子、基于扇形分割的輪盤賭選擇因子和鄰域搜索機制,達到了最大完工時間和成本最優(yōu)[6];Gong等設計一種新型混合遺傳算法,采用三層染色體編碼,完成了作業(yè)順序和工人資源合理的配置[7];在文獻[8]提出了一種混合粒子群算法,并引入可變領域結構的模擬退火來解決DRCJSP問題;文獻[9]提出了一種基于最大適應度函數的混合粒子群算法,并采取動態(tài)搜索策略來增強粒子群局部搜索能力;文獻[10]運用蟻群算法和模擬退火算法結合的混合算法,實現了分階段性能的優(yōu)化。還有一些學者運用新型的果蠅算法[11]、水滴算法[12]和鳥群算法[13]求解DRCJSP問題。

分析上述學者的研究發(fā)現:一方面,針對DRCFJSP的研究大多數是沒有考慮人員操作水平的差異性;另一方面,在算法上,大多數都是從單一種群出發(fā),優(yōu)化結果依賴初始種群。因此,本文考慮人員效率差異性,構建了人-機雙資源多目標柔性車間調度模型,并對傳統NSGA-Ⅱ加入小生境技術初始化種群策略、重復個體控制策略和熵權法選擇策略進行改進,最后,通過實驗求解和仿真對比說明了改進后的NSGA-Ⅱ對解決多目標DRCFJSP具有優(yōu)越性。

1 多目標DRCFJSP優(yōu)化建模

在一個加工系統中,有W名工人可以操控M臺機器中的一臺或者多臺來加工N個待加工的工件Ji(i∈{1,2,…,N}),每個工件Ji包含ni道工序,每道工序記為Oij。其中每道工序Oij必須在可選用的Mij={1,2,…,M}臺機器集中任選一臺進行加工,并且每臺機器M可以從可操控該機器的工人集中選一位工人進行操作。

本文的DRCFJSP調度模型用加工過程中的生產時間(T)、綠色制造評價系數(G)、生產成本(C)作為優(yōu)化目標,并對這3個目標進行了深層次的分析。

1) 最小化生產時間

在滿足員工、工藝和機器約束的前提下,最小化生產時間的數學描述如下:

minT=min(max{Ti})=

(1)

生產時間(T)屬性如表1所示。

表1 生產時間屬性表

2) 最小化綠色制造評價系數

制造企業(yè)在生產中也需要注意制造對環(huán)境造成的影響,綠色制造使減少產品在開發(fā)、引進、成長、成熟、衰退過程中對環(huán)境的影響,使得企業(yè)的經濟效益和社會效益都滿足[14]。采用能耗、噪音、切屑回收這3個因素對綠色制造效果進行評價。最小化綠色制造評價系數數學描述如下

(2)

綠色制造評價系數屬性如表2所示。

表2 綠色制造評價系數屬性表

在計算能耗、噪音和切屑回收這3個因素時,需要將數據進行無量綱處理,即

(3)

式中:x′為歸一化后的數據;x為原始數據;xmax、xmin表示x指標的最大、最小值。

3) 最小化生產成本

制造企業(yè)追求的基本目標是盈利最大化,而使生產成本最小化可以有效實現這個目標。其中生產成本包括材料成本和加工成本。加工成本又包括機器成本和人工成本。最小化生產成本數學描述如下:

minC=min(MC+PC)=min(MC+PCM+PCH)

(4)

(5)

(6)

(7)

生產成本屬性如表3所示。

表3 生產成本屬性表

在DRCFJSP問題中,除了滿足以上3個目標,還要有以下的約束條件:

1) 工藝約束

Tij-Ti(j-1)≥Pijkr×Xijkr

(8)

式中:i∈{1,2,…,N};j∈{1,2,…,ni}。式(8)確保工件加工過程中按照工序的優(yōu)先順序進行加工。

2) 機器約束

[(Top-Tij-Popk)×Yopk×Yijk≥0]∨

[(Tij-Top-Pijk)×Yijk×Yopk≥0]

i,o∈{1,2,…,N};

p∈{1,2,…,no};k∈{1,2,…,M};

該式子確保任何一臺機器在同一時刻只能加工一道工序。

3) 員工約束

(9)

式(9)確保任何一個工件的任何工序在同一時刻只能由一個工人來操作一臺機器進行加工。

2 改進NSGA-Ⅱ求解多目標DRCFJSP

由第1節(jié)的分析可以得到,本文建立的DRCFJSP模型是一個多目標優(yōu)化問題(Multi-objective optimization problem, MOP)。在MOP中,改善一個目標往往會降低另一個目標的性能,從而無法同時實現多個目標。因此,只能在多個目標中進行權衡,使所有目標盡量達到最優(yōu),得到Pareto解集[15]。其中非支配排序遺傳算法(NSGA-Ⅱ)算法在解決MOP上具有良好的表現。因此,結合DRCFJSP的特點,加入小生境協同進化策略、重復個體控制策略和熵權法選擇策略,設計了基于工序編碼的改進NSGA-Ⅱ,算法流程如圖1所示。

圖1 改進NSGA-Ⅱ算法流程圖

2.1 總體流程

改進NSGA-Ⅱ算法流程的具體操作步驟為:

步驟1 小生境協同進化策略初始化種群

1) 初始化參數,通過量子編碼和小生境劃分種群生成初始群Q(t);

2) 對種群Q(t)進行量子測量,得到二進制編碼串,隨后轉化為十進制編碼串P(t);

3) 對十進制編碼串P(t)進行解碼和個體評價,保存Pareto解集;

步驟2 循環(huán)maxGEN代,得到Pareto解集

1) 對種群P(t)進行快速非支配排序;

2) 對排序后的種群進行競標法選擇、交叉、變異,得到子種群R(t);

3) 對種群P(t)和R(t)進行合并;

4) 去除合并后的重復個體,若去除后的個體數量小于P(t)的數量,則轉到2),否則進行快速非支配排序,選擇生成新的種群,轉到1);

步驟3 熵權法確定最優(yōu)解

1) 將Pareto解集的各項指標進行歸一化;

2) 根據熵權法確定各項因素的權重;

3) 通過權重對Pareto解集的每一個解進行評價,找出最優(yōu)序列;

4) 對最優(yōu)序列進行解碼,畫出甘特圖和各項指標的迭代圖。

2.2 詳細設計

2.2.1 量子編碼

在量子編碼中,量子比特是描述量子線路狀態(tài)的最基本單元。一個量比特位可以表示為

|φ〉=α|0〉+β|1〉

(10)

柔性車間調度問題的量子編碼可以表示為

(11)

在一個DRCFSP問題中,設工件N個,機器M臺,則量子編碼長度就是L=(log2N+1)×M×N。

量子編碼為

二進制編碼為

Pt=010|011|001|011|010|001

十進制編碼為

Xt=2|3|1|3|2|1

則加工順序和加工機器可以表示為:P21,P31,P11,P32,P22,P12。

2.2.2 小生境協同進化策略

小生境技術可以很好的保持父代和子代的多樣性,還可以提高算法的運算速度和收斂性,從而找到更加適合問題的Pareto解集,所以本文對NSGA-Ⅱ算法的初始化使用小生境技術。

(12)

式中:i表示子種群的序號;N表示子種群的總數。

2.2.3 快速非支配排序

快速非支配排序可以將種群按照非劣解的程度進行分層,運用這種方法找出不被支配的解集就是所求的Pareto解集。其中,ni為支配i的個體數,si為被i支配的集合。具體操作步驟如下:

1) 找到種群中所有ni=0的個體,保存在集合Ft中,t=1;

2) 對于當前的集合Ft中每個個體i,其所支配的個體集合為si,遍歷si每個個體,執(zhí)行ni=ni-1,如果ni=0,t=t+1,并保存在集合Ft中;

3) 重復步驟2),直到整個種群被分級。

2.2.4 交叉和變異

交叉為將原有的兩條染色體的一部分進行互換,這樣就可以得到兩條不同的染色體。在2.2.1中的編碼序列表現為半Lamarckian性,通過文獻[15]表明,采用PBX和LOX交叉算子相結合的方式優(yōu)化的效果優(yōu)于單一交叉算子。因此本文在交叉過程中各按50%的概率進行隨機選擇。

變異是將染色體中間的一部分基因通過一系列操作進行改變得到新的染色體。因為本文采用的是基于工序的編碼方式,為了保證變異操作之后的染色體具有實際意義,不會出現太多的無效解集,所以采用兩段基因相互交換的方式和某段基因插入的方式相結合的作為變異操作。

2.2.5 重復個體控制策略

由于NSGA-Ⅱ算法中,新的種群是通過父代和子代合并后進行適應度計算、競標法選擇、交叉、變異確定的,而在交叉和變異不為1的時候,父代總有一些個體沒有交叉和變異,這些個體是子代的一部分。因此,在父代和子代進行合并的時候,就會有重復個體出現。隨后對新的種群進行非支配排序的時候,這些重復個體是不會互相支配的,部分重復的個體會被選入新的父代種群。這樣多代之后,新的父代被越來越多的重復解占據,導致最后的Pareto解集中的非支配解十分的少。

通過文獻[16]中提到的重復個體刪除算法,本文在NSGA-Ⅱ框架上增加重復個體控制策略改進,其具體步驟如下:

1) 對父代P(t)和子代R(t)合并后的種群S(t)進行刪除重復個體;

2) 判斷刪除后的種群個數是否小于P(t)的個數,若小于,繼續(xù)進行競標法選擇、交叉、變異,合并種群,返回1),否則,對該種群進行快速非支配排序,選出前N個個體作為新的父代種群。

2.2.6 熵權法選擇策略

在MOP問題中,最終得到的是一組Pareto最優(yōu)解集,為了避免選擇方案過程的主觀性,因此本文采用熵權法選擇最優(yōu)解策略。熵權法可以通過利用一組指標之中所含有的信息量的大小對這些指標進行賦權值,之后可以利用這些權值對這些指標進行綜合的評價,得到Pareto解集中綜合評價最好的解[17]。具體步驟如下:

5) 利用加權求和對解集中的每個解進行評價。

3 實例分析

為了說明改進算法的有效性,以某企業(yè)實例為基準進行數據驗證,并與改進前的NSGA-Ⅱ算法進行求解對比。該車間要在6臺設備(M1～M6)上安排6種工件(J1～J6)的生產,車間工人有6名(W1～W6)。其中,每個工件的每道工序是否可以在機器上加工及加工標準時間如表4所示,工人是否可以操作機器及操控效率如表5所示,工人單位時間成本及機器設備單位成本如表6,表7所示。能耗、噪音、切屑回收這3個數據通過文獻[18]的Algorithm3.2在一定范圍內生成。

表4 工序標準時間表

表5 工人可操控機器及操控效率

表6 工人單位時間成本

表7 機器單位時間成本

NSGA-Ⅱ與改進NSGA-Ⅱ參數設置如下:種群規(guī)模為200,迭代次數為200,交叉率為0.9,變異率為0.1。

圖2表示通過NSGA-Ⅱ和改進NSGA-Ⅱ進行多目標雙資源柔性車間調度求解仿真得到的Pareto前沿,圖3表示通過Pareto前沿點集進行擬合得到的Pareto前沿面。對比可知改進后的NSGA-Ⅱ算法相比于NSGA-Ⅱ算法總體上解的個數更多,且生產時間,綠色制造評價系數和生產成本都更加優(yōu)化。證明了改進NSGA-Ⅱ算法的有效性和可行性。

圖2 Pareto前沿圖

圖3 擬合Pareto前沿面

圖4～圖6分別表示生產時間、綠色制造評價系數和生產成本的迭代過程。表8為改進NSGA-Ⅱ求解后得到的Pareto解集,一共包含31組解。

圖4 生產時間迭代圖

圖5 綠色制造評價系數迭代圖

圖6 生產成本迭代圖

表8 最終的得到的31組解集

算法最后通過熵權法選擇策略選出一組最優(yōu)解,生產時間T=24.56,綠色制造評價系數G=15.79,生產成本C=7 660.75。對應甘特圖如圖7所示,其中P(i,j)=h表示第i個工件的第j道工序的實際生產時間,h;下方對應的R=w表示該工序是由工人w進行加工操作。

圖7 最優(yōu)解的調度甘特圖

4 結論

考慮車間中員工操控機床加工工件熟練度不同的情況下,以生產時間最小化,生產成本最小化和綠色制造評價系數最小化為目標,建立了考慮人員的多目標DRCFJSP模型,并引入改進NSGA-Ⅱ算法來求解該問題。針對傳統量子遺傳算法的收斂速度慢,容易陷入早熟而且容易多個重復解的問題,采用了小生境初始化種群、充分個體控制策略和熵權法選擇最優(yōu)解來提升算法效率,避免算法早熟收斂和重復無效解集。最后通過實例分析,并與改進前的NSGA-Ⅱ進行對比,證明本文改進的NSGA-Ⅱ具有很好的收斂性和不會陷入早熟的能力。下一步將對算法進一步改進,對動態(tài)DRCFJSP多目標問題進行研究。