贵金属材料加工的排产调度算法

□ 马峰超 □ 任仕伟 □ 陈 进 □ 陈 宇

江南大学机械工程学院 江苏无锡 214122

1 研究背景

与一般离散型加工过程相比，贵金属材料加工还有熔炼、机加工、初切、退火等工序，加工过程复杂。贵金属材料加工过程通常如下：首先将订单任务材料相同的集中在一起熔炼，需要制订炉次计划；熔炼之后，根据不同订单任务的工艺路线进行加工，包括机加工、初切、退火、分剪、轧制、冲压、检验和包装等，需要制订加工计划。由于缺乏系统的理论和排产方法作为指导，计划员常常依靠经验制订炉次计划和加工计划，因此产生了一系列问题：①炉次计划制订不合理，熔炼能力没有充分利用，资源过度浪费；②分剪计划不合理，材料过度损耗；③生产计划不合理，制造过程混乱，延误交货期；④设备利用率低。

为解决上述问题，一般有效的方法是对生产调度方法进行优化，涉及到的算法主要有遗传算法、进化算法、粒子群算法等［1-7］。但由于贵金属材料加工工艺具有特殊性，生产过程复杂，常规的生产调度方法已无法满足实际需求。在解决炉次计划的相关问题时，唐立新等［8］为解决炼钢连铸计划与调度中的炉次计划问题，构建了一个最优炉次计划的混合整数规划数学模型；张健欣等［9］建立了融合多目标的数学模型，用于解决炼钢连铸热轧一体化生产的炉次计划问题；王闯等［10］采用改进后的单亲遗传算法解决炉次计划问题，通过对比分析，验证了算法的有效性；马天牧等［11］提出了将变邻域搜索算法作为迭代局部搜索算法中局部搜索的混合算法；薛云灿等［12］针对炉次数未知的炼钢连铸一体化生产问题，提出了组炉模型，并将其作为伪旅行商问题来处理，采用离散粒子群优化算法求解。可见，炉次计划在炼钢和热处理过程中行之有效，且取得了不少研究成果，但是针对贵金属熔炼炉次计划的研究仍比较少。

针对贵金属材料加工过程，笔者研究的排产方法集成了炉次计划和加工计划，形成了完整的排产调度算法［13-14］。具体实施过程为：结合工艺路线与多种参数的实际意义，基于启发式算法基本原理与极大极小代数法思想，建立一种融合多目标评价参数的数学模型，通过优化计算可以得到订单的评价指标；根据评价指标，通过迭代计算可以得到炉次计划；依据评价指标的优先顺序可以得到订单的加工优先顺序，安排加工计划。通过排产方法的应用，理论上可以为全部订单安排生产计划，在保证全部订单有序、高效完成生产的同时，能够规范生产过程，降低熔炼费用，保证交货期。通过实际案例对这一排产调度算法进行了验证，证实了算法的实用性，对贵重金属材料排产调度方法的研究具有借鉴意义。

2 算法介绍

2.1 变量定义

j为订单编号， j=1，2，...，a。 k 为设备编号，k=1，2，...，b。

T 为任务加工时间矩阵，T=［tjk］a×b，矩阵元素 tjk为订单编号j在设备k上的加工时间与准备时间之和，当订单j不在设备k上加工时，tjk为0。

R 为工艺路径矩阵，R=［rjk］a×b，矩阵元素 rjk为订单编号j在加工工艺路径中设备k所处的顺序，订单编号j不需要在设备k上进行加工时，rjk为+∞，R即为全部订单的工艺路线。由工艺路径矩阵引出的工艺函数为r（j，k）=O，O为订单 j在设备 k所处的加工工艺路线中的加工顺序号。定义设备反求函数E（j，rjk）=k，则知道订单编号和加工顺序号后，可以通过设备反求函数得到加工设备。

X为开工时间矩阵，xjkl为设备k对订单编号为j且熔炉号为l的订单的加工活动的计划开始时间。

Y为完工时间矩阵，yjkl为设备k对订单编号为j且熔炉号为l的订单的加工活动的计划完成时间。

j为设备k在订单j到达前刚刚加工过的订单。k为订单j在到达设备k前刚刚用过的设备。

