丁 雷 王爱民 宁汝新

北京理工大学,北京,100081

0 引言

卷包生产由卷接和包装两个步骤组成,由于卷接采用高速自动化的专用机组,为了与之配合,一般都通过刚性连接配套一台包装机,因此,可将卷接和包装视为一体化的核心生产机组。同时,卷包生产设备包括与卷包机组上的料口相连的振盘,以及与振盘相连的储丝柜等。由于储丝柜与振盘、振盘与卷包机组、机组与振盘之间具有复杂的关联约束,如不同振盘连接不同数量的储丝柜、一个振盘可以连接多个机组、一个机组可以连接多个振盘等,因此对卷包生产调度提出了复杂的资源动态优化组合分配的要求。

van Dam等[1]对卷包调度中的规则和约束进行了分析;谢五峰等[2]基于SIMATIC IT软件架构展开了卷包调度研究;卞新中[3]基于Rockwell Automation公司的MES产品,结合将军烟草集团实际实施了高级排产;周小莉[4]、苏建军[5]提出了基于初始机组分组和订单分组的卷包调度算法;陈庄等[6]将烟草生产抽象为连续物料流的连通网络模型,进而提出了综合制丝和卷包的调度策略;王萍等[7]采用面向对象的Rational工具对烟厂调度进行了建模研究。另外,昆明卷烟厂2004年引进和实施了Wonderware Factory Suite卷包高级排产,徐州卷烟厂2008年实施了德国的科德宝MES系统。综上所述,卷包调度已经得到了国内外的广泛关注,国内大多引进应用国外软件,实施效果和成本都不甚理想,而国内的研究大多停留在建模、策略方面,虽然提出了一些算法,但对于卷包调度的柔性约束考虑不足。

本文从卷包调度要求出发,以振盘、机组之间柔性连接关系和动态组合为约束,提出适合烟厂周计划作业安排的卷包调度流程及算法。

1 卷包作业调度原则与约束

1.1 卷包作业调度原则

卷包作业调度的核心在于如何将订单任务分配到各个机组资源上,其关键在于机台资源的组合分配,即如何合理地将机台资源进行组合以实现订单任务的合理安排。由于振盘资源有限,以及存在振盘与机台、机台与振盘之间的配置关联关系,因此调度的过程是综合订单任务、振盘资源以及在此基础上的机台资源组合分配的过程。在这个过程中,卷包调度需要遵循如下原则[8-10]：①订单优先连续生产原则。一般情况下,订单任务的生产不能终止,必须保证连续生产完成同一个订单,也即订单生产资源需要连续占用。②订单优先级原则。当要生产的多个订单任务计划的条件相同时,考虑产品机组优先级安排生产机组。③减少换牌生产原则。调度过程中,尽量减少换牌次数,以充分发挥高效卷包机组的生产能力。④订单牌号数量由多到少逐渐变化的原则。在周初进行调度排产时,应该采取尽量安排多种牌号的香烟并行生产,但在周末时,则可以合并资源针对某项任务进行连续流水生产。⑤并行展开的订单数量限制原则。对于烟厂而言,其能够并行展开的订单任务数是由振盘数量决定的。⑥储丝柜数量决定生产平顺的原则。对于储丝柜与机组生产能力匹配的问题,存在如下一些参考规则：3台储丝柜、2台卷接机可保证生产衔接顺畅,但3台储丝柜、4台卷接机则储丝柜的供应相对比较紧张,需要在调度过程中重点考虑。⑦机组资源组合优选配置原则。结合烟草企业的调度习惯,设置机组资源的优选组合配置,以保证最终的调度结果符合企业的习惯和硬件条件限制。⑧订单任务执行齐停原则。当某个订单有多个机组共同承担时,需要计算其齐停点,以保证机组-振盘-储丝柜的完整切换。

1.2 卷包调度约束

