武治含 劉國華 盛守祥 王國棟 王力民

摘 要：部門間協(xié)同化程度低是制約印染企業(yè)生產效率提高的因素，為了解決該問題，本文提出了一種印染協(xié)同管理調度方法。通過對印染生產業(yè)務流程的分析，確定協(xié)同管理調度問題的數(shù)學模型，并利用遺傳算法求得問題的近似最優(yōu)解。在本文的遺傳算法中，個體采用基于序列的編碼方式，交叉操作采用互換交叉的方式，變異操作采用逆轉變異方式。實驗結果表明，本文提出的方法可以有效地提高資源利用率，縮短訂單完工時間。

關鍵詞： 印染生產;協(xié)同管理調度;遺傳算法

文章編號： 2095-2163（2019）03-0142-04 中圖分類號： TP311.5 文獻標志碼： A

0 引 言

中國紡織、輕工業(yè)等行業(yè)的信息化程度較低[1-2]，導致部門間協(xié)同信息匱乏。印染業(yè)作為紡織業(yè)的重要分支之一，面對競爭白熱化帶來的新變局，迫切需要尋求技術上的突破，提高協(xié)同管理水平，從而提升產業(yè)競爭力。

目前印染企業(yè)部門間的協(xié)同化程度低，任務順序均由部門主管統(tǒng)籌安排或線性執(zhí)行。這種生產模式導致各部門的信息時效性差，異步協(xié)同工作難以充分展開，資源的最優(yōu)利用也仍停留在理論上。長此以往，必將導致人力物力資源的極大浪費、生產效率低下，同時產業(yè)競爭力也不高。

針對人為協(xié)同管理調度資源利用率低的問題，Steenhuisen等人[3]于2009年提出了協(xié)同調度的概念，所謂的協(xié)同調度，即當一個復雜的任務須經由多個部門的協(xié)同運作時，亟需制定一個切實可行的計劃，使得每個部門協(xié)同有效地完成子任務，從而保證總任務順利交付。在國內很多領域，也已經陸續(xù)見到相關的問題研究，例如，馮霞等人[4]研發(fā)了基于多目標遺傳算法的模型用于求解機場運輸工作的協(xié)同調度問題;陳鵬慧等人[5]提出了一種基于遺傳算法的協(xié)同調度方法，用于解決機器人的協(xié)同調度問題。而在印染業(yè)，研究者的關注重心多是聚焦在生產車間調度[6-7]方面。在印染生產的業(yè)務協(xié)同管理方面的研究迄今為止仍不多見。研究可知，協(xié)同管理調度屬于常見的組合優(yōu)化問題，近年來國內外學者就求解該問題進行了大量的實驗。目前比較通用的方法有模擬退火法[8]、遺傳算法[9-10]、粒子群算法[11]、蟻群算法、人工神經網絡等。其中，遺傳算法作為時下解決調度問題效率較高、通用性較好的一種啟發(fā)式算法，具有求解過程簡潔，收斂性好，近優(yōu)解質量高的特點[12]。綜上論述可知，本文在對印染生產協(xié)同管理問題研究的基礎上，利用遺傳算法，提出了印染協(xié)同管理調度方法。本文對此擬做研究論述如下。

1 問題描述與建模

印染企業(yè)的印染業(yè)務流程描述如下：業(yè)務員接收訂單后，根據生產需求創(chuàng)建訂單，訂單審核通過后，將依次經歷原料采購、打樣生產、質檢以及運輸?shù)拳h(huán)節(jié)，以上步驟將整個流程拆分成多個業(yè)務。本文將通過調度算法研究來使各部門協(xié)同處理多個訂單的作業(yè)時間最短。

1.1 問題描述

已知一個生產訂單集合O={Oi|i=1，2，...，n}，一個業(yè)務集合P={Pj|j=1，2，...，m}，對于O中的任意一個元素Oi，均要經過k（k≤m）個有序的業(yè)務處理，且各生產訂單對應的業(yè)務運行時間為已知。求業(yè)務部門處理訂單的順序，確保在規(guī)定時間內近似最優(yōu)、資源利用率最高地完成全部訂單。

