基于改進(jìn)遺傳算法的標(biāo)簽印刷生產(chǎn)調(diào)度技術(shù)

（南京理工大學(xué)機(jī)械工程學(xué)院，南京 210094）

0 引言

近年來(lái)，全球新技術(shù)革命和產(chǎn)業(yè)變革正在給制造企業(yè)的生產(chǎn)經(jīng)營(yíng)活動(dòng)帶來(lái)質(zhì)的變化［1］。企業(yè)生產(chǎn)規(guī)模擴(kuò)大的同時(shí)，客戶需求也越來(lái)越復(fù)雜，企業(yè)為了滿足客戶的個(gè)性化需求，逐步趨向MTO（Make To Order）的生產(chǎn)模式［2］。

標(biāo)簽印刷產(chǎn)品是一種用于簡(jiǎn)要標(biāo)明物品的名稱、質(zhì)量、尺寸和用途等的復(fù)合材料，它主要以涂硅保護(hù)紙作為底紙，在底紙背面涂上離型涂層粘附在涂有粘合劑的防粘紙上，最后經(jīng)過(guò)印刷、模切等工序成為成品標(biāo)簽。標(biāo)簽印刷產(chǎn)品具有種類多、印量小、印品的不可替代性等特點(diǎn)。在日益激烈的市場(chǎng)競(jìng)爭(zhēng)下，中小型標(biāo)簽印刷企業(yè)面臨著增強(qiáng)市場(chǎng)競(jìng)爭(zhēng)力、提高產(chǎn)品加工效率、降低生產(chǎn)成本的迫切需求［3］。但目前我國(guó)絕大多數(shù)的中小標(biāo)簽印刷企業(yè)仍然以傳統(tǒng)粗放式生產(chǎn)管理方式為主，企業(yè)的信息化水平較低［4］，雖然部分企業(yè)通過(guò)引進(jìn)企業(yè)資源計(jì)劃（Enterprise Resource Planning，ERP）生產(chǎn)管理系統(tǒng)來(lái)提高生產(chǎn)效率，但由于大部分企業(yè)所使用的ERP 系統(tǒng)側(cè)重于財(cái)務(wù)管理［5］，缺乏完善的生產(chǎn)調(diào)度模塊，無(wú)法發(fā)揮真正有效的作用。

近年來(lái)，車間調(diào)度問(wèn)題由于其多約束性、計(jì)算復(fù)雜和不確定性等特性，一直受到國(guó)內(nèi)外研究學(xué)者的廣泛關(guān)注［6］。國(guó)內(nèi)外學(xué)者通過(guò)研究和發(fā)展，提出了回溯搜索算法［7］、教與學(xué)算法［8］、猴群算法［9］和鯨魚優(yōu)化算法［10］等算法。劉巍巍等［11］提出用改進(jìn)變鄰域搜索算法求解柔性作業(yè)車間調(diào)度問(wèn)題，采用遺傳算法進(jìn)行最優(yōu)解搜索，并將搜索的結(jié)果作為變鄰域搜索算法的初始解，提高了初始解的質(zhì)量。Ye 等［12］以完工時(shí)間最小化為目標(biāo)，提出了平均撤出時(shí)間啟發(fā)式求解零等待車間調(diào)度問(wèn)題（No-Wait Flow shop Scheduling Problem，NWFSP），插入過(guò)程采用了目標(biāo)值增量法來(lái)降低算法的計(jì)算復(fù)雜度。印刷車間調(diào)度問(wèn)題相較普通車間調(diào)度問(wèn)題有所不同，印刷生產(chǎn)的工藝流程較為固定，但部分工藝環(huán)節(jié)的不確定性與復(fù)雜程度較高。針對(duì)這些問(wèn)題，Duan 等［13］提出了一種基于動(dòng)態(tài)增量進(jìn)化算法的高性能實(shí)時(shí)數(shù)字印刷生產(chǎn)調(diào)度算法，相較于規(guī)則的啟發(fā)式算法，該算法具有更高、更穩(wěn)定的訂單準(zhǔn)時(shí)交貨率。趙怡然［14］以作業(yè)排序優(yōu)化為目標(biāo)研究了印刷行業(yè)的生產(chǎn)計(jì)劃排程，設(shè)計(jì)了一種循環(huán)操作模式的遺傳算法，并建立手工排程與自動(dòng)排程相結(jié)合的印刷企業(yè)排程系統(tǒng)。