卷包调度的关键是对机组资源进行合理分配组织,在这个过程中需遵循如下一些约束：①生产任务的优先级约束。不同的订单任务具有不同的优先级,这决定了进行优先安排的前后顺序。②机组资源约束。卷包调度必须在企业有限的机组资源基础上展开。③振盘资源约束。振盘资源决定了最多可以并行展开的任务种类数。④振盘与机台之间的连接约束。每一台振盘最多只能连接n台机组,该振盘上的具体任务进一步限制了并行可选机组。⑤机组与振盘之间的连接约束。某个机组最多可以连接m个振盘,但在某个时刻只能连接一个振盘。⑥机组与香烟牌号之间的生产能力约束。某个机组生产某种牌号香烟的生产速度一般以箱/小时或支/分钟为单位。⑦不同香烟牌号生产中的换牌时间约束。⑧机组工作日历的约束。反映为综合机台的周保、轮保时间、企业工作日历等信息基础上的机组可用工作时间。⑨订单任务的可选生产机组约束。主要表明哪些机组可以生产哪些牌号的配置关系,同时说明各个机组与牌号之间的生产优先级关系。⑩生产任务的交货期约束。卷包调度必须满足生产任务的交货期约束,从而影响了各个订单任务的生产顺序。

2 卷包调度问题数学建模

2.1 卷包作业调度中的资源动态组合问题

卷包作业调度需要遵循多方面的原则和约束,其体现形式为,通过卷包机组动态组合实现对订单的合理安排,以保证交货期。以3个振盘、6个机组和5个任务为例的卷包作业调度方案形式如图1所示。

图1 卷包作业调度方案示意图

根据图1,卷包作业调度方案需要满足如下一些形式化要求：①各个订单都占用特定机组组合,并且具有共同的齐停点。②机组资源的组合具有动态性,如订单2在机组3上的开始时间与在机组1、机组2上的开始时间不同。③机组组合继承情况不同,如订单2在机组1、机组2、机组3上展开,虽然继承了订单1的机组1和机组2的组合,但根据自身的批量添加了机组3。④对于振盘切换情况,如开始生产时机组1、机组2与振盘1连接,机组3、机组 4与振盘2连接,机组5、机组6与振盘3连接;订单3结束时假定释放了振盘2,则订单2利用振盘2所连接的机组3开始生产;假定订单1结束时释放了振盘1,此时订单2就可以追加机组1和机组2开始生产,可以切换到振盘2,也可以使用振盘1,表明在任务执行过程中振盘与机组具有灵活的切换情况。

2.2 卷包作业调度目标函数

卷包作业调度的核心目标是,在充分利用机组资源的情况下保证订单的交货期,以延期订单数量最少作为目标函数。

首先定义调度过程中采用的量符号：W={w1,w2,…,wn}表示生产订单集合 ;Wni、Ai、Di、分别表示第 i个订单的加工数量、下达日期、交货期、计划开始时间、计划完工时间、实际开始时间和实际完成时间;F={}为振盘集合;P={P1,}为卷包机组集合;B=Bb}为香烟牌号集合;SW =sw1,n;sw2,1,sw2,2,…,sw2,n;……;swp,1,swp,2,}表示分配到机组上的子订单,其中,sw i,j表示机组Pi上加工的第 j个子订单;C={C1,1,C1,2,…,C1,p;C2,1,C2,2,…,C2,p;……;Cb,1,}表示生产能力集合,其中Ci,j表示牌号Bi在卷包机组Pj上的加工能力;N={N1,1,…,N f,p}表示振盘与卷包机组的连接关系集合,如果振盘i与卷包机组j连接则Ni,j=1,否则Ni,j=}表示振盘与卷包机组的可连接关系集合,如果振盘i与卷包机组j可以连接则CN i,j=1,否则CN i,j=0。

3 卷包作业调度技术方案

3.1 卷包作业调度技术思路