生產訂單與業(yè)務約束關系及對應業(yè)務的處理時間見表1。例如，O1訂單的對應的業(yè)務序列為P1-P2-P4-P6。

1.2 問題建模

本文數(shù)學模型遵循的約束條件的釋義說明可分述如下：

（1） 業(yè)務部門同一時刻只能處理某個訂單中的相應業(yè)務。

（2）各訂單對應的訂單業(yè)務有嚴格的執(zhí)行順序，且各訂單之間邏輯獨立，互不影響。

（3）業(yè)務必須由特定的業(yè)務部門來完成，并且前一項業(yè)務完成后才能處理后續(xù)業(yè)務。

（4）業(yè)務處理時間已知，不隨業(yè)務處理順序或訂單執(zhí)行順序的改變而改變。

（5）業(yè)務執(zhí)行期間，直到結束不會進行其他任務。

結合約束條件，根據表1中的數(shù)據形式，對本文研究的協(xié)同管理調度問題進行數(shù)學建模，對此可表述為：

研究中，設n表示訂單數(shù)，m表示全部訂單對應業(yè)務數(shù)中的最大值，數(shù)組orderProject[n][m]表示n個訂單分別對應的業(yè)務序列，即，訂單業(yè)務約束關系數(shù)組;數(shù)組projectTime[n][m]表示n個訂單業(yè)務序列分別對應的業(yè)務執(zhí)行時間;P[m][n]表示m個業(yè)務部門對應的訂單處理順序;T[n][m]表示n個訂單業(yè)務序列中各個業(yè)務的開始運行時間。

對于n個訂單，每個訂單最多涉及m個業(yè)務的協(xié)同管理調度問題，令TMax表示完成所有訂單所需的最大完工時間，則求取TMax最小的目標函數(shù)可寫作如下數(shù)學形式：

其中，M為種群個體數(shù)，Ti表示訂單在某一種處理順序下，全部訂單的最大完成時間，即：

2 基于遺傳算法的求解方法

遺傳算法在研究染色體編碼方式時，需要考慮最突出的個體特征，從而確定編碼方式。個體的編碼方式，將直接影響算法后續(xù)步驟以及算法性能。而在得到編碼方式后，則根據個體特點進一步確定適應度函數(shù)、選擇方法、交叉與變異方式，以及初始種群大小、交叉變異概率、迭代次數(shù)等。本文對此將給出探討詳述如下。

2.1 編碼

本文的研究目標是獲取訂單的最優(yōu)處理順序?；诖?，本文采用基于序列的編碼方式[13]對個體進行編碼。染色體的基因數(shù)為所有訂單全部業(yè)務數(shù)之和，用訂單序號表示對應訂單。染色體序列由訂單序號組成，且同一訂單序號的出現(xiàn)次數(shù)為該訂單對應的業(yè)務數(shù)。

采用基于序列的編碼方式對表1中的數(shù)據進行編碼，編碼后的一條染色體為：[2 2 1 2 1 2 1 1 2]。其中，序號2出現(xiàn)了5次，表示訂單O2對應著5個業(yè)務。

2.2 解碼

由于訂單業(yè)務有著嚴格的執(zhí)行順序，訂單序號第幾次出現(xiàn)即表征該訂單的第幾個業(yè)務。結合表1數(shù)據可知，染色體序列[2 2 1 2 1 2 1 1 2]中第一個基因2表示訂單O2的首道工序P5，同理，序列中第五個基因1則表示訂單O1中的第二道工序P2。

故而，由染色體序列結合數(shù)組orderProject[n][m]便可判斷出當前處于幾號訂單的幾號業(yè)務。

2.3 適應度值計算

適應度值的大小關系到個體的優(yōu)劣判斷。本文的適應度值為完成全部訂單所需最大時間的倒數(shù)，即1/Ti（i=1，2，...，M）。最大完工時間越短，適應度值越高，個體的生存幾率就越大。

