基于遺傳算法的印刷企業生產調度模型的構建

郝 琪，張緒勇，邢潔芳

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

基于遺傳算法的印刷企業生產調度模型的構建

郝 琪，張緒勇，邢潔芳

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

目的：針對網絡數字印刷訂單多、周期短等特點，利用遺傳算法求解印品的生產計劃排產問題。方法 設定若干印品訂單、加工工藝、機器設備以及各工序加工時間，采用多層編碼遺傳算法進行編程計算，通過MATLAB模擬驗證遺傳算法用于求解調度問題所得到的效果，獲得排產順序甘特圖。結果：通過算法搜索過程可知，全部印品加工總時間在第8次迭代時趨于最小值，并且設計算法收斂較快，運算效率較高。調度人員在正常生產條件下，可以通過甘特圖直觀地進行生產計劃排產，能夠使車間在保證交貨期的前提下快速而又有條不紊的進行生產，縮短了印刷加工周期，提高了機器利用率和生產效率。結論：遺傳算法靜態生產調度模型可以有效用于印刷作業的一般排產調度，在遇突發狀態時可參與人工配合調整，或者需要提供動態調度解決方案。

ERP；遺傳算法；印刷生產；調度模型

0 引言

近年來，全球化競爭日益激烈，中國印刷企業面臨著需要提高企業核心競爭力的迫切需求[1]。無論是長版的傳統印刷還是短版的數字印刷，都存在著生產管理效率低下的問題。許多印刷企業通過引入ERP管理系統來提高生產效率，效果仍無法令人滿意。譬如ERP生產管理系統中的調度模塊并不完善，其原理是在MRPII的基礎上基于無限物料、無限能力的理論，只能根據物料生成粗略的調度計劃，不能生成具體調度方案[2～6]。

針對目前印刷企業ERP生產排產中存在的問題，多數學者提出兩種方案：1）將ERP系統與APS高級排產系統結合使用[7]；2）將一些智能算法直接鑲嵌在ERP系統的車間調度模塊中進行優化排產。前者，雖然APS系統可以補充、優化ERP系統在排產上的不足，但兩者結合存在很多兼容問題[8]，在使用過程中仍較繁瑣。后者，由于智能算法復雜、數據量較大，占用存儲空間較大，給系統帶來巨大負擔[9,10]。有學者將其應用于船舶停靠、機械零件加工等方面的調度，但仍存在不完全貼合實際生產的情況[11～13]。如何選擇合適的智能算法，并根據印刷車間生產特點做一些適當的簡化，使其運算量減少，從而能夠有效的用于印刷車間的生產調度。因此，本文針對網絡短版數字印刷的印品種類繁多、印量少、交貨期短等特點，選擇遺傳算法用于數字印刷車間的生產計劃排產，構建其生產調度模型。

1 可行性分析

目前有眾多算法應用在ERP車間調度模塊中，這些算法或多或少都存在著一些不足，與其他算法相比較，遺傳算法有一定的優勢。遺傳算法是一種智能仿生的算法，其算法模型模仿達爾文進化論中的“適者生存，不適者淘汰”的進化過程。它是在20世紀60年代，由美國Michigan大學的John Holland設計出來的一種全局化、隨機搜索的優化算法。遺傳算法一般認為有五個基本組成部分：1）問題的解的遺傳表示；2）初始種群生成的方式；3）構件評價函數，對其染色體的優劣進行評價；4）設計遺傳算子對父代染色體進行操作產生新的子代染色體；5）運算操作流程中參數的設置。

遺傳算法的優越性表現在[14,15]：

1）在不連續或非規則的適應函數中，搜索過程不容易陷于局部最優解，它仍然能最大概率的找出其整體的最優解。

2）由于它固有的并行性，遺傳算法非常適用于大規模的并行的計算機運行中。