目前,国内关于卷包作业调度的基本思想[4-5]是,通过能力评估首先划分机组分组及订单分组,然后根据订单的交货期在机组上进行排序而形成调度方案。这种方法在订单数量较少、订单可用机组约束关系简单的情况下有其适应性,但算法不够灵活,无法适应动态的机组组合,算法能否保证交货期值得进一步商榷。因此,本文提出一种基于首批订单的两阶段启发式调度思想：①根据振盘的数量,选取第一批订单,并按照优先级进行排序,根据优选机组组合配置进行安排;②针对剩余的每一个订单进行排序,采取启发式安排的思路,对于同样的牌号尽量优先考虑之前已安排订单的机组组合方案,并根据实际情况调整组合方案。

这种两阶段处理的技术思路有效地减少了换牌次数,并通过振盘对并行生产订单的数量进行了有效控制,支持了机组资源的动态组合,使得所形成的算法具有广泛的适应性。

3.2 卷包作业调度算法流程

接收到订单集合W后,根据首批订单确定初始机组分组,后续订单在此基础上进行调度,卷包作业流程如图2所示。

图2 卷包作业调度流程图

卷包作业调度流程步骤如下：①如果订单数n小于振盘数f,则以全部订单作为首批订单,否则在订单筛选规则库的协助下筛选首批订单,首批订单的数量与振盘数量相同;②根据首批订单对振盘和卷包机进行分组;③利用分组后的机组在调度规则库的协助下对首批订单进行调度;④如果存在未调度订单则转步骤 ⑤,否则转步骤⑨;⑤通过订单筛选,选择出唯一一个订单准备进行调度;⑥如果当前的分组方式能满足选择出的订单的要求则转步骤 ⑧,否则转步骤 ⑦;⑦针对订单的要求调整振盘和卷包机分组;⑧对订单进行调度,转步骤 ④;⑨生成作业计划,结束调度。

4 关键技术

4.1 卷包作业调度数据结构

由于采用卷包机组组合生产的模式,一个订单可以在多台卷包机组上不同时间段内完成订单的生产加工,因此,如果采用传统的数据结构(即在订单信息中直接附加计划开始加工时间、计划完成加工时间以及加工机组等信息),则无法将调度结果准确无误地传达给操作人员,必须根据卷包调度的特点创建一种新型数据结构以对订单和生产计划进行表述。

由于调度系统接收到的订单与下达给卷包机组的订单在数据的结构及内容层次上差别较大,因此在新的数据结构中采用分层数据关联的形式进行表述：一是接收的原始订单;二是下达到机组的生产订单。一个接收到的原始订单可以被拆分成一个或者多个生产订单。原始订单记录用于数据的输入,记录订单的所属牌号、下达日期、交货期等订单基本信息;生产订单用于输出作业计划到生产机组,记录生产订单所属的父订单、计划开始时间、计划结束时间和计划加工机组等信息。原始订单负责数据输入,生产订单负责数据输出,两者之间通过订单的唯一标识 ——订单编号联系在一起,形成一个独立而又统一的数据结构,共同完成生产调度任务。

4.2 卷包作业调度规则实现机制

在调度过程中只能逐个订单地完成调度,因此必须通过订单筛选规则选出最符合条件的订单。在选择出订单后必须选择机组组合对该订单进行加工。

图3 复合筛选规则实现过程

然而,在调度中单一的调度规则往往无法得到想要的结果,因此本文提出基于一种逐层筛选调度规则的方法,如图3所示。首先,接收到待筛选的集合O0(O0为设备集合或工序集合),当集合的元素个数Size(O0)大于1时启动筛选过程;然后利用规则i(i=1,2,…,g)对集合Oi-1进行筛选,当i=g或Size(Oi)=1时跳出循环;最后,如果Size(Og)＞1则说明集合中的元素对于当前规则是相同的,因此采用随机选择的方式选择一个元素。通过此种方式筛选出的元素综合考虑了各种规则,比单一考虑一种规则的方式更可靠。