訂單業(yè)務根據染色體序列從左到右依次開始執(zhí)行，結合數(shù)組orderProject[n][m]以及projectTime[n][m]可知，當前訂單業(yè)務是幾號訂單的幾號業(yè)務，并且該業(yè)務的執(zhí)行時間亦已知。選取該業(yè)務之前一個業(yè)務的完成時間或者處理該業(yè)務的業(yè)務部門的最近空閑時間這二者中的較大值，作為該業(yè)務的開始時間。綜上方法就可求得每個業(yè)務的開始工作時間與完工時間。不斷更新Ti，使Ti為目前所需的最大完工時間。直到全部訂單被處理完畢，求得的1/Ti即為該個體的適應度值，記為fi （i=1，2，...，M）。

2.4 選擇

選擇的設計是基于優(yōu)勝劣汰的原則，從當前的種群中選出優(yōu)異的染色體作為交叉變異執(zhí)行的個體。本文采用輪盤賭選擇法結合精英策略進行個體選擇。

計算種群個體的適應度值之和∑fi （i=1，2，...，M）。研究推得個體選擇概率的計算公式為：

由式（3），可得個體的選擇概率為個體適應度值除以種群內全部染色體適應度之和。

接下來，計算∑pi，并且在[0，1]區(qū)間內產生隨機數(shù)r，如果r∈（∑pi-1，∑pi]，則個體vi被選中。

將選中的個體作為交叉操作與變異操作的候選個體。

2.5 交叉

本文采用基于序列的編碼方式，個體序列順序的交換并不影響訂單業(yè)務的執(zhí)行順序，故本文采用互換基因的方式[14]進行交叉操作（交叉概率Pc=0.9）。記染色體長度為L?；Q交叉操作如圖1所示。具體步驟如下。

（1）產生一個在[1，L]之間的隨機數(shù)r1。

（2）記錄C1、C2染色體中r1位置的基因值分別為c1、c2。

（3）互換C1、C2中r1位置的基因值。

（4）在C2中找到c1第一次出現(xiàn)的位置，記為g2，在C1中找到c2第一次出現(xiàn)的位置，記為g1。

（5）互換g1、g2位置的基因值。

（6）返回新的染色體C1'、C2'。

當r1的值為2時，交叉后的染色體如圖2所示。

由于交叉后的個體只改變了訂單開始時間，訂單間業(yè)務邏輯互不影響。故而求得的解仍為可行解。

2.6 變異

為了防止種群陷入局部最優(yōu)解，保護優(yōu)良基因，本文采用了逆轉變異的方法（變異概率Pm=0.05）進行染色體變異。具體過程如下。

在[1，L]之間產生2個隨機數(shù)l1、l2，且要求這2個隨機數(shù)不等。交換這2個位置上的基因，生成新的個體。例如基因數(shù)為6的個體，取2個隨機數(shù)l1、l2分別為2與4，互換第二位與第四位的基因，形成新個體。設計變換過程如圖3所示。

由于個體序列順序的交換并不影響訂單業(yè)務的執(zhí)行順序，故由此變異方法得到的變異個體仍是可行解。

2.7 終止條件

若遺傳算法代碼運行時間超過設定時間或迭代次數(shù)達到給定次數(shù)，則停止運行，得到的結果則為協(xié)同管理調度問題的近似最優(yōu)解。

3 實驗結果

結合某印染車間的實際業(yè)務流程進行試驗。已知有標號分別為O1～O5的5個訂單，其中包括的項目業(yè)務如下：原料采購、原料質檢、打樣、制定生產工藝、訂單生產、成品質檢、成品入庫與運輸，分別記為1、2、3、4、5、6、7、8。訂單與業(yè)務對應的約束關系orderProject[5][8]見表2，對應的業(yè)務執(zhí)行時間數(shù)據projectTime[5][8]見表3。

