基于窗口的印刷車間作業動態調度研究

郝 琪，邢潔芳

(南京林業大學 江蘇省制漿造紙科學與技術重點實驗室，南京 210037)

基于窗口的印刷車間作業動態調度研究

郝 琪，邢潔芳

(南京林業大學 江蘇省制漿造紙科學與技術重點實驗室，南京 210037)

為了解決實際印刷車間突發設備故障和緊急插單問題，采用滾動窗口技術結合遺傳算法的方法，建立適合實際印刷車間生產的動態再調度模型;設定若干印品訂單、機器設備的加工工序以及各工序加工時間、工序約束條件等，以訂單的最大最小加工時間和再調度的偏離度為多目標優化，采用周期與事件混合驅動策略，將滾動窗口再調度機制和遺傳算法相結合進行流程設計和編碼，構建印刷車間再調度模型;采用標準問題FT06和FT01驗證了文章設計的模型算法的有效性和可行性;運行程序，模擬正常加工時緊急插單和機器故障突發時，系統生產新的調度計劃即調度甘特圖，仿真結果表明該動態調度模型可以用于印刷作業的正常排產調度，在遇突發狀況時可生成穩定、符合交貨日期的再調度方案。

滾動窗口；遺傳算法；動態調度；印刷車間作業

0 引言

在多媒體數字出版飛速發展的背景下，使得客戶對印品的需求日益多樣化、個性化、印品生產周期不斷縮短，傳統書刊印刷企業需要著手解決提高產品質量、降低成本、高效生產、按時交付等方面的問題，解決這些問題的核心是解決印刷車間的動態調度問題。目前印刷車間的排產調度主要依賴于人工手動排產和靜動態調度+人工合作排產兩種方式，前者排產需要提前確定訂單類型、材料庫存、印刷工藝、設備等生產信息，調度周期較長；后者是在靜態算法下生成確定的排產計劃，當突發事件如緊急插單、機器故障等事件發生后，已有的排產計劃不再適用于當前生產，需要配合人工重新進行排產，排產計劃效率低、不靈活和隨意性高[1]。因此印刷企業迫切需要一套適合印刷生產工序的動態調度方案，來解決目前印刷車間調度的瓶頸問題。

Jackson[2]在1958年提出動態調度概念。當時動態調度研究方法主要為整數規劃、啟發式規則、離散系統仿真[3]等，這些方法可能存在一些問題如：解的質量不高、普遍性差、易受限制等問題，使得動態調度較靜態調度研究發展緩慢。直到Nelson等[4]在1977年提出了滾動窗口再調度策略，為動態調度研究開辟了新的思路。目前，文獻[5]將滾動窗口再調度模型應用于某航空發動機裝配車間調度中，解決了航空零件的動態調度；文獻[6]建立了關于集裝箱碼頭泊位的動態調度模型，實現了碼頭靈活調度。印刷企業調度問題起步較晚，近年來，主要研究集中于印刷企業ERP模型的建立和APS系統中靜態調度研究上，文獻[7]建立了印刷調度ERP模型，但沒研究調度算法模型；文獻[8]提出了APS系統遺傳算法模型的建立，但沒有解決突發事件的再調度。關于印刷車間動態調度研究還未被學者注意到，本文在借鑒文獻[5-6]的研究基礎上，結合GA算法建立適合印刷車間動態調度模型。

針對實際印刷車間常見的問題緊急插單和印刷設備故障，采用周期、事件驅動策略建立滾動窗口再調度模型。在沒有突發事件時，系統按GA生產周期調度計劃正常調度，當有緊急印単加入或印刷設備故障時，觸發再調度機制生產再調度方案。具有降低印刷企業生產陳本、靈活調度、達到印刷企業“零庫存”目標的深遠意義。

1 傳統書刊印刷車間動態調度問題描述

1.1 傳統書刊印刷車間描述

傳統書刊印刷不同于其他制造業，其生產任務是根據客戶要求制定，生產目標為“零剩余”，剩余產品不能再次銷售只能報廢，因此為了不造成企業資源浪費，對調度方案的精確度較高。印刷車間主要分為印前車間、印刷車間和印后車間[8]，印前車間主要利用計算機將原稿調整可印狀態、排版；印刷車間主要完成印刷任務，主要設備分為單色印刷機和彩色印刷機；印后車間主要完成印品表面整飾提高印品價值。傳統書刊印刷一般流程為：根據客戶的要求和提供的原稿將原稿進行處理、排版，設計印品印刷流程，進入印刷環節，將印刷好的印品進行折頁、配頁、裁切、包封面、壓光、覆膜等流程，完成整個印刷流程[9]。

圖1 印刷流程

1.2 數學模型的建立

變量定義:

(1)