设置如下假设条件：在同一熔炉中熔炼的订单具有相同的配方，一个炉次中订单的熔炼、机加工、初切、退火具有相同的工艺。

2.2 算法建模

贵金属材料加工过程复杂，不仅要保证交货期，而且要保证设备有较高的利用率，提高排产效率，特别是要充分利用熔炉的熔炼能力。经过反复建模和试验验证，构建计算量小、计算时间短、优化效果好的启发式目标函数作为评判准则。

式中：h为加工顺序号，1≤h≤e，e为订单j在加工工艺路线中最大的加工顺序号；ΔTdj，τ为交货期与当前排产时间的差值，d为常量，τ为当前排产时间；yj为优先级，yj越小，说明订单越重要，应优先考虑排产；mj为订单需要用到的材料质量，由于是贵金属材料，因此mj越大，说明订单价值越大，应优先进行排产；ε1、ε2、ε3、ε4为权重；Qj，k为在设备k处订单j具有的评价指标，评价指标越小，说明订单的优先级越高，应优先安排生产。

取O=1，即在第一道熔炼工序时，得到全部订单任务的评价指标，然后从小到大进行排序，i=1，2，3…c，c等价于订单数。通过设备反求函数可以得到订单编号，P（i）=j。

熔炉的熔炼能力为W。尽量将评价指标相近或者相互连续的订单放到一个熔炉中进行熔炼，使熔炼订单的总质量接近W，以达到保证订单按照优先级的先后进行加工，充分利用熔炉的熔炼能力，减少浪费。

炉次计划步骤如下。

（1）将未排订单按照评价指标从小到大进行排序，第一个序号为1，第二个序号为2，依次类推。排好后如图1所示开始循环，图中M为订单质量的累加。

（2）循环结束，将符合条件的订单合为一炉熔炼，不符合条件的订单转为未排订单。

（3） 重复步骤（1）、（2），直至所有订单完成。

（4） 计算熔炉的评价指标 Φl，o，并从小到大进行排序。Φl，o越小，表明优先级越高，应优先进行熔炼。

式中：l为当前熔炉编号，q（j）=l表示订单 j在熔炉 l中熔炼；n为熔炉l在一次熔炼计划中熔炼的订单数量。

（5）输出炉次计划。

2.3 变量赋值

▲图1 炉次计划原理

在一个熔炉中熔炼的订单具有相同的熔炼、机加工、初切和退火时间，加工时间上的差异体现在分剪、精轧、冲压和检验包装方面。订单一般包含很多个相同规格的产品，为了简化描述过程，将订单作为整体来进行讨论。

订单的熔炼、机加工、初切、退火是流程性生产，过程比较单一，笔者不做讨论，着重讨论分剪、精轧、冲压、检验包装。对于订单j将要在设备k上加工，分四种情况。

（1）订单j上一道工序未完成，设备k当前有任务，订单j在设备k上的开始加工时间为订单j上一道工序的结束时间与设备k加工完成当前订单时间中的大值，即：

（2）订单j上一道工序完成，设备k当前有任务，订单j在设备k上的开始加工时间为设备k加工完成当前订单的时间，即：

“噬菌体侵染细菌的实验”是人教版“高中生物学”《必修2·遗传与进化》第三章第一节的教学难点。要彻底理解这部分的内容，学生不仅需要对科学史有一定了解，还需要具备一定的分析对比、综合提炼的能力。除此之外，学生还需要具备一定的空间想象能力，能想象出噬菌体的形态特点等。这给学生带来不小的学习障碍。学生在学习过程中经常存在以下的困惑：①利用放射性同位素32P和35S分别标记的是噬菌体的什么物质？②噬菌体侵染细菌的过程具体是怎样的？③为什么上清液和沉淀物的放射性会有不同？

（3）订单j上一道工序未完成，设备k当前无任务，订单j在设备k上的开始加工时间为订单j上一道工序的结束时间，即：

（4）订单j上一道工序完成，设备j当前无任务，订单j在设备k上的开始加工时间为当前时间。

2.4 算法步骤

（1） R、T 根据已知赋初值，j=1，2，…，a，k=1，2，…，b，X的元素赋初值无穷大。