4.3 卷包制造资源动态组合方法

每个振盘存在4～5个可连接的卷包机组,每个卷包机组同样存在多个可连接振盘;在调度排产中,一个振盘可以连接1～4台卷包机组,一台卷包机组只能与一个特定的振盘连接。图4所示的振盘与卷包机组之间的连接约束关系是某烟厂的真实情况,此种约束为制造资源的动态组合提供了空间。

图4 振盘-卷包机组可连接约束关系

图4 所示的可连接关系存在多种可能的分组方式,为了规范分组并使分组后的机组对实际生产具有可行性,以及最大程度地利用机组的生产能力,建立分组规范式1和规范式2。规范式1表示每一个卷包机组最多与一台振盘连接,只有特种机组在没有订单时取值为0,以此保证没有空闲的卷包机组,使生产线发挥最大的生产能力;规范式2表示每个振盘可以连接1～4个卷包机组,保证生产线柔性和分组的可用性。

规范式1为

规范式2为

由于振盘-卷包机组的连接关系经常发生变化,需要记录发生变化的时间及相应的卷包机组,定义CH={CH 1,CH 2,…,CH p},其中,CH i表示卷包机组i最后一次发生分组变化的时间。机组分组的变化可能造成机组上出现生产空隙,造成机组在末段时间段内闲置,降低机组的利用效率,为此必须采取连续生产保障机制,提高机组的利用率。

设正在使用的振盘为当前振盘,寻找可连接但尚未连接到当前振盘的卷包机组,查询这些卷包机组上已经存在的子订单之间是否存在空闲时间段,如果存在则采用该订单填补机组上的空闲时间段,然后根据生产数量对原计划结束时间进行调整。

4.4 基于工作日历的机组齐停算法

一个订单采用多个卷包机组进行生产,同一机组内的多个卷包机组同时释放,但由于卷包机组组合是动态的,故造成同一组合内的卷包机组不能同时释放,而且不同卷包机组的生产能力由于轮保和班保(班保指每个班次在指定的时间段内停止生产,对机组进行保养;轮保指机组在指定的班次(一般一周一次)停止生产,进行较为全面的保养)造成的波动也需要充分考虑。采用机组搜索的方式对生产能力进行计算。确定下达订单所属牌号为Bb1,所要使用的机组集合为{Pk},遍历{Pk}内的卷包机组,获取集合内每一个卷包机组上已排产订单的可使用时间max(Ek,CH k)作为每个卷包机组的计划开始时间PSk,获取其中最晚时间E last;计算[PSk,E last)时间段内加工能力之和∑[(E last-PSk)Cb1,k],从加工数量中核减该时间段内的生产能力;利用核减后的生产数量,以E last为开始加工时间计算计划完成时间。

为了保证卷包机组在良好状态下运行,在生产中为卷包机组安排轮保和班保,建立一个保养时间集合

其中,Rsti,j表示设备P i上第j个保养时间段的开始时间,Esti,j表示设备P i上第j个保养时间段的结束时间,下标mk表示设备P k上保养时间的总数量。

设订单使用的卷包机组为UPI={u1,u2,…,up},如是订单使用机组Pi则ui取值为1,否则为0。设Rs={r1,r2,…,rp}中的元素ri表示卷包机组Pi是否处于维护状态,是则r i=1,否则r i=0;St表示订单在卷包机组上的计划开始时间;生产牌号下标为b。机组在计算生产能力时必须考虑保养的影响,处理步骤如下：

(1)遍历全部选用的卷包机组,找到最早开始/结束的保养开始时间LS。图5中,t1～t8均为St取不同值时得到的 LS,当 St=t3时LS=t4。

图5 机组工作时间示意图

(2)计算所有卷包机组在开始时间至最早开始保养时间之间的加工烟支的数量 TW,计算公式如下：

当St=t3,使用机组1～机组4进行生产时,计算结果为(t4-t3)(Cb,1+Cb,3+Cb,4)。

