緯編織造車間生產調度方法研究

周亞勤， 王 攀， 張 朋， 張 潔

(東華大學 機械工程學院， 上海 201620)

緯編織造車間生產具有以下特點:針織緯編面料種類繁多，工藝多樣；面向訂單生產，客戶訂單數量大小不一，交貨期十分嚴格；設備加工工藝柔性，織造車間有多類型緯編機，同類型設備具有多臺，可加工一定工藝范圍內的多種產品類型，且加工不同產品時，設備的產能不同；織造設備在加工不同產品類型時，需更換設備機架和針筒，改機時間長。綜合以上分析，可將織造車間生產調度問題抽象成面向訂單生產的考慮設備產能和改機時間的非等同并行機調度問題。研究這類生產調度模型和方法具有一定的理論意義和工程應用價值，優化的織造車間生產調度方案可大大減少設備改機時間，提高生產效率，保證產品交貨期。

在非等同并行機調度問題上，國內外學者進行了大量的探索與研究，并取得了許多成果。Maria等[1]考慮設備的準備時間、容量約束以及作業分批屬性等，構建了非等同并行機調度模型，并設計了融入啟發式規則的粒子群算法進行求解。Jose等[2]考慮設備容量以及訂單交貨期等約束，建立了具有準備時間的批處理機調度模型，結合具有最佳擬合的啟發式算法，取得了很好的優化效果。Suhaimi等[3]以最小化加權時間為優化目標，考慮設備的輔助加工時間約束，采用拉格朗日松弛算法進行研究。趙晴瑤[4]建立了帶準備時間序列的不相關并行機調度模型，并基于改進果蠅優化算法對該問題進行求解。周亞勤等[5]綜合考慮批量和輔助時間等實際生產工況，提出一種生物免疫算法對該調度模型進行了優化求解。

盡管調度問題在不同領域取得了不錯的進展，但在針織領域織造車間的研究較少。王靜安等[6]對以往織造車間生產模型進行改進，提出了一種更加實用的織造車間織機調度優化模型，并采用遺傳算法進行求解，但并未考慮設備加工特性約束。孫延[7]構建了織造排產與調度的數學模型，并將所提出的蟻群算法應用于紡織企業織造車間，但未結合具體生產實例進行仿真分析。孟朔等[8]構建了以滿足訂單交貨期為主優化目標、最小化訂單產品翻改等為次優化目標的織機調度模型，并結合改進的非支配遺傳算法求解該調度問題。Yilmaz等[9]考慮了依賴于序列相關的設置時間、作業分批屬性以及機器加工特性等約束，構建了單一優化目標的大規模織機調度模型，并將其所提出的改進遺傳算法應用于該調度問題中，得到了較好的優化結果。

本文結合緯編織造車間生產實際需求，綜合考慮訂單可拆分特性、產品特定加工設備組、設備不同產品間改機時間等約束，構建織造車間生產調度優化模型，設計基于改進遺傳算法的織造車間生產調度方法，實現考慮產品加工時間富裕度的訂單拆分，考慮工藝相似性的產品加工設備選擇和設備加工任務優化排序，使得織造車間加工任務的總完工時間最短和總拖期時間最小。

1 織造車間生產調度模型的建立

1.1 問題描述

緯編織造車間在某個調度周期內，共接收到客戶確認過的訂單k個，每個訂單中均包含多種產品，且每種產品的數量大小以及交貨期存在著差異?，F車間共配備有m臺生產設備，每個訂單產品均可在1臺或多臺設備上進行生產，生產時間會隨著所選設備而變化。同時，設備前后生產不同面料類型的訂單任務時，需要一定的改機時間，因此，織造車間的調度問題在于如何將不同的客戶產品合理地安排在設備上進行生產，并使產品總完工時間和拖期時間最小等性能指標達到最優。

1.2 模型假設

織造車間生產調度模型需要滿足如下基本假設。

1)調度開始(0時刻),所有機器都處于可用狀態，所有訂單任務均處于可加工狀態。

2)紗線原料充足且滿足訂單產品的生產需求。

3)不考慮設備的故障以及動態插單、取消訂單等擾動問題。

4)設備可生產的產品種類以及其對應的產能均已知。

5)不考慮產品的庫存以及運輸成本等。

6)經訂單預處理后的訂單任務均只包含1種產品，且同一設備在同一時間僅能生產1個訂單任務。

