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

郝 琪，張緒勇，邢潔芳

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

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

郝 琪，張緒勇，邢潔芳

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

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

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

0 引言

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

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

1 可行性分析

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

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

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

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

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

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

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

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

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

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

車間調(diào)度問題一般描述：有m臺不同的機器和n個不同的工件，每個工件包含一個由多道工序組成的工序集合，工件的工序順序是預(yù)先給定的。每個工件包含一個由多道工序組成的工序集合。車間調(diào)度數(shù)學模型如下[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）對應(yīng)可用機器的集合OPM={opi1,opi2，…，opik}，OPij={opij1，opij2，…，opijk}表示零件pi的工序j可以選擇的加工機器。

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

（1）個體編碼

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

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

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

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

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

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

（4）交叉算子

圖2 算法1

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

圖3 算法2

（5）變異算子

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

圖4 算法3

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

4 模型測試

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

本車間主要加工簡裝書籍，涉及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）印品調(diào)度情況

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

圖5 算法搜索過程

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

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

3）結(jié)果分析

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

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

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

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

5 結(jié)論

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

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

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

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

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

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

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

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

[8] 陳瑞雪.基于遺傳算法的ERP生產(chǎn)系統(tǒng)的優(yōu)化研究[D].天津:天津工業(yè)大學,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] 林治國.基于滾動窗口的集裝箱碼頭泊位動態(tài)調(diào)度優(yōu)化研究[D].大連:大連海事大學,2010,06.

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

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

[14] 王守友.國內(nèi)外印刷企業(yè)ERP應(yīng)用狀況對比[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

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

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