优化研究和数值模拟解决无等待流水车间在钢铁生产调度

文摘

本文考虑了米机流水车间调度问题不约束最小化总完成时间在钢铁生产是典型的模型。首先,最短处理时间的渐近最优性(SPT)第一个规则是证实这个问题。为了进一步评估算法的性能,性能保证设计新的下界。论文的最后,数值仿真结果表明了该算法的有效性和下界。

1。介绍

炼钢是一个多级的过程中融化铁转化为钢铁产品的流程顺序转换炉、加热炉、轧机。明显,这是一个非常典型的流动商店。不同,在钢铁生产,热半成品可以连续两个操作之间不等。例如,一块达到轧制温度通过热炉前处理的轧机。如果一个加热板等待很长一段时间前的机器,其温度会显著下降。一旦一个板的温度低于轧制温度、再热必须执行,这将消耗大量的能量。此外,在制品的大小在炼钢尤其大,这限制了连续两个机器之间的缓冲区的容量。作为总完工时间最小化准则(TCT;细节TCT目标可以在找到1,2)可以有效地减少在生产的存货,解决无等待流水车间与TCT的研究目标是合理有效的钢铁行业。

与标准调度格雷厄姆等人1979年提出的符号(3解决无等待流水车间调度问题,以减少TCT可以用。岩(4)表示强np困难问题这意味着通用问题的最优解,不能在多项式时间内,除非获得P = NP。Allahverdi和Aldowaisan5)被认为是问题,表示,建立时间序列相关的。得到了最优解的两个特殊流商店和统治关系发展的普遍问题。几个构造启发式算法和多项式的计算时间。Allahverdi和Aldowaisan6)解决问题,在那里表示,设置时间处理时间和顺序独立分开。提出了最优解和主导地位关系,分别对某些案件,一般情况下。五个启发式算法开发和评估对小和大量的工作。Aldowaisan和Allahverdi7)提供了新的启发式和比较这些提出算法的性能与三个现有的启发式的问题。高et al。8]目前两个建设性的启发式,标准差启发式(ISDH),改善和提高Bertolissi启发式(IBH)问题,并提出四个综合启发式,使用insertion-based本地搜索方法和迭代算子来改善ISDH和IBH的解决方案。Allahverdi和Aydilek9讨论问题,,在那里是一个特定的值。一个算法来找到一个上界极小化的情况下,上界不是给定的或未知的。考虑到最大完工时间上限,一个算法和遗传算法用于解决这个问题。调查的问题可以发现在10]。

本文的渐近最优最短处理时间(SPT)首次SPT规则是证明问题在概率极限的感觉,这项研究仅限于排列时间表(排列时间表的细节可以在[1,2])。进一步评估策略,一个新的下界与性能保证设计。论文的最后,数值模拟显示算法的收敛性和有效性的下界。

本文的其余部分组织如下。问题是制定节2SPT的渐近最优性准则是证明3。提出的新下界和计算实验部分4和5,分别。而在部分6关闭,本文的结论。

2。规范问题

解决无等待流水车间问题中,一组n工作必须按顺序处理米不同的机器上没有抢占。每一份工作,,通过米机器以相同的顺序,需要处理时间在机,。假设处理时间是独立和恒等分布的先验知识。随机变量,定义在区间。在任何给定的时间每台机器最多只能处理一个工作,每个工作最多可以处理在一个机器。工作可同时,排列时间表是;也就是说,所有工作上处理所有的机器在同一个订单。连续两个机器之间的工作不能等待和中间存储是零。给定的机器上完成的工作必须完成,直到下一个机器上的处理前的工作。让表示的时间工作,实际上需要离开机器,。工作的时间j开始处理在第一个机器用。工作的完成时间用。工作的目标是找到一个序列排列时间表的约束下最小化完工时间的和最后的机器;也就是说,。

3所示。证明SPT的渐近最优规则

SPT规则实际上是一个启发式的工作安排在不减少的秩序价值。渐近分析的工具,SPT的渐近最优规则问题介绍如下。

定理1。我们的处理时间,,,独立随机变量有相同的连续分布的密度上定义。然后,概率 在哪里获得的客观价值的SPT规则,然后呢是最优值。

证明。工作计划是SPT指数序列。对任意的工作数量,,出现在SPT的处理时间序列可以表示如下 我们添加左边底部工作1的处理时间和工作分别在正确的顶部,并获得一个矩阵如下: 对于一个给定的SPT序列,与矩阵,我们有 总结在工作和分裂米双方(4),我们有 在哪里和磅的下界值吗和磅,分别。表示工作的完成时间j在磅,磅,SPT序列,,,分别。为工作,SPT序列之间的差距和下界 在哪里表示一组包括工作机器,关键路径。分双方(6),以限制,我们有 在哪里表示期望的处理时间,和倒数第二的不平等(7因为大数定律)。让的最大价值在就业机会。因此,我们有 总结了工作,我们有 分双方(8),以限制,我们有 与限制(8)和(9),我们得到的结果定理。

4所示。新的下界

的强np困难问题,下界通常是最佳的替代解决方案。2013年,白和任11提出了一个渐近最优下界,两派,问题如下: 在哪里

