基于遺傳算法的染整車間自動排產(chǎn)問題研究

倪夢妃 劉國華

文章編號： 2095-2163（2018）03-0041-05中圖分類號： 文獻(xiàn)標(biāo)志碼： A

摘要： 關(guān)鍵詞： 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：

基金項目：

作者簡介：

收稿日期： 引言

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

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

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

本文在對排產(chǎn)調(diào)度問題進(jìn)行分析和建立數(shù)學(xué)模型的基礎(chǔ)上，結(jié)合遺傳算法提出染整車間自動排產(chǎn)方法，提高車間生產(chǎn)效率和機臺利用率，實現(xiàn)效率和利益的最大化。

1問題描述和數(shù)學(xué)模型

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

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

本文的數(shù)學(xué)模型遵循以下約定：

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

（2）一個機臺只能接收一個生產(chǎn)任務(wù)單，且工序一旦開始不能停止。

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

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

本文中，將給出如下數(shù)學(xué)符號含義設(shè)定：

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

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

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

本文結(jié)合生產(chǎn)實際情況和對問題的分析，在上述數(shù)學(xué)模型的基礎(chǔ)上，提出基于遺傳算法的染整車間排產(chǎn)調(diào)度方法。

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

2.1染色體編碼方式

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

例1M22 =12

12 M2' 2' =21

21

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

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

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

2.2交叉操作

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

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

12M2' 2' = 11

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

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

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

2.3變異操作

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

12隨機選擇一個基因進(jìn)行變異，產(chǎn)生22

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

（1）依據(jù)變異概率確定需要產(chǎn)生的子代個體的個數(shù)。

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

（3）隨機產(chǎn)生一個在機臺數(shù)量范圍之內(nèi)的隨機數(shù)表示選取的一個機臺。

（4）再產(chǎn)生2個在機臺加工數(shù)量范圍之內(nèi)的隨機數(shù)作為同機臺等基因的變異點，將2個變異點的基因進(jìn)行互換，產(chǎn)生新的子代個體。

（5）重復(fù)步驟（2）～（4），直至產(chǎn)生所有子代個體。

2.4選擇操作

選擇操作采用輪盤賭選擇法，同時進(jìn)一步結(jié)合了精英保存策略。

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

2.5終止條件

當(dāng)?shù)螖?shù)超過給定值后，算法停止運行，此時得到的最優(yōu)解就是排產(chǎn)調(diào)度所需的相對最優(yōu)排產(chǎn)方式。

3實驗驗證及結(jié)果分析

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

[1] 曹學(xué)軍. 我國印染行業(yè)現(xiàn)狀及發(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] 陳昌領(lǐng)，劉長齡，袁德成，等. 單階段多產(chǎn)品批處理過程的短期調(diào)度1.基本模型的建立[J]. 信息與控制，2002，31（2）：106-111.

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

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

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

[8] 莫豐勇. 印染企業(yè)浸染生產(chǎn)排產(chǎn)優(yōu)化問題研究及系統(tǒng)設(shè)計[D]. 杭州：浙江工業(yè)大學(xué)，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.