s.tSTij≥BTi；

(2)

STij≥CTi(j-1)；

(3)

STij≥CTi′j′×Δij i′j′×Φi′j′(MEij);

(4)

CTij=STij+WTijm(MEij)；

(5)

(STij，CTij)∩(LLmp(MEij)p，UL(MEij)p)=φ；

(6)

i,i′=1,...,n,j=(ai+1),...,ni

j′=(ai′+1)，...,ni′,p=1,...,SLm(MEij);

(7)

(8)

i為印品號；

j為工序號；

m為機器號；

p為不可用時間號；

n為印品數量；

BTi為印品i最早可安排時間；

ni為印品i所包含工序數；

ai為印品i已安排的工序數；

M為設備數；

WTijm為印品i的第j道工序在設備m上的加工時間；

SLm為設備m上不可用時間段數；

LLmp為設備m上第p個不可用時間下線；

ULmp為設備m第p個不可用時間上線；

MEij為印品i的第j道工序分配到的設備；

STij為印品i的第j道工序開始時間；

CTij為印品i的第j道工序結束時間；

Ci為印品i所有工序加工完時間；

Sr為機器發生故障后生產的新的調度方案；

Sp為初始調度方案；α、β為加權系數。

式(1)為本文雙優化目標，采用加權將最小最大加工時間和調度穩定性兩個目標結合；式(2)為印品最早可安排時間約束，即根據系統再調度狀態，印品i前ai工序已被安排，后續只需要安排ai+1的工序；式(3)為工序加工順序約束，只要當印品完成前一道工序才能開始下一道工序；式(4)為設備約束，設備不能同時加工兩個印品；式(5)為印刷過程的連續性，一旦開始不能結束；式(6)為印刷加工時需要滿足機器在不可用時段約。

2 動態調度策略

滾動窗口再調度根據再調度策略可分為周期性再調度和事件驅動再調度[10]，前者是指以固定的周期重新再調度生產新調度方案，但不能及時響應突發事件，后者是指當突發事件發生時，觸發再調度生產新調度方案，此方法沒有對突發事件的預見性[11]；本文采用周期、事件驅動混合再調度，可充分結合兩者優勢彌補缺失。

2.1 動態調度過程

在使用滾動窗口再調度時，定義3個窗口：未印刷印品窗口S1、調度印品窗口S2、已完成印刷印品窗口S3。S1含還未進行印刷的印品，報廢或機器故障導致重新印刷的印品，緊急加單的印品；S2包括以一定原則選出來的印品將按照靜態算法進行排產，按照排產計劃進行印刷；S3包括已經完成所有印刷流程的印品；Wmax為窗口數量，W為S2中剩余印品數,Wlast為最終剩下未加工印品數。動態過程如下：

Step1：在初始時刻，從S1中以交貨緊迫度λ(t)=ti-t0為原則選取Wmax印品數將其放入S2中。其中t0為當前的再調度時刻，ti為印品交貨時間，因此值越小，越優先選擇放入印品調度窗口。

Step2：對S2窗口所有印品以目標函數f1進行GA算法靜態排產，生產預調度方案，執行預調度方案。

Step3：當突發事件或再調度周期ΔT到來時，將S2中已經完成全部印刷流程的印品拿出來放入S3中，再從S1選取min{(Wmax-W),Wlast}個印品放入S2中。

Step4：系統狀態更新。

Step5：對S2窗口所有印品以目標函數f3進行GA算法靜態排產，并執行排產計劃。

Step6：循環Step3、4、5直到所有產品調度結束。

圖2 窗口調度流程

2.2 動態系統狀態更新

當突發事件發生啟動系統再調度時，系統主要更新設備的再調度時刻和印品加工工序情況，如下更新：

2.2.1 印刷機再調度時的開始時刻

當發生再調度的時候，印刷設備處于三種狀態：空閑、工作、故障(設備保養)。當再調度時刻到來時，當印刷設備處于空閑狀態，則不需要修正印刷設備的再調度開始時刻；當印刷設備處于印刷狀態時，由于印刷加工的連續性不能直接使用該機器，已知再調度時刻t0，生成再調度方案時間實際忽略不計，Δti為當前印刷加工序完成剩余時間，則實際t0+Δti為印刷設備再調度開始時刻，因此實際再調度時間為CTij-t0；當印刷設備處于故障(設備保養)狀態時，在需要根據印刷設備可正常使用的時刻為印刷設備再調度開始時刻。當再調度時刻到來時，由于印刷設備比較多，各種設臺處于不同的狀態，需要對每臺設備修正其再調度時刻。

圖3 再調度機器可利用時間

如圖3在10時刻再調度，此時設備1處于空閑中，設備2、3屬于工作中，由于印刷的連續性，必須加工完成再開始調度，因此時刻10時，機器再調度時間分別為10、12、13。