7)某一訂單任務只要開始加工就不允許停止，直到該任務完成加工為止。

8)車間的其他與生產相關的信息均已知。

1.3 目標函數與約束條件

結合實際生產情況，織造車間生產調度模型需綜合考慮訂單可拆分特性、產品特定加工設備組、設備不同產品間改機時間、設備產能、交貨期等約束，以產品完工總時間和總拖期時間最小為目標，以實現產品按期交貨。

1.3.1 優化目標

織造車間生產調度以產品完工總時間最小和拖期時間最小為目標，建立優化目標函數如式(1)和式(2)所示。

(1)

(2)

式中：f1表示最小化最大完工時間;PTj表示設備j上的總加工時間;GTj表示設備j上的改機總時間;f2表示最小化總拖期時間;βi為客戶重要度系數，其取值范圍為[1,10]；ETij表示第i個訂單任務在第j臺設備上的加工結束時間；Di為第i個訂單任務的交貨期時間；Xij為決策變量，當訂單任務i在設備j上生產時，則Xij=1,否則Xij=0。

1.3.2 約束條件

織造車間生產調度模型滿足如下約束條件。

1) 交貨期約束為

ETij≤Di

(3)

(4)

式中：Ue表示產品e的交貨期松弛度；De表示產品e的交貨期；Temax表示產品e在可加工設備集合Ωe上所需生產時間的最大值。

2)訂單拆分數量約束為

(5)

式中：δe表示產品e的拆分數量；Qe表示產品e的數量；Ceavg表示可加工產品e的設備集合平均日產能；T表示計劃周期時間；[]表示取整,且k≥1(取整數)。

3) 加工唯一性約束為

(6)

4)加工時間約束為

ST(i+1)j-STij≥PTij

(7)

ETij+GTjii′Yjii′=STi′j

(8)

式中：STij表示第i個訂單任務在第j臺設備上的加工開始時間；PTij表示第i個訂單任務在第j臺設備上的加工時間；GTjii′表示設備j先后加工訂單任務i與訂單任務i′時所需的改機時間；Yjii′為決策變量，當第j臺設備前后分配的訂單任務的面料類型不同時,Yjii′=1，否則Yjii′=0。

5) 改機約束為

GTjii′=GTjii′Yjii′

(9)

6) 設備產能約束為

(10)

式中：Qi表示第i個訂單任務數量；Qij表示第i個訂單任務在第j臺設備上加工時，設備所對應的產能。

2 模型的求解

2.1 訂單拆分

由于緯編生產企業接收到的訂單具有產品種類繁多、生產工藝復雜、多客戶以及交貨期嚴格等特點，不合理的調度方案易導致車間訂單的堆積以及設備改機次數的增多，嚴重時甚至造成訂單拖期?？紤]到車間設備產能的限制，車間生產要素分配不均易造成設備產能的浪費以及降低車間生產效率，針對不同客戶重要度的差異，針織企業會優先安排重要度高的客戶的產品進行生產。同時為最大限度地保證完成該計劃周期內的所有訂單，企業計劃人員會對重要客戶交貨期緊張的訂單進行拆分處理，從而保證產品交貨期內的加工時間富裕度，具體的預處理操作過程如下。

第1步:將該計劃周期內不同客戶的訂單組成訂單產品集合N1。

第2步:將N1中產品按客戶重要程度以及交貨期進行排序，并按照式(4)對每個產品的交貨期松弛度進行計算。

第3步:對于交貨期松馳度小于0且客戶等級大于8的產品，按照式(5)進行等量拆分，并優先安排生產。

第4步:將經過預處理操作后的訂單產品建立訂單任務序列，用于織造車間生產調度。

2.2 訂單任務設備選擇

設備選擇是指為經過訂單拆分后的訂單任務選擇合適的加工設備的過程。本文基于產品加工工藝的相似性，設計啟發式規則為每個訂單任務進行設備選擇，從而使設備的利用率均衡以及減少訂單的拖期時間，其主要規則如下。

規則1:訂單任務選擇可加工設備集合中分配有相同面料類型訂單任務的設備集合，并在該設備集合中選擇該訂單任務加入時交貨期松弛度最大的設備。如果該訂單任務分配到的設備集合上的交貨期松弛度均小于0，則轉到規則2。

規則2:訂單任務在可加工設備集合中選擇該訂單任務加入時所造成拖期時間最短的設備進行加工。

