基于窗口的印刷车间作业动态调度研究

郝 琪，邢洁芳

(南京林业大学 江苏省制浆造纸科学与技术重点实验室，南京 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