共查询到20条相似文献,搜索用时 31 毫秒
1.
排序问题的一个判别条件和一类特殊的m×n排序问题 总被引:2,自引:0,他引:2
一、引言 在排序理论的一篇开创性的文章中,Johnson给出了2×n排序问题(二台“机床”,n个“零件”的同顺序排序问题,这里机床和零件被理解成广义的)的最优顺序的算法。在导出这算法时,Johnson给出的判别两个相邻零件的先后次序的一个条件起着关键作用。这判别条件是:设i,j是相邻的两个零件,α_i和b_i(α_j,b_j)是i(j)分别在机床M_1和M_2上的加工时间,如 相似文献
2.
3.
在工厂的零件加工车间,设有n个零件要在m台机床上加工,各零件根据工艺上的要求,按一定顺序通过这些机床,如何安排这些零件顺序使预先给定的指标达到最优,这就是运筹学中所谓的排序问题。本文所考虑的排序问题:假设1)各零件皆依同一顺序通过这些机床;2)每个零件的加工时间为已知;3)每个机床在同一时间。只能加工一个零件。目的是要寻求一个顺序,使总的加工时间为最短。我们所得到的主要结果如下:1.设ω为(1…n)的某一排列,ω’为从ω经交换相邻两数字i和′的位置后的排列,T(ω)和T(ω′)分别表示在ω和ω’之下总加工时间,则当时,有T(ω)≤T(ω′)。2.我们所给出的条件比Nabeshima所给出的条件要弱。3.从推广Johnson法则这一角度看,本文定理4的结果已是最好的结果。 相似文献
4.
5.
6.
7.
研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法. 相似文献
8.
排序问题自Johnson提出后,长期以来对于多台机床的情形,一直进展不大。直到1975年越民义、韩继业才把这一问题大大向前推进了一步。到目前为止,关于同顺序的排序问题,越-韩条件算是最好的结果了。对于n个零件于单台机床上加工的最优排序问题,越民义、韩继业在文献[3]中作了系统的整理。Lawler在分段与加权之后,也得到了一些较好的结果。然而,上述作者所研究的问题,均以单位时间内诸零件 相似文献
9.
数控加工在机械制造领域具有举足轻重的作用,如何在满足加工精度的前提下提高加工速度是数控加工的一个关键问题.据数学机械化方法,将插补问题分解为局部优化和整体优化两部分,其中局部优化是在线段连接处通过采用二次曲线(抛物线)和三次曲线族过渡的方法,提高线段连接处的通过速度,使得局部通过速度最优;同时根据加工误差确定线段连接处的插补时间,并以插补时间为参数对线段连接处的插补参数统一进行调整,提高了数控软件的智能性.在局郎优化的基础上进一步进行整体优化,即采用基于直线加减速和S型加减速控制方式的前瞻处理算法,对加工路径进行有效预测,避免了因突然加减速造成机床振动,从一定程度上保证整体加工速度的提高,采用符号与数值混合算法,算法简单,保证了计算精度和速度,满足实时加工的要求.算法在蓝天数控系统上进行了实际加工验证,结果表明该算法达到了预期效果,验证了算法的有效性.与当前已有算法相比,根据机床加工参数不同,加工速度提高了50%-170%. 相似文献
10.
11.
12.
13.
张焕镇 《数学的实践与认识》1989,(3)
文[1]讨论了将多个零件分派给多台机器加工的一类排序问题,对满足特定条件的分派给出使总花费时间最少的计算方法.但条件过于苛刻,本文讨论一般的排序问题的最优解算法. 相似文献
14.
讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况. 相似文献
15.
一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上的在线排序,其中每个工件有事先未知的到达时间,加工时间在其到达时才知道,目标是极小化工件的最大完工时间.Zhang等(Naval Research Logistics,2001,48:241~258)就该问题提出了一个竞争比不超过2的算法MHB,并猜测其竞争比可以达到1.618,因此是最好的在线算法.在本文中,我们证明了当机器容量趋于无穷时,算法MHB的竞争比不可能小于2,从而就上述猜测给出了否定的回答;另外,我们也提出了一个新算法,其竞争比也不超过2. 相似文献
16.
17.
关于排序模型1|·|ri≥0|n∑i=1vi的注记 总被引:2,自引:1,他引:1
设 J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少.1978年Kise,Ibaraki,Mine等在条件ri<rj蕴涵di≤dj(对于任何1≤i,j≤n)下,对于任何给定的J找到算法A.他们在论文[1]中"证明"算法A是最优算法.最近,李杉林给出一个例子说明他们的证明中的一个关键引理是错误的.本文作者在书[2]中也沿用了这个错误的"证明".对于算法A的最优性,本文给出一个新的简单的证明. 相似文献
18.
设J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件Ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少.1978年Kise,Ibaraki,Mine等在条件ri相似文献
19.
20.
设J={J1,…,Jn}是n个工件的集合,M是一台机器.每个工件Ji要在机器M上加工一次,而且是相继只加工一次,即加工不能够中断.Ji的加工时间是pi,准备时间是ri,即Ji不能在ri之前加工,要求完工的期限是di,即工件Ji的加工应该在di之前完成.否则,这个工件将被拒绝放在一旁.我们的目的是寻找排序算法A,当使用到给定的J上时,使被拒绝的工件个数为最少.
1978年Kise,Ibaraki,Mine等在条件ri〈rj蕴涵di≤dj(对于任何1≤i,j≤n)下,对于任何给定的J找到算法A他们在论文[1]中“证明”算法A是最优算法.最近,李杉林给出一个例子说明他们的证明中的一个关键引理是错误的.本文作者在书[2]中也沿用了这个错误的“证明”.对于算法A的最优性,本文给出一个新的简单的证明. 相似文献