目前國(guó)內(nèi)外的研究主要是基于紙張印刷生產(chǎn)問(wèn)題，而對(duì)于標(biāo)簽印刷生產(chǎn)調(diào)度問(wèn)題的研究相對(duì)較少，本文主要針對(duì)標(biāo)簽印刷生產(chǎn)調(diào)度問(wèn)題進(jìn)行研究。上述研究對(duì)于求解標(biāo)簽印刷車間調(diào)度問(wèn)題提供了有效的方法，標(biāo)簽印刷過(guò)程除具有普通印刷生產(chǎn)加工工藝流程較為固定、部分工藝生產(chǎn)復(fù)雜度高等特點(diǎn)外，在實(shí)際生產(chǎn)過(guò)程中，由于標(biāo)簽印品種類多，根據(jù)客戶的個(gè)性化要求，部分工藝環(huán)節(jié)存在多臺(tái)設(shè)備可供選擇的情況，因此具有柔性作業(yè)車間調(diào)度的特點(diǎn)?；谝陨蠘?biāo)簽印刷車間調(diào)度問(wèn)題的特點(diǎn)，本文構(gòu)建了以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的柔性作業(yè)車間調(diào)度問(wèn)題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）調(diào)度模型，并提出了一種改進(jìn)遺傳算法對(duì)該模型進(jìn)行求解，從而對(duì)標(biāo)簽印刷車間的調(diào)度問(wèn)題進(jìn)行研究。

1 標(biāo)簽印刷行業(yè)生產(chǎn)管理現(xiàn)狀

1.1 標(biāo)簽印刷生產(chǎn)工藝流程

標(biāo)簽印刷產(chǎn)品應(yīng)用廣泛，具有使用方便、撕下即貼、價(jià)格便宜等特點(diǎn)。大多數(shù)標(biāo)簽印刷產(chǎn)品采用不干膠印刷工藝，圖1 展示的是不干膠標(biāo)簽印刷產(chǎn)品的結(jié)構(gòu)圖。標(biāo)簽印刷最底層為承印物，在承印物背面涂上離型涂層，粘附在涂有粘合劑的防粘紙上。印刷完成后通過(guò)模切工序?qū)⒎勒臣堒堄〕鏊栊螤?，使用時(shí)撕下即貼。

標(biāo)簽印刷工藝流程主要包括印前、印中、印后三個(gè)部分。印前包括購(gòu)買原材料、原稿設(shè)計(jì)、圖像錄入、印前圖文處理、刀模定制、印刷版制版、油墨調(diào)色、機(jī)器調(diào)機(jī)等。其中，油墨調(diào)色和調(diào)機(jī)都非常依賴車間師傅的技術(shù)經(jīng)驗(yàn)，具有很大的不確定性。印中主要包括產(chǎn)品印刷、模切、燙金。印后處理主要包括產(chǎn)品質(zhì)量檢驗(yàn)、分條等。根據(jù)客戶需求不同，部分標(biāo)簽印刷產(chǎn)品需要進(jìn)行表面加工，主要包括上光、覆膜、電化鋁燙、壓痕等操作。

圖1 不干膠印刷產(chǎn)品結(jié)構(gòu)Fig.1 Structure of pressure sensitive adhesive printing product

在實(shí)際的車間生產(chǎn)過(guò)程中，普通不干膠標(biāo)簽的印刷生產(chǎn)工藝流程如圖2 所示。上料工序包括開卷、機(jī)器調(diào)機(jī)和油墨調(diào)色等工序，但因?yàn)檫@些工序都是人工進(jìn)行操作，所以在后續(xù)的工序研究中直接從印刷工序開始研究。目前不干膠印刷有凸版印刷、膠版印刷、網(wǎng)版印刷、柔印版印刷和凹版印刷這五種印刷方式，其中凸版印刷和膠版印刷方式是目前最為廣泛使用的印刷方式。模切又可分為全切、壓痕和半切三種模切方式，模切后進(jìn)入燙金工序，模切與燙金既可以是兩臺(tái)機(jī)器，也可以是同一臺(tái)機(jī)器既實(shí)現(xiàn)模切工序，又完成燙金工序。品檢和分條是標(biāo)簽印刷生產(chǎn)的最后兩道工序環(huán)節(jié)。