2.2.2 印品工序矩陣的修正

再調度時刻印品的兩種狀態：全部印刷工序完成和部分印刷工序完成。當再調度時刻到來時，當印品處于的所有加工工序都完成的狀態時，把這個印品從S2移入S1中；當印品處于有部分加工完成工序的狀態時，將已經印刷完的工序和正在印刷的工序從印刷工序矩陣中移除，保留還未開始印刷的工序在矩陣中。當機器出現故障時，撤銷該設備正在加工的印品和t0時刻后該設備安排的印品工序，將這些工序放在任務集TK，假設印品i正在加工j工序，則印品i報廢，需全部工序放入TK中。

其中，從再調度的可行性、穩定性角度出發，需考慮窗口大小、周期長短。窗口中印品數量直接影響最終的優化結果，數量選取太小時，生成的調度方案優化不理想且設備利用率低，數量選取過大時，再調度計算時間較長，對突發事件響應時間較長，使得車間生產效率降低。通過大量學者研究周期對滾動窗口調度的影響，可歸納：隨著周期ΔT的增大，對總的完工時間影響較少，對總拖延期影響較大，總效率和穩定性降低。因此需要根據實際印刷車間訂單情況選取合理的周期[12]。

3 GA算法設計

GA算法是一種智能仿生的算法，其算法模型模仿達爾文進化論中的“適者生存，不適者淘汰”的進化過程[10]。它是在20世紀60年代由美國Michigan大學的John Holland設計出來的一種全局化、隨機搜索的優化算法[11]。

3.1 GA算法設計

適應值函數：F(i)=1/f3 。

選擇算子：本文采用輪盤賭法選擇較好的染色體，選擇概率為：

3.2 GA算法流程

Step1：隨機產生初始種群N。

Step2：以F(i)為評價函數，選出適應值高的染色體選出，傳遞給子代染色體。

Step3：以Pi(i)為概率取出染色體，按照設定的Pm、Pc進行交叉、變異操作，產生新的染色體。

Step4：判斷迭代次數是否到達，若是，結束循環，否則跳轉操作Step2。

圖4 算法流程圖

4 實驗仿真

4.1 GA算法驗證

本文用標準問題FT06和FT01來驗證本文采用GA算法的有效性，數據如表1所示。

表1 測試數據

表2 結果數據

圖5 FT06收斂曲線

圖6 FT01收斂曲線

從表2可以看出，本文的GA收斂速度較快，對比標準問題的解可得本文GA得出的解比較理想，綜上圖表可得本文GA的效果較為理想。

4.2 運行環境和參數確定

運行環境：Matlab 2008a。

參數確定：種群規模N=100，最大迭代次數為100,代溝G=0.9，交叉率Pm=0.8,變異率Pc=0.6，α為0.7，β為0.3，窗口的大小選擇3，周期為20再調度。

印刷車間作業調度仿真：

設備1、2為方正P5200單色雙面卷筒紙印刷機，設備3、4為三菱折頁機，設備5、6為日本Horizon三面刀設備，7、8為日本Horizon膠裝機，在印刷車間取6批書刊的印刷工藝數據，每個印品經歷印刷、折頁配貼、裁切、膠裝4道工序，實際工序較多，為了減少實驗用例的復雜度本文只選取了四道加工工序，數據如表3、表4所示。

表3 加工機器

表4 印品加工時間表

圖7 正常調度甘特圖

圖8 機器故障再調度甘特圖

圖9 緊急插單再調度

結果分析：正常調度下生成甘特圖7。圖中不同色塊代表不同印品，如色塊201代表印品2加工第一道工序所安排的開始時間和加工設備。當t=6時刻，設備3出現故障，在經過30時刻后修好，修好時刻為36時刻，生產甘特圖8。從圖7、8對比可以看出，在t=6時刻時，印品2正在折頁、配頁一體機3上折頁配貼，由于印刷的連續性，印品2報廢，需要重新印刷，印品3完成印刷還沒進行折頁配貼加工，同理印品4、6、7一樣沒有毀壞只需要重新安排調度，從圖8可知印品3、4、6重新安排到了折頁、配頁一體機4上進行生產，印品7在折頁、配頁一體機3修好后安排在折頁、配頁一體機3上生產。生成的再調度方案滿足交付日期規定。

在t=8時刻，緊急插入印品10，要求30時刻交付，生產再調度方案如圖9。對比圖7、9可知，當印品10插入時，給出的再調度計劃方案主要重新調度了印品4，其他產品并未受影響，可知本調度方案的偏離度較低。在正常調度圖7中時刻8時，印品4正在印刷機2上進行印刷，插入印品10時，在新的調度方案圖9中，印品4在12時刻被安排在印刷機1上重新印刷，印品4的后續加工全部重新安排了新的設備進行加工，印品10在8時刻被安排在印刷機2上開始進行印刷，在26時刻加工完成，印品4在32時刻完成加工，再調度方案符合交付日期。