本文以網絡數字印刷車間為背景，將遺傳算法用于解決印品生產調度問題，可以顯著提高排產計劃的智能性和準確性，能夠高效利用機器及物料資源，避免生產擁堵、交貨不及時等現象，實現快速的優化排產功能。

2 遺傳算法流程設計

遺傳算法運行流程為：1）隨機產生初始種群；2）計算染色體的適應值，將適應值高的染色體選出，傳遞給子代染色體；3）選擇染色體以交叉概率和變異概率進行染色體的交叉、變異操作，產生新的染色體；4）判斷迭代次數是否到達，若是，結束循環，否則跳轉操作2。其流程如圖1所示。

本文運行環境為Matlab 2008a。Matlab 2008是由美國MathWorks公司推出的一款數學運算軟件，本文在Matlab 2008系統中模擬車間調度。

3 印刷車間生產調度模型

1）車間調度問題描述

車間調度問題一般描述：有m臺不同的機器和n個不同的工件，每個工件包含一個由多道工序組成的工序集合，工件的工序順序是預先給定的。每個工件包含一個由多道工序組成的工序集合。車間調度數學模型如下[9]：

（1）機器集M={m1，m2，…，mm}，mj表示第j臺機器，j=1，2，…，m。

（2）零件集P={p1，p2，…，pn}，表示第i個零件，i=1，2，…，n。

（3）工序序列集OP={op1，op2，…，opn}，OPi={opi1，opi2，…，opik}表示零件pi的工序序列。

（4）對應可用機器的集合OPM={opi1,opi2，…，opik}，OPij={opij1，opij2，…，opijk}表示零件pi的工序j可以選擇的加工機器。

2）遺傳算子的操作設計

（1）個體編碼

本文染色體的編碼方式采用整數編碼，染色體體分為兩部分，前半段代表所有工件的所有工序，后半段代表所有工序的所用工序所使用的機器標號，即當工件總數為n，工件ni的加工工序共為mj時，此時染色體的長度為的整數串。例如一條染色體：

表示4個工件，每個工件2道加工工序，有三臺機器完成所有工序。上述染色體前八位表示工件加工的順序為工件4→工件1→工件3→工件2→工件2 →工件3→工件4→工件1。后八位表示該工序所用的機器編號，機器1→機器3→機器2→機器3→機器2→機器2→機器1→機器3。

（2）適應值函數

其中，time指目標函數為最長加工時間最短。

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

其中，pi（i）表示染色體i在每次選擇中被選中的概率。

（4）交叉算子

圖2 算法1

②交叉后產生子代S1'，S2'且產生的子代S1'，S2'為不可行性。以S1'為例，在前段基因中出現了工件2多了工序，工件1少了工序，則需要進行將多余的工序用缺失的工序代替操作。并且按照交叉前工序對應的機器來調整后半段的機器順序。

圖3 算法2

（5）變異算子

本文采用的變異操作為：在種群中隨機選取一個父代染色體，在前段中隨機選擇兩個位置pos1和pos2；將pos1和pos2位置上的工序所對應的機器進行對調。如pos1=3，pos2=7。

圖4 算法3

（6）遺傳算法中種群規模N=100，最大迭代次數為100，代溝G=0.9，交叉率Pm=0.8，變異率Pc=0.6。

4 模型測試

1）車間印品工藝及設備描述

本車間主要加工簡裝書籍，涉及6道工序，分別為：工序1印刷、工序2折頁、工序3配頁、工序4包封面、工序5裁切、工序6覆膜。車間有10臺機器，分別為：機器1方正P5200單色印刷機，機器2科美達C8000彩色印刷機、機器3折頁機、機器4配頁機、機器5 Horizon膠裝機、機器6hohner騎馬裝訂機、機器7為蝴蝶裝訂機、機器8、9為Horizon三面刀、機器0覆膜機。6種印品具體種類及所需工序如表1所示，表中，1表示有此工序，0表示無此工序，印品每道工序可選機器如表2所示，印品每道工序加工時間如表3所示，時間是以分鐘為單位。