圖2 不干膠標(biāo)簽印刷工藝流程Fig.2 Procedure of pressure sensitive adhesive label printing

1.2 標(biāo)簽印刷生產(chǎn)過(guò)程中存在的問(wèn)題分析

標(biāo)簽印刷行業(yè)在MTO 的生產(chǎn)模式下，其生產(chǎn)過(guò)程中存在的特點(diǎn)主要包括：

1）印品種類多、單次印刷量少。標(biāo)簽印刷產(chǎn)品應(yīng)用領(lǐng)域廣泛，且同一產(chǎn)品的標(biāo)簽根據(jù)客戶企業(yè)個(gè)性化需求不同，其生產(chǎn)工藝、材料、配色均有所不同，且單次印刷量少，顏色和刀模切換頻繁。因此，多品種小批量是標(biāo)簽印刷生產(chǎn)調(diào)度的特點(diǎn)，也是難點(diǎn)。

2）客戶個(gè)性化需求高。客戶對(duì)標(biāo)簽的大小尺寸、使用材料、顏色配色、圖案布局、表面處理工藝以及交貨期等需求都因人而異。因此，在滿足不同客戶需求的前提下，要提高加工效率，對(duì)企業(yè)車間生產(chǎn)進(jìn)度的安排提出了很高的要求。

3）不確定性程度高。標(biāo)簽印刷生產(chǎn)的上料準(zhǔn)備工序包含了調(diào)機(jī)、油墨調(diào)色工序，而調(diào)機(jī)和調(diào)色時(shí)間非常依賴車間師傅經(jīng)驗(yàn)，不確定性很大。標(biāo)簽印刷產(chǎn)品雖然加工工序嚴(yán)格，但在實(shí)際生產(chǎn)中，存在部分工序有多臺(tái)機(jī)器可選擇的情況，因此標(biāo)簽印刷生產(chǎn)過(guò)程存在較大的柔性。

4）突發(fā)狀況發(fā)生頻繁。對(duì)于中小企業(yè)來(lái)說(shuō)，由于其管理不善，經(jīng)常會(huì)發(fā)生緊急訂單插入、設(shè)備故障、原材料逾期到貨等突發(fā)事件，傳統(tǒng)的人工排產(chǎn)難以保證重調(diào)度的高效性與可行性。

在實(shí)際生產(chǎn)過(guò)程中，對(duì)于標(biāo)簽印刷生產(chǎn)過(guò)程中存在的多品種、小批量和客戶個(gè)性化需求高的問(wèn)題，企業(yè)所使用的手工排產(chǎn)方式無(wú)法在問(wèn)題實(shí)質(zhì)上進(jìn)行有效解決。本文通過(guò)結(jié)合標(biāo)簽印刷生產(chǎn)過(guò)程中存在工序柔性的特點(diǎn)，將柔性作業(yè)車間調(diào)度模型應(yīng)用到標(biāo)簽印刷生產(chǎn)調(diào)度問(wèn)題中，構(gòu)建標(biāo)簽印刷生產(chǎn)調(diào)度問(wèn)題的靜態(tài)調(diào)度模型，并采用改進(jìn)遺傳算法進(jìn)行求解，從而實(shí)現(xiàn)自動(dòng)排產(chǎn)功能，有效提高加工效率。針對(duì)生產(chǎn)過(guò)程中突發(fā)狀況發(fā)生頻繁這一問(wèn)題，在實(shí)現(xiàn)本文靜態(tài)車間調(diào)度的基礎(chǔ)上可以進(jìn)一步展開動(dòng)態(tài)車間調(diào)度，從而有效解決這一問(wèn)題。針對(duì)上述問(wèn)題的分析，本文對(duì)標(biāo)簽印刷生產(chǎn)車間的調(diào)度問(wèn)題開展了相關(guān)研究。