2.3 訂單任務優化排序

遺傳算法是基于染色體群的具有并行搜索能力的算法，已廣泛應用于織造車間的生產調度中[6,8-9]，本文將采用遺傳算法進行設備上訂單任務排序的優化求解，并針對傳統遺傳算法局部搜索能力弱以及收斂速度慢等缺陷，提出改進遺傳算法對訂單優化排序問題進行求解，得到更加優化的排序結果。改進遺傳算法的流程圖如圖1所示。

圖1 改進遺傳算法流程圖

1)編碼。本文對訂單任務及設備采取雙層實數編碼形式，上層為訂單任務編碼，是訂單拆分后形成的所有訂單任務的排列；下層為設備編碼，根據訂單任務設備選擇規則，為上層的各訂單任務選擇設備，或者在訂單任務可加工設備中任選一臺設備，形成第2層設備編碼，同設備上任務的加工順序遵循第1層的排列順序。例如，上層訂單任務編碼為164872935，下層設備編碼為143322114，則設備1上的訂單任務加工順序為1，9，3。

2)種群初始化。采用2.2節啟發式規則與隨機生成相結合的方式產生初始種群，且2種方法產生初始解的比例均設置為50%。

3)適應度函數?？紤]到2個優化目標時間量綱的不一致性，故將2個優化目標函數進行歸一化處理，然后對2個目標函數求和后取倒數作為適應度函數。定義的適應度函數為

(11)

式中：f表示適應度函數；w1、w2分別為完工時間和延期時間的加權系數值；af1表示所有個體最大完工時間之和的均值；af2表示所有個體拖期時間之和的均值。

4)交叉變異?？紤]到設備生產柔性，即不同訂單任務可在多臺設備上加工生產的特點，本文采用2點交叉[10]以及單點變異[11]的方式，通過隨機選擇2個交叉點交換交叉區間的基因片段以生成子代，然后在子代中隨機選擇一個變異點，針對設備層進行單點變異。

5)局部搜索策略。為提高遺傳算法的局部搜索能力，本文采取以下3種鄰域結構操作方法在當前最優染色體上進行局部搜索，以尋找更優個體。插入操作：首先在最優解染色體上隨機選取2個基因位置R1與R2(R1

6)算法關鍵參數的選取。由于遺傳算子中交叉概率Pc和變異概率Pm對算法的運行效率影響較大，若采用固定的交叉概率和變異概率則易使算法陷入局部最優，為加快算法的收斂速度以及避免算法陷入局部最優，本文采用改進的自適應交叉概率以及變異概率。自適應交叉概率與自適應變異概率的設置如下式所示。

(12)

式中：Pc_max、Pc_mid、Pc_min分別表示最大、中等以及最小的交叉概率;fmax、favg、fmin分別表示當前種群中所有個體的最高適應度值、平均適應度值以及最低適應度值;fc表示進入交配池中的2個個體中適應度值較大的個體。

(13)

式中：Pm_max、Pm_mid、Pm_min分別表示最大、中等以及最小的變異概率;fm表示要進行變異操作個體的適應度值。

3 實驗驗證

3.1 案例背景

以上海某針織企業緯編生產車間的實際生產情況為背景進行案例測試，其中車間設備信息如表1所示，訂單信息如表2所示。

表1 車間設備信息(節選)

表2 車間訂單信息(節選)

3.2 仿真結果對比及分析

本文改進遺傳算法的求解方法采用C#語言編程實現，程序運行環境為visual studio 2013，CPU為AMD Ryzen5 PRO 2 500 U @2 GHz，內存為8 GB，Windows 10操作系統。取該求解方法的初始種群規模為80，算法的交叉概率Pc_max=0.9，Pc_mid=0.65，Pc_min=0.35；變異概率Pm_max=0.1，Pm_mid=0.05，Pm_min=0.01，最大迭代次數取150，變鄰域搜索次數取80，閾值θ取8。

1)訂單拆分結果分析。訂單拆分數量的大小對本文提出的算法搜索效率影響較大，過大或過小都不利于算法搜索效率的提高。為確定不同訂單合理的拆分數量，分別取式(5)中k的大小為{1，2，3，4，5，6}，算法運行20次得到的目標函數值和設備的平均改機次數(同一設備在生產不同類型的產品時，需要進行的機器調整次數)如表3所示?？芍?，當k取3時，目標函數值最優，且設備的改機次數較少，綜合考慮目標函數值和設備改機次數，選取k值為3。