（2）统计相关信息，包括订单j在设备k上的加工时间及在加工工艺路线中的加工顺序号、订单j的交货期、订单j的优先级、订单j所需熔炼原料质量。

（3） 利用式（1）计算 Qj，k，得到投料顺序，根据图1和式（2）计算 Φl，o，得到炉次计划。

（4） Φl，o越小的订单，越优先进行熔炼；Qj，k越小的订单，越优先进行加工。

（5） 按照优先顺序从大到小，利用式（3）～式（6）循环计算开工时间变量xjkl，同时通过公式yjkl=xjkl+tjkl计算输出完工时间矩阵Y，直到所有订单中每个工序的开工时间和完工时间均被赋值，计算结束。

3 算法实例

生产系统由2个熔炉、1台机加工设备、1台初切设备、1个退火炉、3台分剪设备、2台精轧设备、2台冲压设备、3台检验包装设备组成，人力资源作为设备来考虑。熔炉的设备编号为1a、1b，机加工设备的设备编号为2，初切设备的设备编号为3，退火炉的设备编号为4，分剪设备的设备编号分别为5、6、7，精轧设备的设备编号分别为8、9，冲压设备的设备编号分别为10、11，包装检验的设备编号分别为 12、13、14。

确定任务加工时间矩阵T和工艺路径矩阵R，设定系统的起始时间为0，熔炉的熔炼能力为100 kg，求解订单的状态矩阵和输出矩阵。

订单关系表记中所包含的属性有订单号、物料编码、优先级、质量、交货期、Qj，k、投料顺序、设备、开工时间、加工时间、完工时间。现有12个订单，订单号、设备、物料编码、优先级、质量、交货期、加工时间为已知。将订单号、优先级、质量、交货期、加工时间，以及O=1、ε1=1、ε2=1、ε3=10、ε4=0.01 代入式（1），经过求解计算，得到 Qj，k。 根据 Qj，k的大小，从小到大进行排序，得到投料顺序。

订单关系表见表1，表中交货期无量纲。

表1 订单关系表

根据图1和式（2），得到炉次计划，如图2和图3所示。熔炉1a安排两次熔炼，先熔炼编号为8、9、4的订单，后熔炼编号为 5、11、3、10、12 的订单。熔炉 1b 安排一次熔炼，熔炼订单编号为 6、7、2、1。 熔炉 1a、1b 同时开工。

根据算法，得到全部排产方案，见表2。

图4为熔炉1a熔炼订单8、9、4时熔炉的利用率，图5为熔炉 1a熔炼订单 5、11、3、10、12 时熔炉的利用率，图6为熔炉1b熔炼订单6、7、2、1时熔炉的利用率。由图4～图6可见，熔炉1a第一次熔炼时熔炉的利用率达到了92%，熔炉1a第二次熔炼时熔炉的利用率达到了95%，熔炉1b的利用率达到了96%。

订单在熔炼、机加工、初切、退火完成后，已完成退火但未参加下一步加工的订单，再按评价指标从小到大进行排序，评价指标小的先进行排产加工。

表2 排产方案

▲图2 熔炉1a炉次计划

▲图3 熔炉1b炉次计划

▲图4 熔炉1a第一次熔炼利用率

▲图5 熔炉1a第二次熔炼利用率

▲图6 熔炉1b熔炼利用率

4 结论

笔者集合了炉次计划、加工排产、车间调度等多种需求，首先采用启发式算法对所有订单进行评价排序，得到投料顺序；然后在此基础上结合熔炉的熔炼能力，得到了炉次计划；最后得到一整套完整的排产调度算法。通过这一算法可以确定每个订单每道工序加工过程中具体的计划开始时间和计划结束时间。

贵金属材料加工的工艺流程具有熔炼、集中、分剪等特点，用启发式算法建立生产运作的数学模型，运行速度快，实用性强，优化效果明显。

求解模型融合了多目标评价参数，可以通过改变权重 ε1、ε2、ε3、ε4的大小， 来调节各参数的权重比例，达到预期的排产效果。

笔者提出的排产调度算法结合实际情况，在安排订单高效有序进行生产加工的同时，可以保证订单交货期，节约能源消耗，提高设备利用率，进而使熔炉的熔炼能力得到充分利用。