2 問(wèn)題描述

標(biāo)簽印刷企業(yè)柔性作業(yè)車間調(diào)度問(wèn)題描述為：有n個(gè)印品需要在m臺(tái)加工機(jī)器上進(jìn)行加工，每個(gè)印品包含一道及以上的加工工序，工序順序是提前確定好的，每道工序存在一臺(tái)及以上的設(shè)備可供使用加工，但同一工序所使用的設(shè)備不同，加工時(shí)間也不同，最終目標(biāo)是確定每個(gè)印品的每道工序在不同機(jī)器上的加工順序，從而使得最大完工時(shí)間取得最優(yōu)值。

下面是針對(duì)該車間調(diào)度模型的假設(shè)：

1）每臺(tái)機(jī)器同一時(shí)刻只能加工一個(gè)印品。

2）每道工序只能在一臺(tái)機(jī)器上加工。

3）每個(gè)印品在加工過(guò)程中必須按照既定的工序進(jìn)行加工，前一道工序加工完以后立即送下一道工序加工。

4）加工過(guò)程不允許中斷。一件印品一旦開始加工，必須加工到最后一道工序完工，不允許中途停工插入其他工件。

下面對(duì)有關(guān)符號(hào)進(jìn)行說(shuō)明：

1）Ji為印品i（i=1，2，…，n）；

2）Kq為印品加工工序q（q=1，2，…，p）；

3）Mj為機(jī)器j（j=1，2，…，m）；

4）Di為印品i的交貨期；

5）Siq為印品i的第q道工序的開始加工時(shí)間；

6）Tiq為印品i的第q道工序的結(jié)束加工時(shí)間；

7）Ciq為印品i的第q道工序的加工時(shí)間；

8）Ciqj為印品i的第q道工序在機(jī)器j上的加工時(shí)間；

9）Cij為印品i在機(jī)器j上的加工時(shí)間；

10）Xiqj印品i的第q道工序在機(jī)器j上加工其他；

11）Ci為印品Ji的加工完工時(shí)間；

12）Cmax為最長(zhǎng)完工時(shí)間，Cmax=

本文針對(duì)標(biāo)簽印刷企業(yè)作業(yè)車間調(diào)度問(wèn)題采用最長(zhǎng)完工時(shí)間最短指標(biāo)為評(píng)價(jià)指標(biāo)，相應(yīng)的數(shù)學(xué)模型如下。

優(yōu)化目標(biāo)：

約束條件：

式（1）為優(yōu)化目標(biāo)函數(shù)，式（2）表示工序約束，式（3）和式（4）表示對(duì)加工機(jī)器的約束，式（5）表示每一個(gè)印品的每道工序開始加工時(shí)不能被中斷，式（6）表示各下標(biāo)變量的取值范圍。

3 算法操作分析與設(shè)計(jì)

本文研究標(biāo)簽印刷企業(yè)車間調(diào)度問(wèn)題時(shí)采用整數(shù)編碼對(duì)簡(jiǎn)單遺傳算法做了改進(jìn)，根據(jù)圖3 所示的運(yùn)算流程，主要步驟為：1）取代傳統(tǒng)的二進(jìn)制編碼，根據(jù)待優(yōu)化問(wèn)題參數(shù)集進(jìn)行整數(shù)編碼，生成隨機(jī)初始種群；2）計(jì)算染色體適應(yīng)度值，結(jié)合精英解保留策略［15］和輪盤賭法選擇適應(yīng)度值最高的染色體傳遞給子代染色體；3）進(jìn)行交叉、變異操作，并采用設(shè)計(jì)的動(dòng)態(tài)自適應(yīng)交叉和變異概率，從而得到新的子代染色體；；4）通過(guò)迭代次數(shù)判斷是否結(jié)束運(yùn)行，當(dāng)滿足迭代次數(shù)時(shí)，將得到的具有最大適應(yīng)度值的染色體確定為最優(yōu)解，并通過(guò)解碼輸出最優(yōu)解。

圖3 改進(jìn)遺傳算法運(yùn)算流程Fig.3 Operation flow of the improved genetic algorithm