4 結論

本文主要研究了品種多樣、產品工藝多變、個性化需求高、生產周期短的傳統印刷車間動態調度問題，以最小最大加工時間和調度的穩定性為調度優化目標，通過采用滾動窗口機制，結合GA算法建立了印刷車間動態調度模型。利用標準問題驗證了本文GA算法的有效性，根據印刷車間實際情況解決了當突發事件設備故障、緊急插單發生時，重新生成調度方案的問題，再調度方案具有可行性、偏離度低、滿足交付日期。該動態調度模型貼合實際印刷車間情況，有效地提高了交貨率、生產效率和機器利用率等，對印刷企業排產方式做了新的探索，為印刷企業管理生產提供了新的研究方向。但本文研究

的優化目標任然較為單一，收集的數據較少，日后將繼續采集數據建立更加貼合印刷車間的調度模型。

[1]張國輝.多階段人機協同求解動態柔性作業車間調度問題[J].控制與決策，2016，31(1)：169-172

[2]余琦瑋，蔣海清.柔性作業車間動態調度問題研究[J].管理錦囊，2013.

[3]呂盛萍，喬立紅.工藝規劃與車間調度及兩者集成的研究現狀和發展趨勢[J].計算機集成及制造系統，2014,20(2).

[4]王萬良，王 磊，王海燕.基于混合差分進化算法的作業車間動態調度[J].計算機集成及制造系統，2012,18(3):531-539.

[5]劉 欣，嚴宏森.基于窗口的某航空發動機裝配車間動態調度研究[J].計算機技術與發展，2013(12)：213-218.

[6]林志國，基于滾動窗口的集裝箱碼頭泊位動態調度研究[D].大連:大連海事大學，2009.

[7]李志敏，印刷廠管理ERP研究與開發[D].西安:西安理工大學，2007.

[8]趙奕然，印刷企業排產系統的研究與實現[D].武漢:華中科技大學，2007.

[9]王淑娟，柔性作業車間的多目標動態穩健調度研究[D].山東：山東大學，2014.

[10]何燕，基于遺傳算法的車間調度優化及仿真[D].湖北：武漢理工大學，2006.

[11]楊冬濤，基于遺傳算法的MES車間生產計劃動態調度研究[D].廣東：廣州工業大學，2008.

[12]黃英杰，基于目標級聯法和智能優化算法的車間調度問題研究[D].廣州:華南理工大學，2012.

[13]賈兆紅，粒子群優化算法在柔性作業車間調度中的應用研究[D].北京:中國科學技術大學，2008.

[14]陳振同.基于改進遺傳算法的車間調度問題研究與應用[D].大連:大連理工大學，2007.

[15] Geoff L. Application of mathematical programming—before, now and after. Operation Research Society, 1985, 35(5): 347-356

[16]徐雯雯，基于遺傳算法的車間動態粗調度研究[D].濟南：山東大學，2010.

Research on Dynamic Scheduling of Printing Workshop Based on Windows

Hao Qi,Xing Jiefang

(Jiangsu Provincial Key Lab of Pulp and Paper Science and Technology, Nanjing Forestry University,Nanjing 210037，China)

In order to solve the problem of emergent equipment failure and emergency insertion in practical printing workshop, a rolling window method combined with genetic algorithm was adopted to study,for the construction of dynamic production scheduling model of a practical printing shop. Set a number such as print orders, the processing time of the machine and Time-consuming equipment , the fastest time to finish the order and the stability of the scheduling are taken as the optimization target. By using the hybrid strategy of periodic and event driven, the rolling window rescheduling mechanism and genetic algorithm are combined to process design and coding.The validity and feasibility of the proposed algorithm are verified by the standard FT06 and FT01.Run the program to simulate the normal processing of emergency insert and machine failure,The system produces a new schedule,The simulation results show that the dynamic scheduling model can be used in the print job scheduling, in the event of a sudden situation can generate stable, in line with the delivery date of the rescheduling scheme.

scroll window; genetic algorithm; dynamic scheduling; printing workshop

2017-03-17；

2017-04-07。

國家級大學生實踐創新訓練計劃項目(201410298044Z)江蘇省產學研前瞻性聯合研究項目(BY2016006-01)。

郝 琪(1990-)，女，山西陽泉人，碩士，主要從事印刷與包裝工程方向的研究。

1671-4598(2017)12-0141-05

10.16526/j.cnki.11-4762/tp.2017.12.037

TH212；TH213.3

A