一种提高辐照箱利用率的生产调度算法*

马玲叶 陈金广

（1.西安工程大学计算机科学学院 西安 710048）（2.柯桥区西纺纺织产业创新研究院 绍兴 312030）

1 引言

辐照加工在食品的灭菌保存［1］，农业突变育种等方面得到较为广泛的应用［2］。辐照加工企业是特殊的加工类企业，其辐照源是由放射性元素如γ［3～5］构成，放射强度随时间而不断衰减且价格昂贵。目前已有一大批专业化辐照加工企业诞生［6～8］，合理的生产调度尤为重要。

1986 年Ikura 和Gimple［9］首 次 提 出 批 调 度 问题，主要针对尺寸相同的工件，并假设各个批的加工时间是固定的，与批大小无关；1994年Uzsoy［10］首先提出差异工件批调度（NBM）问题，证明了NBM问题是NP难问题。吴愁［11］在单机批调度问题中考虑了耗能情况，使调度更加合理。Kashan［12］等利用遗传算法对最小化加工时间和最小化延迟时间这两个目标同时进行优化，实现多目标优化。杨栋［13］考虑了遗传算法在包含差异工件的并行批处理机调度中的应用问题。李国臣等［14］和张震等［15］分别考虑了能耗约束和模具约束并行批调度问题。辐照企业的生产调度属于差异工件单机批调度问题（NSBM），是NP-hard［16］问题。对于辐照企业生产调度问题，张晓静［17］等设计基于工件序列编码的混合遗传算法，缩短生产周期。王众［18］用遗传算法对订单进行优化排序，缩短订单间的空闲时间。

一段时间内辐照企业加工能力固定不变，若订单到达过多，部分订单不能按期完成，造成经济损失。目前的辐照企业生产调度算法是以最小化最大完成时间为目标，处理该问题时，会出现订单排产不合理，造成企业经济损失。本文提出企业负载能力［19］思想，根据企业的负载能力将排产方式分为两种，使该问题得到处理。

2 辐照加工技术

加工技术描述如下：假设某企业有一个辐照源，一个辐照行程内（辐照箱围绕放射源行进一圈称为一个辐照行程）共有m 个辐照箱同时接受辐照。产品到达时，由于γ射线穿透能力强，工人直接按原包装装入辐照箱，辐照箱中产品的堆积厚度不能超过客户要求或产品本身要求；完成装箱后工人利用辐照箱进场的时间间隔将辐照箱放到加工链上，加工链围绕着辐照源匀速前进，并以一定的方式翻转移位；辐照箱在，产品在完成辐照后，工人利用出场时间间隔完成卸货，进、出场的时间间隔相同。

3 问题描述

本文的目标是使剩余辐照箱最少，公式如下式：

其中m 为总辐照箱数，Bi为订单i 时所需辐照箱数。

假设J1,J2,…,JN是订单集合S 中的订单，每个订单都有严格的到达、交付时间，订单i到达与交付之间的时间段为订单有效期Ti；订单批量到达后，按规则拆分：1）一个订单只包含一种产品，不同产品拆分为多个订单；2）产品所需辐照箱数大于m，拆分订单。

辐照加工时需满足以下几点约束：

1）不同订单的产品可以同时接受辐照，相互之间没有干扰；

2）一个已排产订单对应一个批P，批中有m个辐照箱，所有批组成一个批集合；

3）每个工件不能拆分只属于一个批，批次进入辐照场就不能中断；

4）每个订单都需在Ti内完成加工；

5）装箱时，直到产品全部装完或辐照箱已满，再顺序装载下一个辐照箱。

相关变量描述如下：

企业负载能力U：企业一段时间内所能处理的订单量，值为各订单加工时间与Ti的比值之和。

批中占用箱数Bi：值为产品总件数除以辐照箱可容纳的产品件数。一个批中包含多个订单时，Bi为各订单占用箱数之和。

辐照剂量κi：由客户要求给出，在排产前就已确定。

辐照圈数：由κi决定，值为κi除以辐照一圈最低吸收辐照剂量G。

混合优先级proi：计算方法参考文献［20］，如下式：

proi=hi+pri+impi+profi+resi