1）編碼。

本文研究的車間調(diào)度模型中，待加工印品個(gè)數(shù)為n，當(dāng)印品ni的工序個(gè)數(shù)為mj時(shí)，染色體長(zhǎng)度為整數(shù)串，即每個(gè)染色體分為兩部分：前半段nimj部分表示所有印品的加工順序，而后半段nimj部分表示印品加工前半段染色體所對(duì)應(yīng)的工序時(shí)的機(jī)器號(hào)。如圖4所示，該染色體包含24個(gè)元素，表示有4 個(gè)待加工印品，每個(gè)印品有3 道工序，共有3 臺(tái)加工機(jī)器去完成所有工序加工。

圖4 染色體編號(hào)Fig.4 Chromosome codes

圖5 為所有待加工印品的加工順序，其中，該序列中的第一個(gè)3 表示待加工印品3 的第一道工序，第二個(gè)3 表示待加工印品3 的第二道工序，以此類推所有待加工印品的加工工序順序。圖6所示為加工每道工序時(shí)所對(duì)應(yīng)的機(jī)器號(hào)，其中，M1表示機(jī)器1，M2表示機(jī)器1，以此類推所有待加工印品加工每道工序時(shí)所使用的機(jī)器。

圖5 染色體前12位Fig.5 Top 12 chromosomes

圖6 染色體后12位Fig.6 Last 12 chromosomes

2）解碼。

求得最佳染色體個(gè)體后，需要通過(guò)解碼確定每個(gè)印品的每道工序在機(jī)器上的加工順序。本文從染色體的第1 個(gè)基因位開始對(duì)染色體的所有基因順序進(jìn)行解碼，假設(shè)第I個(gè)基因?yàn)閍，該基因是第X個(gè)出現(xiàn)，則該位基因解碼表示為a*100 +X，且解碼前與解碼后的染色體長(zhǎng)度保持不變。

3）適應(yīng)度函數(shù)。

在本調(diào)度模型中，染色體適應(yīng)度值函數(shù)即為優(yōu)化指標(biāo)f，f越大，即工件最長(zhǎng)完工時(shí)間越短，染色體適應(yīng)度值越好。適應(yīng)度計(jì)算公式為：

4）選擇操作。

選擇操作時(shí)運(yùn)用精英解保留策略和輪盤賭法相結(jié)合的策略，選擇出種群中適應(yīng)度值最大的染色體直接傳遞給子代染色體，然后通過(guò)輪盤賭法選擇其余適應(yīng)度值較好的染色體傳遞給子代染色體，染色體選擇概率為：

其中：Pi(i)表示在每次的選擇中染色體i被選中的概率。

5）交叉操作。

交叉操作分為以下兩個(gè)步驟：

圖7 交叉操作算法Fig.7 Crossover operation algorithm

②交叉后產(chǎn)生新的子代染色體S1'和S2'，但S1'和S2'染色體存在某些工件有多余工序和某些工件缺失工序的不可行性問(wèn)題。比如S1'染色體，在前部分染色體中，工件2出現(xiàn)4 道工序，而工件3 只有2 道工序。S2'染色體的前部分染色體中，工件3 出現(xiàn)4 道工序，而工件2 只有2道工序，因此，對(duì)S1'和S2'染色體，分別需要用多余的工序代替缺失的工序，如S1'染色體中用缺失的工件3 的第3 道工序去替換多余的工件2的第4道工序。S2'染色體中用缺失的工件2 的第3 道染色體去替換多余的工件3 的第4 道染色體，并按照交叉前染色體部分顯示的每個(gè)工件每道工序所使用的機(jī)器加工順序來(lái)調(diào)整S1'和S2'的至部分的機(jī)器加工順序，調(diào)整后的染色體如圖8所示。

圖8 變異操作算法1Fig.8 Mutation operation algorithm 1

6）變異操作。