利用上述實驗數(shù)據運行算法，計算得出訂單最短完成時間（49 h）、各業(yè)務開始時間數(shù)組T[5][8]。本文遺傳算法的運行參數(shù)為：初始種群大小100，Pc為0.9，Pm為0.05，迭代次數(shù)為1 000。協(xié)同管理調度結果如圖4所示。在圖4中，定義了O（i）： t的模式，其中i表示訂單號，t表示業(yè)務開始時間。

根據實驗結果甘特圖可得，訂單處理順序明確，任務分工合理。算法調度管理下的業(yè)務時間節(jié)點清晰，部門工作效率與資源利用率得到有效提高。當訂單量大時，協(xié)同管理調度算法的優(yōu)勢就更加明顯。在生產實踐中，企業(yè)可將算法結果與工作日程結合，得出各部門的任務時間安排表，提高部門執(zhí)行力與各部門間的溝通時效性。

4 結束語

面對日趨激烈的競爭環(huán)境，紡織印染行業(yè)必須緊跟時代潮流，提升產業(yè)信息化水平。本文提出的基于遺傳算法的印染協(xié)同管理調度方案契合實際生產需求，對提高業(yè)務協(xié)同運作效率以及提升產業(yè)競爭力起到了積極重要的推動作用。隨著研究的深入，用于解決部門協(xié)同合作的算法將會具有更加廣闊的應用前景，算法的求解速度和近似最優(yōu)解的質量也將得到不斷地提升與完善。

參考文獻

[1]賀正楚，潘紅玉. 德國“工業(yè)4.0”與“中國制造2025”[J]. 長沙理工大學學報（社會科學版），2015，30（3）：103-110.

[2]李瑞萍. 中國印染行業(yè)發(fā)展現(xiàn)狀及未來趨勢[J]. 染料與染色，2015，52（2）：52-62.

[3]STEENHUISEN J R， WITTEVEEN C. Plan decoupling of agents with qualitatively constrained tasks[J]. Multiagent and Grid Systems， 2009， 5（4）： 357-371.

[4]馮霞，任子云. 基于遺傳算法的加油車和擺渡車協(xié)同調度研究[J]. 交通運輸系統(tǒng)工程與信息，2016，16（2）：155-163.

[5]陳鵬慧，蔡瓊，彭華順. 基于遺傳算法的多移動機器人協(xié)同調度方案[J]. 微型電腦應用，2016，32（7）：34-38.

[6]張洪業(yè)，金剛，王宇新. 微粒群算法在印染企業(yè)車間調度中的研究應用[J]. 計算機工程與應用，2009，45（21）：245-248.

[7]張國輝. 柔性作業(yè)車間調度方法研究[D]. 武漢：華中科技大學，2009.

[8]LI W? D，MCMAHON C A.? A simulated annealing-based optimization approach for integrated process planning and scheduling[J]. International Journal of Computer Integrated Manufacturing，2007，20（1）：80-95.

[9]席裕庚，柴天佑，惲為民. 遺傳算法綜述[J]. 控制理論與應用，1996，13（6）：697-708.

[10]PANDEY H M， CHAUDHARY? A， MEHROTRA D. A comparative review of approaches to prevent premature convergence in GA[J]. Applied Soft Computing Journal， 2014（24）：1047-1077.

[11]王萬良，趙澄，熊婧，等. 基于改進蟻群算法的柔性作業(yè)車間調度問題的求解方法[J]. 系統(tǒng)仿真學報，2008，20（16）：4326-4329.

[12]馬永杰，云文霞. 遺傳算法研究進展[J]. 計算機應用研究，2012，29（4）：1201-1206，1210.

[13]姜迪剛，葉尚輝. 基于遺傳算法的車間作業(yè)調度[J]. 西安電子科技大學學報，2001，28（2）：207-210.

[14]曾強，鄧敬源，張進春，等. 多工作日歷下流水作業(yè)調度遺傳優(yōu)化方法[J]. 計算機工程與應用，2019，55（4）：238-247.