表3 不同k值對優化結果的影響

2)初始解對比實驗。本節以經過訂單預處理操作后形成的40個訂單任務為實際案例，進行25次迭代實驗，對比隨機規則、文獻[12]的啟發式規則以及本文提出的車間啟發式規則，產生初始解的質量如圖2所示?？梢缘贸?，本文提出的車間啟發式規則,在迭代過程中所產生的初始解平均值的質量明顯優于其他2種方法，該方法不僅保證了種群的多樣性(隨機規則)，且改善了初始解的質量(車間啟發式規則)。

圖2 初始解結果對比圖

3)算法收斂性分析。圖3示出改進遺傳算法在求解這40個訂單任務案例時的收斂曲線。由圖可知，算法具有快速收斂的特性，且在進化初期適應度值迅速增加，最后算法大概在迭代次數為55時趨于穩定，并收斂至一穩定的最優值。圖4示出算法部分調度結果甘特圖?？芍?，最大完工時間為26 d左右，且僅有2個訂單任務拖期，拖期僅為1 d，同時是不重要客戶的訂單任務，而企業以前采用Excel表格進行訂單任務機臺預排時，訂單任務的總完工時間平均為32 d左右，采用本文算法生產效率可提高18%，由此可以驗證本文所提算法對于求解該調度問題的有效性。

圖3 種群迭代變化圖

圖4 部分調度結果甘特圖

為對本文所提出的改進遺傳算法性能進行測試，利用不同規模下的算例進行仿真實驗。算例由設備類型、設備數量以及訂單任務數量3部分組成，如：4*5*20表示4種不同類型的設備，5臺設備以及20個訂單任務，并以訂單任務數為20、30,以及設備數為4、5、6組成正交試驗,生成了6組不同的算例，然后分別采用遺傳算法(GA)、自適應遺傳算法(SAGA)、變鄰域遺傳算法(VGA)以及改進的遺傳算法(IGA)對算例進行求解。其中，GA未加入任何改進策略，SAGA去掉了變鄰域搜索策略，VGA則采用固定的交叉及變異概率。

考慮到不同算法的隨機性，對算例分別運行15次，得到目標函數值的最優適應度值解(best)、平均適應度值解(avg)以及算法的平均收斂代數，求解結果如表4所示。由對比結果分析可得，SAGA相較于GA在最優值尋優方面提升不大，但SAGA求解的平均適應度值較GA有較大的提升，最大提升程度為10.07%，表明SAGA算法求解結果更具穩定性。同時VGA算法相較于GA算法在最優值以及平均值方面均有很大提升，這表明VGA算法具有很好的局部尋優能力。IGA算法求解的最優適應度值以及平均適應度值均優于其他3種算法，在最優適應度值方面分別平均提升40.4%、37.7%、4.1%，在平均適應度值方面分別平均提升65.5%、50.5%、4.5%。從求解穩定性方面來看，本文提出的IGA算法求解質量不會隨著案例規模的變化而有較大的波動性，這表明IGA算法在求解織造車間調度問題上具有很好的穩定性。從算法收斂性的角度來看，本文提出的IGA算法相比于其他3種算法平均早25代左右收斂至最優值，由此可以得出在相同迭代次數的前提下，IGA算法具有更好的優化能力以及收斂能力，同時驗證了本文所提改進策略的有效性。

表4 不同算法仿真結果對比

4 結 論

本文圍繞針織企業織造車間調度問題展開研究，構建了考慮訂單拆分特性的織造車間多目標調度優化模型，提出“訂單拆分-設備選擇-任務排序”的織造車間調度方法，并通過企業的實際生產案例進行案例仿真，通過訂單拆分結果分析、種群初始解對比實驗和算法與其他算法進行比較，得出本文提出的訂單拆分規則和任務設備選擇規則可以改善算法初始解的質量，提出的改進遺傳算法具有很好的收斂性。結果表明，本文提出的方法相較于人工排產具有較大的優越性，且改進遺傳算法在性能上優于其他算法，能有效指導織造車間生產排程。

考慮到企業車間在實際生產過程中的不穩定性，緊急插單、設備故障以及原材料延期等擾動事件的發生使車間生產變得更為復雜，如何進一步完善模型，以及考慮各種擾動事件發生下對織造車間動態調度問題的研究是下一步重要的研究方向。