通過(guò)變異操作可以獲得新的子代染色體，從而促使種群進(jìn)一步進(jìn)化。本文進(jìn)行染色體變異操作的步驟：從種群中隨機(jī)選擇父代變異染色體，在前部分染色體中，隨機(jī)選擇兩個(gè)變異位置Pos1 和Pos2，對(duì)調(diào)Pos1 和Pos2 位置的元素，并將Pos1 和Pos2 位置上工序所對(duì)應(yīng)染色體后部分中機(jī)器加工順序進(jìn)行對(duì)調(diào)，從而得到新的子代染色體。如圖9所示，假設(shè)隨機(jī)選擇的變異位置Pos1=3，Pos2=3。

圖9 變異操作算法2Fig.9 Mutation operation algorithm 2

7）改進(jìn)的自適應(yīng)交叉和變異概率。

傳統(tǒng)的遺傳算法在進(jìn)行交叉與變異操作時(shí)都是選擇固定的交叉概率和變異概率，這對(duì)求最優(yōu)解增加了難度。當(dāng)交叉概率和變異概率取較小數(shù)值時(shí)會(huì)造成搜索范圍變小的情況，不利于尋優(yōu)。而取較大數(shù)值時(shí)，極易導(dǎo)致在得到最優(yōu)個(gè)體時(shí)經(jīng)過(guò)交叉和變異操作后使個(gè)體適應(yīng)度降低。因此，本文在算法操作過(guò)程中設(shè)計(jì)了如式（1）～（3）所示的動(dòng)態(tài)自適應(yīng)交叉和變異概率，從兩個(gè)方面改進(jìn)最優(yōu)解的尋優(yōu)過(guò)程。一方面，根據(jù)個(gè)體在種群中的適應(yīng)度值大小來(lái)給予相應(yīng)的交叉概率和變異概率，規(guī)則是適應(yīng)度值較大的相對(duì)給予較大的交叉概率和變異概率，適應(yīng)度值較小的相對(duì)給予較小的交叉概率和變異概率。另一方面，通過(guò)采用動(dòng)態(tài)概率遍歷種群，使個(gè)體在前期以較大的概率進(jìn)行交叉和變異操作，擴(kuò)大尋優(yōu)范圍，保證算法不出現(xiàn)早熟現(xiàn)象，而在后期則以較小的概率進(jìn)行交叉和變異操作，使在前期得到的優(yōu)良個(gè)體不會(huì)因?yàn)檩^大的概率而降低適應(yīng)度值，也進(jìn)一步加快算法收斂。

式（10）～（12）中：i為當(dāng)前迭代次數(shù)，迭代到第N次時(shí)迭代結(jié)束，ν為調(diào)整參數(shù)，取值范圍為區(qū)間[1，5]內(nèi)的整數(shù)；Pt為交叉概率；Pm為變異概率；kc和km為常數(shù)，取值范圍為[0，1]；fc和fm分別為兩交叉?zhèn)€體較大的適應(yīng)度值和兩變異個(gè)體較大的適應(yīng)度值；fa為種群的平均適應(yīng)度值；fmax為當(dāng)前種群最大的適應(yīng)度值。

4 基準(zhǔn)算例仿真及驗(yàn)證

本文以文獻(xiàn)［16］的Ft06基準(zhǔn)算例來(lái)驗(yàn)證改進(jìn)后的遺傳算法的性能。通過(guò)Matlab 2019a在Windows 10的64位操作系統(tǒng)上實(shí)現(xiàn)。改進(jìn)遺傳算法中的主要參數(shù)設(shè)置為：種群規(guī)模N=100，代溝GGAP=0.9，進(jìn)化代數(shù)G=100，交叉概率Pc和變異概率Pm分別由式（11）和式（12）確定，其中，參數(shù)取值為kc=0.9，km=0.12，ν分別取1、2、3、4、5，將改進(jìn)遺傳算法在ν取值分別為1、2、3、4、5 時(shí)的運(yùn)行結(jié)果和標(biāo)準(zhǔn)遺傳算法（Genetic Algorithm，GA）運(yùn)行結(jié)果進(jìn)行比較，結(jié)果如表1所示。

表1 改進(jìn)遺傳算法與標(biāo)準(zhǔn)遺傳算法結(jié)果對(duì)比Tab.1 Result comparison between the improved genetic algorithm and standard genetic algorithm

