郝 琪，張緒勇，邢潔芳

（南京林業(yè)大學(xué) 江蘇省制漿造紙科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 210037）

基于遺傳算法的印刷企業(yè)生產(chǎn)調(diào)度模型的構(gòu)建

郝 琪，張緒勇，邢潔芳

（南京林業(yè)大學(xué) 江蘇省制漿造紙科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 210037）

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

ERP；遺傳算法；印刷生產(chǎn)；調(diào)度模型

0 引言

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

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

1 可行性分析

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

遺傳算法的優(yōu)越性表現(xiàn)在[14,15]：

1）在不連續(xù)或非規(guī)則的適應(yīng)函數(shù)中，搜索過程不容易陷于局部最優(yōu)解，它仍然能最大概率的找出其整體的最優(yōu)解。

2）由于它固有的并行性，遺傳算法非常適用于大規(guī)模的并行的計(jì)算機(jī)運(yùn)行中。

本文以網(wǎng)絡(luò)數(shù)字印刷車間為背景，將遺傳算法用于解決印品生產(chǎn)調(diào)度問題，可以顯著提高排產(chǎn)計(jì)劃的智能性和準(zhǔn)確性，能夠高效利用機(jī)器及物料資源，避免生產(chǎn)擁堵、交貨不及時(shí)等現(xiàn)象，實(shí)現(xiàn)快速的優(yōu)化排產(chǎn)功能。

2 遺傳算法流程設(shè)計(jì)

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

本文運(yùn)行環(huán)境為Matlab 2008a。Matlab 2008是由美國(guó)MathWorks公司推出的一款數(shù)學(xué)運(yùn)算軟件，本文在Matlab 2008系統(tǒng)中模擬車間調(diào)度。

3 印刷車間生產(chǎn)調(diào)度模型

1）車間調(diào)度問題描述

車間調(diào)度問題一般描述：有m臺(tái)不同的機(jī)器和n個(gè)不同的工件，每個(gè)工件包含一個(gè)由多道工序組成的工序集合，工件的工序順序是預(yù)先給定的。每個(gè)工件包含一個(gè)由多道工序組成的工序集合。車間調(diào)度數(shù)學(xué)模型如下[9]：

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

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

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

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

2）遺傳算子的操作設(shè)計(jì)

（1）個(gè)體編碼

本文染色體的編碼方式采用整數(shù)編碼，染色體體分為兩部分，前半段代表所有工件的所有工序，后半段代表所有工序的所用工序所使用的機(jī)器標(biāo)號(hào)，即當(dāng)工件總數(shù)為n，工件ni的加工工序共為mj時(shí)，此時(shí)染色體的長(zhǎng)度為的整數(shù)串。例如一條染色體：

表示4個(gè)工件，每個(gè)工件2道加工工序，有三臺(tái)機(jī)器完成所有工序。上述染色體前八位表示工件加工的順序?yàn)楣ぜ?→工件1→工件3→工件2→工件2 →工件3→工件4→工件1。后八位表示該工序所用的機(jī)器編號(hào)，機(jī)器1→機(jī)器3→機(jī)器2→機(jī)器3→機(jī)器2→機(jī)器2→機(jī)器1→機(jī)器3。

（2）適應(yīng)值函數(shù)

其中，time指目標(biāo)函數(shù)為最長(zhǎng)加工時(shí)間最短。

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

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

（4）交叉算子

圖2 算法1

②交叉后產(chǎn)生子代S1'，S2'且產(chǎn)生的子代S1'，S2'為不可行性。以S1'為例，在前段基因中出現(xiàn)了工件2多了工序，工件1少了工序，則需要進(jìn)行將多余的工序用缺失的工序代替操作。并且按照交叉前工序?qū)?yīng)的機(jī)器來調(diào)整后半段的機(jī)器順序。

圖3 算法2

（5）變異算子

