基于遺傳算法的染整車間自動排產問題研究

倪夢妃 劉國華

文章編號： 2095-2163（2018）03-0041-05中圖分類號： 文獻標志碼： A

摘要： 關鍵詞： dyeing and finishing workshops based on genetic algorithm

（School of Computer Science and Technology， Donghua University， Shanghai 201620， China）

Abstract： The advanced planning and scheduling problem， referred to as APS， is a typical NP-hard problem. In the dyeing and finishing industry， some research results have been made on the production of the dye VAT， but no fruit has been reported on the automatic production of the workshop. In order to solve production scheduling problem of the dyeing workshop， this paper first analyzes and describes the problems， then establishes a mathematical model，meanwhile combined with genetic algorithm， the solution method is proposed. This method could obtain a relatively optimal solution， and conduct the experiment through actual production scheduling task to verify the efficiency of the method. The experimental results show that compared with the artificial production scheduling， scheduling efficiency of using the algorithm has been greatly improved.

Key words：

基金項目：

作者簡介：

收稿日期： 引言

隨著現代信息技術的不斷發(fā)展，各行各業(yè)都在引進電子信息化來提高行業(yè)工作效率。紡織行業(yè)作為中國勞動密集度較高的傳統(tǒng)行業(yè)，毫無例外地受到時下信息化時代所帶來的浪潮沖擊，面臨著巨大挑戰(zhàn)的同時，也伴隨著潛在機遇。紡織業(yè)中印染行業(yè)的技術改造是重點對象之一，國家在技術開發(fā)和科技投入方面都出臺了有關的扶持政策，致力于使國內的印染行業(yè)不論是在質量、或是在效率方面都能夠得到全面的改善，進而提高該行業(yè)的整體競爭實力[1]。

染整車間的排產工作通常由專業(yè)人員根據生產任務單憑經驗來完成，但其結果卻存在很多問題。問題之一就是人工排產工作量大，耗費大量時間。問題之二是生產過程經常會出現無法預料的意外導致排產結果無效，需要進行二次排產調整。問題之三是專業(yè)人員雖然對生產流程的排產調度上具備著高度認知與豐富處理經驗，但是人工排產在結果上卻難以達到最優(yōu)化，不能充分、有效地切實發(fā)揮機臺的工作能力與運行效率。

由于排產調度是一個典型的NP難問題，學界也已在尋求近似最優(yōu)解方面取得了一定成果。如Nasr等人在1990年提出了2種啟發(fā)式方法，以確定n個作業(yè)/m臺機器問題的有效調度，并為每個操作提供了可選的機床路線[2]。Palmer在1996年開發(fā)了一種基于模擬退火（SA）的方法[3]。陳昌領等通過對單生產多目的的批處理過程建立短期調度混合整數規(guī)劃模型，并引入啟發(fā)式規(guī)則來求得包含多個同種訂單的調度相對最優(yōu)解[4-5]。目前，針對染整行業(yè)的排產問題，現已推出的設計解決方案就是染缸排產[6-8]，但是對于車間的自動排產研究還未見到有關文獻發(fā)表。

本文在對排產調度問題進行分析和建立數學模型的基礎上，結合遺傳算法提出染整車間自動排產方法，提高車間生產效率和機臺利用率，實現效率和利益的最大化。

1問題描述和數學模型

染整車間生產過程中的工序操作包括翻縫、打底、拉幅打卷、軋光、拉幅、烘培、絲光、燒毛、水洗、退漿、印花和蒸化，相應的工序對應機臺。排產調度受生產任務單型號規(guī)格、所需布長、生產流程鏈的差異和機臺車速等因素的影響。

問題描述在確保交期內生產完成的情況下，有n個生產任務單n1，n2，…，nn要在2～m個機臺上進行生產，機臺編號分別為m1，m2，…，mm，機臺對應生產工序。每個生產任務單有對應的生產流程鏈，每道工序加工時間確定，求出相對最優(yōu)加工批次進行生產且保證機臺滿負荷工作，減少機臺的刷車、切換次數。

本文的數學模型遵循以下約定：

（1）同一個生產任務單按流程鏈順序生產，但是不同生產任務單之間不存在流程先后約束。

（2）一個機臺只能接收一個生產任務單，且工序一旦開始不能停止。

（3）通過生產任務單中的布長信息和機臺車速信息求得每個生產任務單的加工時間。

（4）所有生產任務單都能按時完成，中途不會發(fā)生異常，如車速突然減慢、布料卡住等問題。

本文中，將給出如下數學符號含義設定：