由表1 中數(shù)據(jù)可知，本文算法多次運(yùn)行的最優(yōu)解均優(yōu)于標(biāo)準(zhǔn)遺傳算法的最優(yōu)解，而且當(dāng)ν=3 時(shí)，本文算法的平均迭代次數(shù)明顯低于標(biāo)準(zhǔn)遺傳算法。圖10 是當(dāng)ν=3 時(shí)算例進(jìn)化曲線，通過(guò)運(yùn)算很快得到最佳個(gè)體為［3 3 2 6 1 1 3 2 6 4 2 4 5 3 4 6 2 1 1 1 5 4 5 2 3 6 5 2 3 4 5 5 6 1 6 4］，圖11 是當(dāng)ν=3 時(shí)本文改進(jìn)算法與標(biāo)準(zhǔn)遺傳算法進(jìn)化對(duì)比，由圖11 可知，本文算法進(jìn)化到第12代已經(jīng)得到最優(yōu)解，而標(biāo)準(zhǔn)遺傳算法迭代到50代才得到最優(yōu)解。

圖10 Ft06算例進(jìn)化曲線Fig.10 Evolution curve of Ft06 example

圖11 不同算法進(jìn)化曲線對(duì)比Fig.11 Comparison of evolution curves of different algorithm

本文進(jìn)一步采用文獻(xiàn)［17］、文獻(xiàn)［18］和文獻(xiàn)［19］相同的8× 8、10 × 10 和15× 10 的FJSP 標(biāo)準(zhǔn)算例和文獻(xiàn)中的方法來(lái)驗(yàn)證算法的穩(wěn)定性和尋優(yōu)性能，測(cè)試結(jié)果如表2所示。由表2可以看出，在3 個(gè)標(biāo)準(zhǔn)測(cè)試算例中，本文的改進(jìn)算法均在較短時(shí)間內(nèi)獲得了最優(yōu)解，T表示本文算法求得最優(yōu)解的時(shí)間。

表2 改進(jìn)遺傳算法與其他算法結(jié)果對(duì)比 單位：sTab.2 Result comparison between the improved genetic algorithm and other algorithms unit：s

根據(jù)上述研究可知，本文提出的改進(jìn)遺傳算法不僅具有良好的搜索能力，還有更高的搜索速度，從而驗(yàn)證了本文算法是可行且高效的。

5 標(biāo)簽印刷企業(yè)車間靜態(tài)調(diào)度仿真分析

本文以某標(biāo)簽印刷廠的實(shí)際生產(chǎn)車間為背景，運(yùn)用本文所提出的改進(jìn)遺傳算法進(jìn)行仿真，得出調(diào)度方案，并與企業(yè)當(dāng)天實(shí)際手工排產(chǎn)方案進(jìn)行比較分析，從而驗(yàn)證本文改進(jìn)算法的有效性。運(yùn)行參數(shù)設(shè)置為：種群規(guī)模N=100，代溝GGAP=0.9，交叉概率Pc=0.8，變異概率Pm=0.6，進(jìn)化代數(shù)G=100。

5.1 標(biāo)簽印刷企業(yè)車間實(shí)際情況描述

該企業(yè)是一家專業(yè)生產(chǎn)高檔標(biāo)簽印刷制品的印刷企業(yè)，具有印刷車間、模切（燙金）車間、品檢車間、分條車間。車間主要用于加工不干膠標(biāo)簽，其加工過(guò)程主要涉及5 道工序，加工順序分別為：印刷、模切、燙金、品檢、分條。車間有8 臺(tái)機(jī)器，機(jī)器1、2 為預(yù)涂感光版（Pre-coated photoSensitive plate，PS版）印刷機(jī)，機(jī)器3 為數(shù)字印刷機(jī)、機(jī)器4、5 為激光數(shù)控模切機(jī)、機(jī)器6 為燙金機(jī)、機(jī)器7 為品檢機(jī)、機(jī)器8 為分條機(jī)。待加工印品的每道工序可選機(jī)器如表3 所示，每道工序加工時(shí)間如表4所示，時(shí)間單位是分鐘（min）。

表3 各工序可選機(jī)器Tab.3 Selectable machines for different procedures