本文采用的變異操作為：在種群中隨機(jī)選取一個(gè)父代染色體，在前段中隨機(jī)選擇兩個(gè)位置pos1和pos2；將pos1和pos2位置上的工序所對(duì)應(yīng)的機(jī)器進(jìn)行對(duì)調(diào)。如pos1=3，pos2=7。

圖4 算法3

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

4 模型測(cè)試

1）車間印品工藝及設(shè)備描述

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

表1 印品所需工序

表2 印品可選機(jī)器

表3 工序加工時(shí)間

2）印品調(diào)度情況

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

圖5 算法搜索過程

最優(yōu)排產(chǎn)方案對(duì)應(yīng)的書籍加工排產(chǎn)甘特圖如圖6所示。

圖6 書籍排產(chǎn)甘特圖

3）結(jié)果分析

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

【】【】在第8次迭代時(shí)趨于最小值，并且設(shè)計(jì)算法收斂較快，運(yùn)算效率較高。

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

3）該模型調(diào)度方案可以直接應(yīng)用于實(shí)際生產(chǎn)。由于本文構(gòu)建的是靜態(tài)調(diào)度模型，但實(shí)際生產(chǎn)是一個(gè)復(fù)雜的動(dòng)態(tài)過程，期間會(huì)出現(xiàn)一些非正常狀況，譬如機(jī)器故障、緊急插單等等，故還需要配合有經(jīng)驗(yàn)的工人師傅做些調(diào)整，使整個(gè)印品的排產(chǎn)方案更貼合實(shí)際情況。

5 結(jié)論

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

[1] 羅永強(qiáng).中小企業(yè)ERP的實(shí)施與應(yīng)用[D].廣州:廣東工業(yè)大學(xué),2013.

[2] 邢潔芳.基于APS的印刷企業(yè)生產(chǎn)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].南京:南京林業(yè)大學(xué),2014.

[3] 梁亞敏.基于高級(jí)生產(chǎn)計(jì)劃與排程的作業(yè)車間調(diào)度優(yōu)化模型研究[D].東北:東北林業(yè)大學(xué),2014.

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

[5] 劉言東.遺傳算法在ERP生產(chǎn)系統(tǒng)的計(jì)劃與研究[D].鄭州:鄭州大學(xué),2008

[6] 劉寧.基于APS優(yōu)化ERP生產(chǎn)計(jì)劃的方法研究[D].長(zhǎng)沙:長(zhǎng)沙理工大學(xué),2009.

[7] 林堅(jiān).基于遺傳算法的ERP生產(chǎn)計(jì)劃排單模型[J].福州大學(xué)學(xué)報(bào),2002.

[8] 陳瑞雪.基于遺傳算法的ERP生產(chǎn)系統(tǒng)的優(yōu)化研究[D].天津:天津工業(yè)大學(xué),2008.

[9] 史峰,王輝,郁磊.智能算法[M].北京航空航天大學(xué)出版社,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] 林治國(guó).基于滾動(dòng)窗口的集裝箱碼頭泊位動(dòng)態(tài)調(diào)度優(yōu)化研究[D].大連:大連海事大學(xué),2010,06.

[12] 劉樹林.SZ印刷公司面向ERP應(yīng)用的需求分析與流程優(yōu)化研究[D].濟(jì)南:山東大學(xué),2012.

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

[14] 王守友.國(guó)內(nèi)外印刷企業(yè)ERP應(yīng)用狀況對(duì)比[J].今日印刷,2007,12:7-8.

[15] 何彩霞,葛力.印刷企業(yè)的生產(chǎn)排程方式窺探[J].印刷技術(shù),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

國(guó)家級(jí)大學(xué)生實(shí)踐創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目（201410298044Z）；江蘇省產(chǎn)學(xué)研前瞻性聯(lián)合研究項(xiàng)目（BY2016006-01）

郝琪（1990 -），女，山西陽(yáng)泉人，碩士研究生，研究方向?yàn)橛∷⑴c包裝工程。