基于遗传算法的印刷企业生产调度模型的构建

郝 琪，张绪勇，邢洁芳

（南京林业大学 江苏省制浆造纸科学与技术重点实验室，南京 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 -），女，山西阳泉人，硕士研究生，研究方向为印刷与包装工程。