表4 工序加工時(shí)間單位：minTab.4 Procedure processing timeunit：min

5.2 仿真結(jié)果分析

由如圖12 所示的算法搜索過(guò)程可知，所有印品迭代到第10次時(shí)已經(jīng)得到最優(yōu)解。圖13所示的加工排產(chǎn)甘特圖中，橫坐標(biāo)表示印品加工時(shí)間，縱坐標(biāo)表示工序所使用設(shè)備，同一色塊表示同一種標(biāo)簽的不同加工工序在不同設(shè)備上進(jìn)行加工，比如，模塊201 表示印品2 的第一道加工工序——印刷，且該工序在100 min 時(shí)刻在第一臺(tái)機(jī)器上開始加工，至148 min 時(shí)刻完成該道工序的加工。由圖13 可知，完成6 種標(biāo)簽印刷印品的加工完工時(shí)間為322 min，而該標(biāo)簽印刷企業(yè)實(shí)際當(dāng)天加工生產(chǎn)該筆訂單的時(shí)間為648 min，加工效率提高50.3%。由此可見，本文提出的求解標(biāo)簽印刷生產(chǎn)調(diào)度模型的改進(jìn)遺傳算法可以有效提高加工效率，大大提高機(jī)器使用率，縮短了印品生產(chǎn)加工周期，可以直接用于標(biāo)簽印刷企業(yè)的實(shí)際生產(chǎn)調(diào)度。

圖12 改進(jìn)遺傳算法搜索過(guò)程Fig.12 Search process of the improved genetic algorithm

圖13 加工排產(chǎn)甘特圖Fig.13 Gantt diagram of production scheduling

6 結(jié)語(yǔ)

本文基于標(biāo)簽印刷生產(chǎn)過(guò)程中存在印品種類多、單次印刷量少、客戶個(gè)性化需求高等問(wèn)題，并針對(duì)其車間調(diào)度問(wèn)題復(fù)雜程度高、具有不確定性等特點(diǎn)，構(gòu)建了以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的FJSP 調(diào)度模型，并提出了一種改進(jìn)遺傳算法對(duì)該模型進(jìn)行求解。算法首先從編碼方式和個(gè)體選擇兩方面進(jìn)行改進(jìn)，整數(shù)編碼方式具有穩(wěn)定性好、收斂快等特點(diǎn)，在選擇階段采用輪盤賭法并引入精英解保留策略來(lái)確保算法的收斂性。還提出了一種動(dòng)態(tài)自適應(yīng)交叉和變異概率，在前期實(shí)現(xiàn)較大范圍尋優(yōu)，避免算法發(fā)生早熟現(xiàn)象，后期保證得到的最優(yōu)個(gè)體不遭到破壞，實(shí)現(xiàn)較快收斂。實(shí)驗(yàn)過(guò)程采用標(biāo)準(zhǔn)算例對(duì)算法的有效性和穩(wěn)定性進(jìn)行了驗(yàn)證，并針對(duì)某標(biāo)簽印刷企業(yè)的實(shí)際生產(chǎn)情況，利用本文的改進(jìn)遺傳算法求解出該標(biāo)簽印刷車間的生產(chǎn)調(diào)度方案，與實(shí)際手工排產(chǎn)完工時(shí)間進(jìn)行比較分析得出，在該模型下加工效率提高了50.3%，使得機(jī)器使用率大大提高，縮短了印品生產(chǎn)加工周期，有效解決了交貨期不準(zhǔn)時(shí)的問(wèn)題，進(jìn)一步表明了本文算法求解標(biāo)簽印刷產(chǎn)品生產(chǎn)調(diào)度問(wèn)題的可行性和有效性。

但本文研究只針對(duì)標(biāo)簽印刷生產(chǎn)加工的靜態(tài)車間調(diào)度模型，在實(shí)際生產(chǎn)過(guò)程中，經(jīng)常會(huì)發(fā)生緊急訂單插入、設(shè)備故障、原材料逾期到貨等突發(fā)事件，因此，在后續(xù)的研究中會(huì)繼續(xù)對(duì)動(dòng)態(tài)車間調(diào)度問(wèn)題進(jìn)行深入研究。