表1 印品所需工序

表2 印品可選機器

表3 工序加工時間

2）印品調度情況

模型算法搜索過程如圖5所示。

圖5 算法搜索過程

最優排產方案對應的書籍加工排產甘特圖如圖6所示。

圖6 書籍排產甘特圖

3）結果分析

1）通過算法搜索過程可知，全部印品加工總時間

【】【】在第8次迭代時趨于最小值，并且設計算法收斂較快，運算效率較高。

2）通過排產甘特圖可知，全部完成6種印品加工耗時215min。圖6中同一色塊表示同一書籍的不同工序在不同機器的加工時間，例如：綠色模塊的106表示書籍1從102時刻開始在0號機器（覆膜機）上進行工序6（覆膜）的加工，到124時刻結束。

3）該模型調度方案可以直接應用于實際生產。由于本文構建的是靜態調度模型，但實際生產是一個復雜的動態過程，期間會出現一些非正常狀況，譬如機器故障、緊急插單等等，故還需要配合有經驗的工人師傅做些調整，使整個印品的排產方案更貼合實際情況。

5 結論

本文針對網絡數字印刷生產車間的特點，利用遺傳算法求解印品的計劃排產問題。采用多層編碼遺傳算法進行編程計算，通過MATLAB模擬驗證了遺傳算法用于求解調度問題所得到的效果。結果表明：遺傳算法可以有效用于印刷作業的排產調度，解決網絡狀態下訂單多、周期短帶來的排產和交貨問題，縮短了印刷加工周期，提高了機器的利用率，能夠在保證交貨期的前提下快速而又有條不紊的進行生產。由于該模型為靜態調度模型，在遇突發狀態時尚需要人工配合調整，后續研究還將會補充動態調度方案。

[1] 羅永強.中小企業ERP的實施與應用[D].廣州:廣東工業大學,2013.

[2] 邢潔芳.基于APS的印刷企業生產管理系統的設計與實現[D].南京:南京林業大學,2014.

[3] 梁亞敏.基于高級生產計劃與排程的作業車間調度優化模型研究[D].東北:東北林業大學,2014.

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

[5] 劉言東.遺傳算法在ERP生產系統的計劃與研究[D].鄭州:鄭州大學,2008

[6] 劉寧.基于APS優化ERP生產計劃的方法研究[D].長沙:長沙理工大學,2009.

[7] 林堅.基于遺傳算法的ERP生產計劃排單模型[J].福州大學學報,2002.

[8] 陳瑞雪.基于遺傳算法的ERP生產系統的優化研究[D].天津:天津工業大學,2008.

[9] 史峰,王輝,郁磊.智能算法[M].北京航空航天大學出版社,2007.

[10] Tamer F.Abdelmaguid,Ashraf O.Nassef,Badawia A.Kamal，and Mohamed F.Hassan.A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles[J].INT.J.PROD.RES.2004,

[11] 林治國.基于滾動窗口的集裝箱碼頭泊位動態調度優化研究[D].大連:大連海事大學,2010,06.

[12] 劉樹林.SZ印刷公司面向ERP應用的需求分析與流程優化研究[D].濟南:山東大學,2012.

[13] 肖華良.解析印刷企業中的ERP管理[J].媒體管理,2005,6:71-72.

[14] 王守友.國內外印刷企業ERP應用狀況對比[J].今日印刷,2007,12:7-8.

[15] 何彩霞,葛力.印刷企業的生產排程方式窺探[J].印刷技術,2013,6:1-3.

Optimization of scheduling of printing enterprises based on genetic algorithm

HAO Qi, ZHANG Xu-yong, XING Jie-fang

TH212；TH213.3

：A

1009-0134(2017)01-0064-04

2016-09-20

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

郝琪（1990 -），女，山西陽泉人，碩士研究生，研究方向為印刷與包裝工程。