倪夢(mèng)妃 劉國(guó)華

文章編號(hào)： 2095-2163（2018）03-0041-05中圖分類號(hào)： 文獻(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àng)目：

作者簡(jiǎn)介：

收稿日期： 引言

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

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

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

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

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

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

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

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

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

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

（3）通過生產(chǎn)任務(wù)單中的布長(zhǎng)信息和機(jī)臺(tái)車速信息求得每個(gè)生產(chǎn)任務(wù)單的加工時(shí)間。

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

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

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

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

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

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

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

2.1染色體編碼方式

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

例1M22 =12

12 M2' 2' =21

21

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

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

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

2.2交叉操作

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

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

12M2' 2' = 11

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

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

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

2.3變異操作

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

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

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

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

（2）隨機(jī)選擇種群中的某一個(gè)體作為變異個(gè)體。

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

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

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

2.4選擇操作

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

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

2.5終止條件

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

3實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

[8] 莫豐勇. 印染企業(yè)浸染生產(chǎn)排產(chǎn)優(yōu)化問題研究及系統(tǒng)設(shè)計(jì)[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.