基于遺傳算法的印染協(xié)同管理調(diào)度問題研究

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

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

關(guān)鍵詞： 印染生產(chǎn);協(xié)同管理調(diào)度;遺傳算法

文章編號： 2095-2163（2019）03-0142-04 中圖分類號： TP311.5 文獻(xiàn)標(biāo)志碼： A

0 引 言

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

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

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

1 問題描述與建模

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

1.1 問題描述

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

生產(chǎn)訂單與業(yè)務(wù)約束關(guān)系及對應(yīng)業(yè)務(wù)的處理時(shí)間見表1。例如，O1訂單的對應(yīng)的業(yè)務(wù)序列為P1-P2-P4-P6。

1.2 問題建模

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

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

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

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

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

（5）業(yè)務(wù)執(zhí)行期間，直到結(jié)束不會進(jìn)行其他任務(wù)。

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

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

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

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

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

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

2.1 編碼

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

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

2.2 解碼

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

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

2.3 適應(yīng)度值計(jì)算

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

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

2.4 選擇

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

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

由式（3），可得個(gè)體的選擇概率為個(gè)體適應(yīng)度值除以種群內(nèi)全部染色體適應(yīng)度之和。

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

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

2.5 交叉

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

（1）產(chǎn)生一個(gè)在[1，L]之間的隨機(jī)數(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'。

當(dāng)r1的值為2時(shí)，交叉后的染色體如圖2所示。

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

2.6 變異

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

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

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

2.7 終止條件

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)

[1]賀正楚，潘紅玉. 德國“工業(yè)4.0”與“中國制造2025”[J]. 長沙理工大學(xué)學(xué)報(bào)（社會科學(xué)版），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é)同調(diào)度研究[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2016，16（2）：155-163.

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

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

[7]張國輝. 柔性作業(yè)車間調(diào)度方法研究[D]. 武漢：華中科技大學(xué)，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]. 控制理論與應(yīng)用，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]王萬良，趙澄，熊婧，等. 基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問題的求解方法[J]. 系統(tǒng)仿真學(xué)報(bào)，2008，20（16）：4326-4329.

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

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

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