(3)如果生产能力大于剩余订单,转步骤(4);否则转步骤(5)。

(5)根据St到LS时间段的生产能力计算生产剩余数量,公式如下：

(6)转步骤(1)。

(7)计算结束。

5 应用验证

在Windows XP平台上采用Visual C++开发了卷包作业调度软件系统,该系统已结合某烟厂的卷包生产线展开了工程化应用,实现了精细化的卷包作业调度。振盘、储丝柜、机组以及三者之间的连接关系见图4,表1所示为输入订单,表2为订单生产的优选机组配置约束表,在2009年2月1日至2月8日间,1日至7日为工作日,8日休息,设定牌号切换时间统一为40min、生产能力为6000支/min。

表1 输入订单表

表2 订单生产的优选机组配置约束表

订单08佳品醇采用机组GD01～GD07进行生产,由于这7个机组此前已经安排了其他订单,因此不能在同一时间进行生产。在安排生产时先根据最晚开始时间核减生产数量然后计算订单齐停时间,结果为：机组 GD4、GD5、GD6 上的计划开始时间为2009-02-0419：37：00,机组 GD1、GD2、GD3、GD7上的计划开始时间为2009-02-05 01：10：00,而在全部机组上的计划结束时间统一为2009-02-07 15：43：00。为了保证订单03世纪佳品生产的连续性,机组FK02在 2009-02-04 18：54 ：00 至 2009-02-05 10：03：00间与机组 FK03和FK04在同一机组内生产 订 单 03,在 2009-02-07 01：26：00 至2009-02-0717：29 ：00之间为了保证订单 03 能够按时交货而与机组FK03和FK04在同一机组组内生产订单03,而其他时间FK02则与FK01形成一个机组组合进行生产。

6 结语

卷包调度是烟草企业有序、协调、可控和高效生产的核心技术。针对当前烟草行业深入整合的需求和解决核心算法受制于国外软件的问题,提出了基于制造资源动态组合的卷包作业调度技术。分析并建立了卷包作业排产的原则和约束,提出了支持卷包作业机组动态组合优化分配的、基于首批订单的两阶段启发式调度思想,建立了下达订单与生产订单关联的数据结构,完成了订单和机组调度规则的多层次复合筛选方法的构建,提出了基于规范式的卷包机组动态组合方法以及基于工作日历的机组齐停算法,开发了卷包作业调度软件系统,实现了基于制造资源动态组合的卷包优化调度。

[1] van Dam P,Gaalman G J C,Sierksma G.Designing Scheduling Systems for Packaging in Process Industries：a Tobacco Company Case[J].Int.J.Production Economics,1998,19(56/57)：649-659.

[2] 谢五峰,鄂明成.基于西门子平台的卷包排产子系统的研究[J].中国制造业信息化,2007,36(1)：5-7.[3] 卞新中.将军集团M ES系统解决方案与研究[D].济南：山东大学,2005.

[4] 周小莉.基于MES的生产动态调度子系统的研究与应用[D].北京：中国地质大学,2007.

[5] 苏建军.混合流程型生产调度策略的应用研究[D].北京：中国地质大学,2006.

[6] 陈庄,刘永梅,崔贯勋,等.一种面向卷烟生产线的优化调度策略[J].计算机集成制造系统-CIMS,2004,10(7)：801-807.

[7] 王萍,蔡雨阳,黄丽华.面向对象的建模方法-上海卷烟厂计调系统分析与设计[J].中国管理科学,2000,8(11)：459-466.

[8] 程贞敏.平行机调度问题研究的若干结果[D].北京：北京师范大学,2008.

[9] McBride RD,O'Leary D E.The Use of Mathematieal Programming with Artifieial Intelligence and Expert Systems[J].European Journal of Operational Researeh,1993,70：1-15.

[10] 郑松.啤酒生产过程优化和综合自动化若干关键技术研究[D].杭州：浙江大学,2008.