N為生產任務單總數；M為機臺總數；i為生產任務單編號（i=1，2，3，…， N）；j為機臺編號（j=1，2，3，…，M）；ki為對于每一個生產任務單都有對應的生產流程鏈，ki表示編號為i的生產任務單工序數量；Oi是一個長度為ki的序列，表示生產任務單在機臺上的加工序列；Pkm是一個max{ki}*N的二維矩陣，表示編號為i的生產任務單需要在對應編號的機臺上加工，即生產任務單機臺加工路線；Tkm是一個max{ki}*M的二維矩陣，表示編號為n的生產任務單在Pkm對應的機臺上所需的加工時間，工序加工時間的數學運算形式如式（1）所示：工序加工時間=生產任務單布長機臺車速（1）至此，可以分析推得本次研究中的數學模型描述如下：

Mnm是一個N*M的二維矩陣，表示編號為j的機臺加工對應編號的生產任務單，即最后所需的結果表示為機臺生產任務單加工路線；Skm是一個max{ki}*M的二維矩陣，表示編號為n的生產任務單在Pkm對應的機臺上開始加工時間。

預先假設機臺生產任務單加工路線確定，求得在該路線基礎上的生產任務單工序的開始加工時間，不斷變換加工路線求出滿足目標函數式（2），即對應最快完工時間的那個生產任務單就是排產結果。由此，可得數學公式如下：Smin=min （∑Skm（2）2遺傳算法應用

本文結合生產實際情況和對問題的分析，在上述數學模型的基礎上，提出基于遺傳算法的染整車間排產調度方法。

遺傳算法在設計過程中，通常會分解為如下研究內容要點，分別是：染色體編碼、初代種群初始化、交叉操作、變異操作、選擇操作和評價函數。以及遺傳算法所需的遺傳參數，如種群大小、交叉概率、變異概率和種群最大迭代次數在算法啟動前均已確定。這里，可展開研究論述如下。

2.1染色體編碼方式

染色體為一個二維矩陣，矩陣行數為機臺編號，矩陣中基因表示為生產任務單編號，整個染色體表示為各生產任務單在機臺上的生產序列，對應數學模型中的Mnm，如例1的M22和M2' 2'是2個比較簡單直觀的染色體，具體如下：

例1M22 =12

12 M2' 2' =21

21

該染色體是一個完整的生產流程序列，M22 （0，j）（j=0，1）表示編號為1的機臺上依次生產編號為1，2的生產任務單， M22 （1， j）（j=0，1）表示編號為2的機臺上一次生產編號為1，2的生產任務單。且該染色體清晰明確，也不需要進行解碼。

在染色體編碼方式確定的情況下，隨機選取20例個體產生初代種群。研究中，種群染色體基因是機臺上加工生產任務單的順序，所有只要是生產任務單編號范圍內的就合法，因此將無需額外判斷產生的個體是否可行，只需將隨機選取的個體加入到種群即可。

對個體的評價是先根據機臺加工路線求得每個生產任務單的每道工序的開始時間。然后在知道開始時間的基礎上再求得整個加工過程最遲完工時間，這個時間就是個體的評分score。

2.2交叉操作

對染色體基因進行交叉操作時，由于此處選取的2個父個體在交叉過后無法保證每一例個體在結束后子串的基因值一致而引發(fā)致破壞個體穩(wěn)定性的后果，產生非法解。如例2的M22和M22，如果產生以下交換就是非法解，研究對其展示如下：

例2染色體非法交叉操作非法解：M22 = 22

12M2' 2' = 11

21所以為了保證染色體的可行性與穩(wěn)定性，需要在同一機臺上設計實現基因之間的交叉。

正確交叉為：如果交叉點為0和1之間，上述2個父個體M22和M2' 2'產生的孩子個體為21

12。這樣產生的孩子個體的機臺加工序列還是合法的，是可行解。

2.3變異操作

與交叉操作類似，如果隨機將染色體中基因變異成基因可取范圍內的其它值，會破壞染色體的穩(wěn)定性，并且產生非法解。例如將M22 = 12

12隨機選擇一個基因進行變異，產生22

12個體，就是非法解。所以為了保證染色體的穩(wěn)定性，可采用如下方式來構建變異操作，設計步驟流程可表述如下。

（1）依據變異概率確定需要產生的子代個體的個數。

（2）隨機選擇種群中的某一個體作為變異個體。

（3）隨機產生一個在機臺數量范圍之內的隨機數表示選取的一個機臺。

（4）再產生2個在機臺加工數量范圍之內的隨機數作為同機臺等基因的變異點，將2個變異點的基因進行互換，產生新的子代個體。

（5）重復步驟（2）～（4），直至產生所有子代個體。

2.4選擇操作

選擇操作采用輪盤賭選擇法，同時進一步結合了精英保存策略。