其中hi表示紧迫度，由订单有效期决定，有效期越短值越大。pri表示订单优先级，分为紧急、急、正常三种级别。impi表示客户重要程度，分为非常重要、重要、普通三种程度。profi表示订单利润，由产品辐照圈数和有效期决定，分为高、中、低三个等级。resi表示设备资源利用程度，由Bi决定。

工件加工时间Ci：由基本加工时间和辐照箱进场时间决定。基本加工时间为κi与G之比乘以辐照一圈所需的时间D；进场时间是Bi的第一个辐照箱进场至最后一个辐照箱进场的时间，辐照箱之间的时间间隔为V。计算公式为

最优调度集Q 为S 中混合优先级高且U未过载的订单；非最优调度集I为S中的剩余订单。

4 合理排产订单、提高辐照箱利用率的排产算法

初始情况为企业还没有接到订单，即S 为空。当订单批量到达时，加入S并排产。根据U是否过载，将排产方式分为两种分别予以讨论。

情况一：企业负载能力未过载（U≤1）

当U≤1 即加工S 中的订单在企业加工能力范围之内时，按照Ti排序订单。由于排产后每个订单与确定批对应，批的辐照圈数以及Bi均可确定，排产前先判断批集合中有无合适的批，若有则排产到合适批中，否则排产到新批中。

情况二：企业负载能力过载（U＞1）

当U＞1 即加工S 中的订单超出企业加工能力范围时，先确定S 中各订单的proi，根据proi降序排序订单，挑选Q 并排产，排产后每个订单与确定批对应。然后在I中选择合适的订单排产到对应批中。

对于企业加工能力过载的情况，算法的主要思想是先排产proi高的订单，再依据批集合中各批的辐照圈数以及批中空闲辐照箱数，在I 中挑选出合适的订单进行排产。如此可优先排产价值大的订单，使其按期完成，并能提高辐照箱利用率，尽可能多地排产未排产订单。

合理排产订单、提高辐照箱利用率的排产算法实现步骤如下。

输入：订单集合S，辐照空箱数m。

输出：订单排产顺序以及所对应的批。

步骤1：对S 中的所有订单是否超出企业加工能力进行判断，若U≤1，转至步骤2；若U＞1，转至步骤3。

步骤2：对S中的订单按Ti升序排序并排产，排产订单时先判断能否在批集合中找到与该订单所需辐照圈数相同的批，若找到则判断是否拆分订单，在将符合条件的订单安排到对应批中，并更新批的剩余辐照箱数；若没找到直接排产该订单，该订单对应一个新批，记录新批的辐照圈数和剩余辐照箱数，并加入批集合中。

步骤3：计算各订单的proi并降序排序订单，挑选订单组成Q。排产Q，记录排产后各订单所对应批的剩余辐照箱数和辐照圈数，按辐照圈数升序排序各批。再顺序挑选I 中的订单，若找到符合条件的批则判断是否拆分订单，若没找到则处理下一个订单。

判断是否拆分订单依据：订单所需辐照箱数小于或等于批中剩余辐照箱数，不拆分订单；否则将订单按照批中剩余辐照箱所能容纳的产品大小拆分并排产到应批中，另一个订单保存到S 中；更新相应的值。算法流程如图1 所示，挑选Q 流程如图2所示。

图1 算法流程图

图2 最优调度集流程图

5 算例与结果分析

假设某辐照加工企业只有一个辐照源，辐照箱m=6，辐照一圈所需时长D=30 min，空箱辐照一圈最低吸收剂量G=0.2 kGy，相邻两辐照箱的发车间隔V=5 min。

5.1 算例1

该算例考虑U≤1 情况下的调度，假设一段时间内企业订单集合中有5 个订单，其参数如表1 所示。

表1 低负载情况下的产品加工参数

