文摘
解决充电计划问题涉及指控和订单在每个电荷,基于旅行商问题负责规划模型,并提出了改进的交叉熵算法。首先,未知负载量的费用规划问题建模为一个旅行推销员问题。模型的目标是最小化每个订单及其电荷之间的不同成本中心,开放订单成本,未选中的订单成本。其次,改进的交叉熵算法与改进的初始状态转移概率矩阵,根据不同的钢材建造等级和秩序订单之间的宽度。最后,一个实际的算例显示了模型和算法的有效性。
1。介绍
主要炼钢是钢铁生产过程的主要阶段(1),氧炉或电动炉铁水转化为批钢液。批处理,用来满足一组订单要求相同的电荷宽度和钢铁的成绩,被称为在钢铁生产的条件。收费计划将主要的订单需求转换成各种指控钢铁生产的过程约束。设计合理的费用可以提高生产力和减少资源和能源消耗。负责规划是一个关键元素的生产炼钢行业的运营管理和讨论在当下文学很多。例如,唐et al。2)建立了一个混合整数规划模型和遗传算法的问题。在另一篇论文,唐,江3]提出了一种新颖的混合整数规划模型的电荷规划问题,提出了和两种类型的拉格朗日松弛方法通过使用不同的放松的方法来解决这个问题。的指控这些文章之前,而最好是由规划师在钢铁生产过程中为了提高生产力。董et al。4)指控的数量最小化的目标转换为一个约束的最小和最大数量的指控。然而,当我们得到一个收费计划,费用也需要根据约束首先解决。雪et al。5)负责规划问题建模与未知的电荷数量和模型转变成pseudo-traveling推销员模型。在这个模型中,不同成本费用计算总差异订单相同的电荷,而最好计算差异订单每个电荷,电荷中心顺序根据实际钢铁生产过程。王等人。6)开发了一个新的收费计划模型和修改孤雌生殖的坯锭连续铸造过程的算法,但处罚合同产品的宽度和钢铁的成绩从模型中删除。基于上述论文的分析,精确的充电计划模型,特别是在不同的最佳负载量和最小成本之间的每个订单及其电荷中心秩序,需要进一步的研究。
负责规划问题是一个np难组合优化问题,因此如何提高算法的速度和精度对于这个问题是一个关键。正如上面提到的,收费计划是由一些生产约束条件下,可以用来改善电荷的速度和准确度规划算法。现有的算法只考虑这些约束变量负责规划模型而提出的改进的交叉熵(ICE)算法在研究中可以使用有效的约束。交叉熵(CE)方法(7)是一个简单、高效和一般方法求解np难组合优化问题。它已被用于解决旅行商问题(8),车辆路径问题(9),缓冲区分配问题(10),最大割问题[11]。这些应用程序演示的力量CE法作为解决np难问题的通用和实用工具。
在这个研究中,改进的交叉熵算法来解决费用规划问题与未知的电荷数量及其目标是最小化每个订单及其电荷之间的不同成本中心。剩下的纸是组织如下。部分2州负责规划模型基于旅行商问题。部分3详细介绍了改进的交叉熵算法。该方法应用于一个例子,结果相比,交叉熵方法部分4。本研究总结和结论部分5。
2。基于旅行商问题的规划模型
2.1。问题描述
收费的基本单位是炼钢过程中,问题在这个研究是建立最优收费计划包括电荷中心订单和订单合并。每个订单都有自己的钢种的要求,规范和到期日期。需求的差异可能会导致一些成本当一个订单合并成一个电荷中心秩序。因此,减少需求差异电荷中心订单和订单合并到他们的三个目标之一的规划问题。另外两个目标是最小化的成本没有订单和开放订单的金额用于填写炉但不属于任何当前订单。要求建立一个计划如下。(1)订单收费的钢铁的成绩应该在同一钢种类。(2)订单收费的宽度差异不应超过允许的最大调整宽度。(3)订单的厚度应该是一样的。在这项研究中,相同厚度的订单应该都根据实际生产过程。(4)合同产品的总重量不应超过最大炉容量。(5)合同的到期日期的产品应该是类似的。
2.2。负责规划模型
鉴于订单,假设每一个订单小于炉容量,不能分割。负责规划问题建模如下。
最小化
受 在哪里是一个惩罚系数的开放订单管理中心订单吗,电荷的重量吗,没有处罚的费用,,可以通过计算是不同的成本之间的差异和电荷中心秩序那合并后,,,是钢的成本差异造成的成绩,宽度,和到期日期,分别之间和,可以计算如下: ,,钢级值、宽度、和到期日期的顺序,分别。单位成本系数与钢级的区别。是单位宽度不同违约成本系数。早熟的惩罚系数和吗是迟到的惩罚系数。是到期日期分段参数。
和决策变量,在哪里
在上述费用规划模型,目标函数(1)最小化每个订单的不同所带来的费用的总和及其电荷中心秩序,导致开放订单成本和惩罚没有订单的成本。约束公式的第一部分(2)代表,每个订单只能分配给一个电荷中心最多的第二部分约束公式(2)代表总电荷重量小于炉容量,第三部分约束公式(2)表示变量和有两个可能的值:0或1。
2.3。旅行商问题模型费用计划
以订单为城市,不同的和成本造成的订单合并成电荷中心,导致开放订单成本和惩罚没有订单的距离,炉容量最大距离一个旅行推销员,负责规划问题可以视为一个旅行推销员问题。问题的目标是找到一个最佳的顺序序列最小惩罚成本计算公式 在哪里的违约成本费用,可以计算如下:
分段函数(6)意味着如果不同的和订单合并成所造成的成本th电荷和开放订单成本大于总没有处罚,这个电荷的订单取消,然后的总损失th电荷将总没有处罚。意味着th电荷中心秩序:
指标函数表明是否合并成费用:
3所示。改进的交叉熵算法
在最后一节中,基于旅行商问题模型的规划问题。我们可以利用交叉熵方法,它被证明是一种有效的方法来解决旅行商问题,解决费用规划问题的方法。结果不符合性能期望当我们使用直接的方法,所以我们需要改善它。关键在使用交叉熵方法来解决组合优化问题是状态转移概率矩阵,可以根据问题的特征得到改善。负责规划问题,两个订单不同的钢成绩或宽度有不同的不同成本当合并成一个相同的电荷中心,所以矩阵元素可以根据不同的成本来解决如下。(1)根据矩阵元素赋值过程问题的约束: (2)正常化:
基于上面的状态转移概率矩阵,我们继续改进的交叉熵算法如下。
步骤1。生成顺序的路径,通过马尔可夫过程与初始状态转移概率矩阵描述(10),虚拟开始秩序。
步骤2。计算对于每一个订单路径使用公式(5)。
步骤3。订单从最小到最大的:和评估样本分位数为,在那里,被称为序列的顺序统计量和意味着四舍五入到最接近的整数。
步骤4。更新通过只有那些路径总长度小于或等于考虑到,更新后的值可以被估计为,在那里是集旅游过渡来是由和指标函数。
第5步。如果=对于每一个,计算然后停止;否则,重申从步骤1,表示迭代最小成本的价值。
避免局部最优,而不是更新的过渡矩阵直接通过一步4,我们使用一个平滑的更新程序,在那里是平滑参数。
4所示。计算结果与讨论
我们测试我们的算法在实际生产数据所示5]30的订单安排。基本的模型参数,,,,,,。
为了验证该算法的效率,我们用冰和CE比较结果。算法在Matlab 7.0上运行和个人电脑的奔腾R, 2 GB RAM。有三个参数提出了改进的交叉熵算法和交叉熵方法:样本大小、稀有参数,平滑参数。不同的参数值可能会导致不同的解决方案的结果。我们测试为,为,为。参数时保持同样的测试参数。10计算测试进行的每个参数的不同值。的意思是十个测试的结果之间的偏差和最好的结果以及平均运行时间被视为算法的性能标准。根据测试的结果,我们选择,和在这项研究中。负责规划问题上面提到的结果如表所示1。
获得的最优值是最好的值10倍的两种算法的平均时间是平均时间两种算法运行10次,和平均偏差之间的平均距离十值和最优值的10倍的两种算法。获得的最优收费计划的细节由冰和CE如表所示2。
从表1和2,我们可以观察到冰使相比CE的若干改进方法:最优值降低;平均运行时间减少了约11.2%;平均偏差都显著降低。这些观察结果证明该算法比冰CE法解决收费计划的问题时,这意味着更高的效率和更少的资源消耗在实际生产过程中。
5。结论
在这篇文章中,我们描述了充电计划问题,侧重于未知的电荷数量和订单之间的不同成本和费用中心订单在钢铁生产过程中。负责规划模型,基于旅行商问题,制定和改进的交叉熵算法。通过改善状态转移概率矩阵,提出了冰问题的算法可以利用的特点。结果,提高了算法的速度和精度,证明了一个实际生产的例子。未来的工作将集中在提高稳定性和准确性的冰和扩展模型和算法的实际规划系统。
利益冲突
作者宣称没有利益冲突有关的出版。
确认
作者承认金融支持的国家高技术研究发展计划(863计划)资助下的中国2007 aa04z157,山东省自然科学基金资助下ZR2010FZ001,山东大学和研究生自主创新基金(GIIFSDU)拨款2082012 yzc12136。