設有種群Pop，種群大小為pop_size，首先假設精英個體是第一個，種群中染色體個體Mi的適應度評分score為scorei，由式（3）計算可得每一個體的適應度值fi，也就是可得到如下計算公式：fi=1.0scorei（3）在遍歷計算的過程中，與精英個體進行比較得到種群精英個體，并且計算群體所有染色體個體適應度之和為：F=∑pop_sizei=1fi（4）這就形成了pop_size個區(qū)間為：[0，f1F][f1+f2F]...[∑popsize-1i=1fiF，1]再對種群進行遍歷，首先產生0～1之間的隨機數，保存第一個符合隨機數在區(qū)間之內的個體，直至選出全部所需染色體個體形成新的種群，同時保存最好的個體，即精英個體。

2.5終止條件

當迭代次數超過給定值后，算法停止運行，此時得到的最優(yōu)解就是排產調度所需的相對最優(yōu)排產方式。

3實驗驗證及結果分析

本實驗根據某紡織廠染整車間的真實情況，經過分析建模后選取如下機臺和生產任務單進行實驗驗證。現有7個機臺，分別為燒毛機、退漿機、絲光機、打底機、印花機、軋光機和蒸化機，對應的編號為1、2、3、4、5、6、7；另有5個生產任務單順次編號為1、2、3、4、5需要進行加工生產，設計中的生產流程鏈已確定，轉換為加工序列分別為：O1={2，1，3，4，5，6}，O2={1，2，3，6}，O3={1，3，4}，O4={3，4，5，6，7}，O5={3，4，5，6，7}。從加工序列可知，每一個生產任務單的生產工序數量為k1=6，k2=4，k3=3，k4=5，k5=5，由上述情況可得max{ki}=6，為此從生產任務單屬性和機臺屬性求得工序加工時間T65和生產任務機臺加工路線P65。運算得到結果數值為：

8.413.518.724.029.4從排產結果可知完成生產需要39.4 h，加工甘特圖如圖1所示。甘特圖中，p（i， j）表示編號為j的生產任務單在編號為i的機臺上進行加工生產。

將上述情況輸入到遺傳算法程序中，種群大小為20，交叉概率0.3，變異概率0.1，最大迭代次數為1 000，算法運行得到相對最優(yōu)排產序列M57，一并得到每個生產任務單每道工序的開工時間S75。算法結果數值為：M57 = 321

4.19.214.419.725.1加工甘特圖如圖2所示。甘特圖中，p（j，i）表示編號為i的生產任務單在編號為j的機臺上進行加工生產。

通過算法可得近似最優(yōu)排產方式，該排產結果的生產時間為30.6 h，相比人工排產結果的最終耗時39.4 h，求解速度更快，生產效率更高，機臺利用率更趨理想。并且隨著生產任務單的增多，排產組合會爆炸式上升，此時人工排產與算法排產的效率差異也將更為明顯。

4結束語

在信息化時代，傳統(tǒng)紡織行業(yè)需要緊跟時代潮流，并迫切需要提升企業(yè)生產效率，為此本文研究提出了基于遺傳算法的染整車間排產方法，求得染整車間排產相對最優(yōu)序列，通過實驗驗證和結果分析可知該方法實現了生產效率和利益相對最大化。

參考文獻

[1] 曹學軍. 我國印染行業(yè)現狀及發(fā)展趨勢[J]. 印染，2002（5）：39-42.

[2] NASR N， ELSAYED E A. Job shop scheduling with alternative machines[J]. International Journal of Production Research， 1990，28（9）：1595-1609.

[3]PALMER G J. A simulated annealing approach to integrated production scheduling[J]. Journal of Intelligent Manufacturing，1996，7（3）：163-176.

[4] 陳昌領，劉長齡，袁德成，等. 單階段多產品批處理過程的短期調度1.基本模型的建立[J]. 信息與控制，2002，31（2）：106-111.

[5] 陳昌領，馮曉東，邵惠鶴. 單生產線序貫多目的批處理過程短期調度的MILP建模[J]. 系統(tǒng)仿真學報，2001，13（S1）：69-71.

[6] 戴智杰，宋執(zhí)環(huán)，宋春躍. 基于遺傳算法的浸染生產排缸策略[J]. 運籌與管理，2006，15（2）：149-153.

[7] 莫豐勇，郝平，楊馬英. 基于遺傳算法的拉動式浸染生產動態(tài)排產策略[J]. 計算機應用，2008，28（S2）：97-99.

[8] 莫豐勇. 印染企業(yè)浸染生產排產優(yōu)化問題研究及系統(tǒng)設計[D]. 杭州：浙江工業(yè)大學，2008.

[9] LAOBOONLUR P ，HODGSON T J，THONEY K A. Production scheduling in a knitted fabric dyeing and finishing process[J]. The Journal of The Textile Institute，2006，97（5）：391-399.

[10]PINEDO M L. Scheduling： Theory， algorithms， and systems [M]. 2nd ed. New Jersey，USA： Prentice-Hall Inc， 2001.