该辐照公司总负载为U= 80/600 + 120/600 +70/600+80/600+70/600=420/600 ＜1，企业负载能力未过载，按Ti对订单进行升序排序，排序后的订单顺序为1、3、2、4、5，此时批集合为空。排产订单1，订单1 对应批1，占用两个辐照箱，剩余4 个辐照箱，将批1 加入批集合中；排产订单3，由于批1 与其辐照圈数一致，且订单3 所需辐照箱数小于批1中剩余辐照箱数，故将订单3 排产到批1，此时批1中占用3 个辐照箱，剩余3 个辐照箱；排产订单2，由于批集合中没有符合条件的批，因此订单2 对应批2，批2中占用6个辐照箱，剩余0个辐照箱，将批2加入批集合中；排产订单4时，由于批集合中没有符合条件的批，因此订单4 对应批3，批3 中占用4个辐照箱，剩余两个辐照箱，将批3 加入批集合中；排产订单5，批3 与其辐照圈数一致，且订单5 所需辐照箱数等于批3 中剩余辐照箱数，故将订单5 排产到批3，此时批3 中占用6 个辐照箱，剩余0 个辐照箱，此时5 个订单均可按期完成。各批的辐照箱使用情况如图3（a）所示。与每个订单对应一个批的排产方式相比，辐照箱利用率得到提升，各批的辐照箱使用情况如图3（b）所示。

图3 各批辐照箱使用情况对比

5.2 算例2

该算例考虑U＞1 情况下的调度，假设企业一段时间内订单集合中有5 个订单，其参数如表2 所示。

表2 过载情况下的产品加工参数

该辐照公司总负载为U = 120/360 + 135/360+140/360+150/360+70/360 ＞1，企业负载能力过载。计算各订单proi，proi影响因素如表3所示。

表3 订单混合优先级影响因素表

按proi降序排序各订单，顺序为1、5、2、4、3，挑选Q。由于加工订单1、订单5、订单2时，U=120/360 + 70/360 + 135/360 ＜1，企业负载能力未过载，故可作为Q。排产Q，订单1 对应批1，占用两个辐照箱，剩余4 个辐照箱；订单5 对应批2，占用两个辐照箱，剩余4个辐照箱；订单2对应批3，占用3个辐照箱，剩余3 个辐照箱，此时批1、批2、批3 的辐照箱利用率分别为33%、33%、50%。排产I，在批集合中搜索与订单4 辐照圈数一样的批，判断该批中剩余辐照箱数是否满足订单4 所需辐照箱数，经分析计算将订单4 安排到批1 中，同理，将订单3 安排到批2 中。此时批1 中的占用辐照箱数为6，剩余0个，利用率为100%，提升了67%；批2 中的占用辐照箱数为4，剩余2 个，利用率为66%，提升了33%，此时五个订单均能按期完成。批中辐照箱的使用情况如图4中（a）所示。

若以最小化最大完成时间为目标，按照所选订单在企业的加工能力范围之内和最大完成时间最小这两条规定，选择订单1 和订单4 排产加工。排产完成后，订单1对应批1，占用辐照箱数为2，剩余辐照箱数为4，利用率为33%；订单4对应批2，占用辐照箱数为4，剩余辐照箱数为2，利用率为66%，此时两个订单可按期完成。批中辐照箱的使用情况如图4中（b）所示。

图4 不同优化目标下批中辐照箱使用对比图

经对比本文算法不仅可以合理安排订单排产顺序，提高企业接单率，还能提高辐照箱利用率，提高企业利润。

6 结语

本文提出一种合理安排订单，提高辐照箱利用率的生产调度算法。该算法根据企业加工能力是否过载分为两种情况：企业加工能力过载和企业加工能力未过载。企业加工能力未过载时，按照订单有效期对订单集合排序，排产排序后的订单集合时，先判断批集合中有无合适的批，若有则安排到对应批中加工，若没有则安排到新批中；企业加工能力过载时，按照混合优先级对订单排序，挑选混合优先级高且符合企业负载能力未过载的订单作为最优调度集，优先排产最优调度集中订单，排产订单与批对应，记录各批的辐照圈数与剩余辐照箱数，挑选合适的未排产订单进行排产。算例结果表明所提算法不仅能够合理安排订单排产顺序，使混合优先级高的订单优先排产，排产尽可能多的订单，还能提高辐照箱利用率，增大企业利润。下一步将研究如何提高每个辐照箱空间利用率，使企业资源充分利用。