这下界可以处理问题没有任何改变。但是在某些情况下,两派也不会取得好的效果。例如,考虑下面的示例(请参见图1)。

例1。摘要流车间问题三份工作。这些工作的处理时间;;和。因此,最优序列和最优值是38(见图1)。我们为两值有关, 和最优值的差距,两派(38−27)/ 27×100%≈40.74%。显然,错误是相当大的。改善性能的两派,一个新的下界,磅,提供。考虑 在哪里磅的下界值吗。计算例子1用磅38,获得价值。

定理2。对任何问题的实例,我们有 在哪里两派的客观价值。

证明。考虑给定最优时间表的工作是索引从1到n。表示工作的完成时间,在磅作为,我们有 因此,我们有 总结了工作,我们可以获得这个定理的结果。

5。计算结果

在本节中,我们设计了一系列的计算实验揭示了SPT的融合规则和不同大小的新下界的有效性问题。首先,我们用磅比较SPT的规则收敛的趋势。然后,我们比较磅用磅磅的有效性。不同组合的工作和机器测试显示参数变化时的性能变化。组合有五个,十个,15个机器有100,200,500,1000,1500工作是检测测试SPT规则和下界磅。处理时间是随机生成的离散均匀分布和正态分布的意思分别和方差49。十个不同的随机测试为每个参数进行组合,和平均报道。

比率SPT /磅显示在表1客观的价值观是SPT规则的磅。从表中的数据,我们可以看到,SPT /磅的比率方法一的工作数量的增加从100年到1500年的固定数量的机器。例如,与均匀分布在15个机器,SPT /磅的比率从1.04071下降到1.01291,当工作数量的增加从100年到1500年。这一现象表明SPT的渐近最优规则。相反,固定数量的就业岗位,SPT的比率/磅扩大机器数量的增加从5到15。更大的原因可能是机器的数量,空闲时间插入量越大,它可以放大的价值目标之间的差距及其下界。

磅的比率/磅显示在表2磅的值吗来磅。表中的数据显示,磅很明显优于磅吗适度规模问题。工作岗位数量不断扩大,磅方法磅越来越符合磅的渐近最优性。

6。结论

在本文中,我们研究一个非常有用的钢铁生产调度问题,解决无等待流水车间总完工时间最小化的。古典SPT的渐近最优性规则是证明与渐近分析的工具,当问题规模足够大。促进数值模拟,一个新的下界与性能保证。计算结果表明,SPT规则和新的下界适合大规模问题。

确认

本研究在一定程度上是由中国国家自然科学基金(61104074),基础研究基金为中央大学(N110417005)、中国博士后科学基金会(2013 t60294, 20100471462),中国辽宁省科学研究基金会的医生(20101032),和沈阳城市的2011计划项目(f11 - 264 - 1 - 63)。

引用

1. y . n . Sotskov t . Tautenhahn f·维尔纳,“启发式置换流水车间调度与批处理设置时间,“或频谱,18卷,不。2、67 - 80年,1996页。视图:谷歌学术搜索
2. y . n . Sotskov a Allahverdi,苏耿赋。赖,”Flowshop调度问题最小化总完工时间随机和有限的处理时间,“运筹学学会》杂志上,55卷,不。3、277 - 286年,2004页。视图:出版商的网站|谷歌学术搜索
3. r·l·格雷厄姆·e·l . Lawler j . k . Lenstra和a . h . g . r .菅直人”确定的排序和调度的优化和近似:一项调查,“《离散数学5卷,第326 - 287页,1979年。视图:出版商的网站|谷歌学术搜索
4. h .岩”,一些新的结果流车间调度。”Zeitschrift毛皮操作研究,28卷,不。1,硕士论文,1984页。视图:出版商的网站|谷歌学术搜索|MathSciNet
5. a . Allahverdi和t . Aldowaisan最小化总完成时间在一个不与顺序相依flowshop添加剂转换时期,“运筹学学会》杂志上,52卷,不。4、449 - 462年,2001页。视图:谷歌学术搜索
6. a . Allahverdi和t . Aldowaisan”,不单独设置摘要flowshop总完成时间标准,“在运筹学国际交易7卷,第264 - 245页,2000年。视图:谷歌学术搜索
7. t . Aldowaisan和a . Allahverdi”新启发式m-machine不flowshop总完工时间最小化,“ω,32卷,不。5,345 - 352年,2004页。视图:出版商的网站|谷歌学术搜索
8. 英国高,问:潘,p . n . Suganthan和j·李,“有效解决无等待流水车间调度问题的启发式总流程时间最小化,“国际先进制造技术杂志》上2013年,66年,页1563 - 1572。视图:谷歌学术搜索
9. a . Allahverdi和h . Aydilek算法不flowshops极小化总完工时间问题,”国际先进制造技术杂志》上,卷68,不。9日,第2251 - 2237页,2013年。视图:出版商的网站|谷歌学术搜索
10. n . g .大厅和c . Sriskandarajah机器调度问题的调查过程中阻塞和不,”运筹学,44卷,不。3、510 - 525年,1996页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
11. d .白t . Ren,“新的近似算法流店总完工时间的问题,”工程优化,45卷,不。9日,第1105 - 1091页,2013年。视图:谷歌学术搜索

版权

版权©2013华为元et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。