共查询到17条相似文献,搜索用时 718 毫秒
1.
时凌 《内蒙古师范大学学报(自然科学版)》2003,32(4):374-377
研究了具有优先权的自由作业时间表问题,在工件具有准备时间的条件下,给出一种新的启发式算法,其最坏性能比不超过2,猜想该算法的紧界是2—2/(m 1),其中m是机器的台数,证明在3台机器的情况下,该算法的最坏性能比为3/2,且上界是紧的。 相似文献
2.
时凌 《中央民族大学学报(自然科学版)》2002,11(1):35-38
本文研究具有准备时间的流水作业时间表问题,给了一个简单的启发式算法,证明了一个简单的启发式算法的最坏性能比是m 1/2(其中m是机器的台数),且关于上界是紧的,特别当m=2时,该启发式算法的最坏性能比是3/2,此结果要好于Potts在1985年所给出的算法。 相似文献
3.
时凌 《中南民族大学学报(自然科学版)》2002,21(4):82-84,87
研究了具有准备时间和延迟时间的自由作业问题,通过引入虚拟工作,证明该问题是强NP-困难的,提出了解决这个问题的一种方法--贪婪算法,并证明了在只有2台机器的情况下,具有准备时间和延迟时间的自由作业问题使用贪婪算法,其最坏性能比是3/2。 相似文献
4.
时凌 《湖北民族学院学报(自然科学版)》2002,20(1):33-37
研究一类具有延迟时间的自由作业问题,证明在机器台数任意的情况下,一个简单的贪婪算法的最坏性能比不超过2。特别当m=2时,证明了该算法的最坏性能比为3/2,其中m为机器的台数。 相似文献
5.
时凌 《湖北民族学院学报(自然科学版)》2001,19(4):48-50
讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是(m 1)/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。 相似文献
6.
时凌 《西南民族学院学报(自然科学版)》2003,29(3):258-263
研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的.给出一种新的启发式算法,并证明该算法的最坏性能比是(m 1)/2,且上界是紧的. 相似文献
7.
《石河子大学学报(自然科学版)》2018,(4)
本文研究n个工件在2台机器上加工的流水作业排序问题。同一工件在一台机器上完工后在下一台机器加工之前有一个时间间隔即运输时间,所有运输时间都是由单自动机来完成运输,同一时间自动机只能运输一个工件,本文主要研究所有加工时间均匀等于1的情况下该问题的复杂性,并给出新的启发式算法,证明该算法的最坏性能比是3/2,且上界是紧的。 相似文献
8.
杨汉兴 《武汉科技大学学报(自然科学版)》1996,(4)
Gonzalez和Sahni已证明:当m≥3时,排序问题FmCmax是NP困难问题,没有好算法。因此,很多学者提出了多种简单易行的启发式方法求这类问题的次优解,且对其中的GS算法和RS算法证明了在最坏情况下性能比C*max(A)/C*max的上界不超过{m/2}*。本文用同一例子证明,对这两种算法,这一上界是可达的。 相似文献
9.
带机器准备时间的同类机在线与半在线排序问题 总被引:4,自引:1,他引:4
研究带机器准备时间的m台同类机(uniform machines)在线和半在线排序问题,目标函数为极小化最大机器(工件)完工时间。对于在线情形,证明了LS算法的最坏情况为ρ={(1 √5)/2,m=2,1 √2m-2/2,m≥3,并且当m=2,LS算法是最好的近似算法;当m=2,3,…,6时界是紧的,特别地,当s1=s2=…=sm-1,sm≥l时,证明了LS算法的最坏情况界为ρ={(1 √5)/2,m=2,3-4/m 1,m≥3,而且界是紧的;对于已知加工时间递减的半在线排序问题,证明了LS算法的最坏情况界为2—2/(m 1)。 相似文献
10.
对文献[2]中提出的求AFS问题的次优解的两个简单易行的启发式算法及其品性进行了进一步的研究。由于已证明了其在最坏情况下性能比Cmax(H)/Cmax的上界不去超过2,本文用两个典型的例子证明:对这两种算法,这一上界是可达的。 相似文献
11.
陈秀宏 《宁夏大学学报(自然科学版)》2004,25(3):223-225
将n个工件分配到m台平行机上加工,在工件的加工不中断及目标函数是极小化最大完工时间的条件下,对其GKK算法的最坏情形性能比界作了改进,并用实例表明了所得新上界的可达性。 相似文献
12.
在单机排序和工件运输问题的模型中,在2T1≥T3限制下,我们证明了最劣性能比可改进为27/14. 相似文献
13.
针对实际应用中先验知识存在偏差的问题,基于权向量长度恒定的常规线性约束波束形成算法,提出一种权向量长度恒定的最差情况性能优化波束形成算法.分析了神经次元分析(MCA)学习规则与该波束形成优化问题在数学描述上的相似性,利用神经MCA学习规则实现鲁棒自适应波束形成.仿真结果表明,与基于线性约束的波束形成算法相比,该算法具有更强的信号跟踪能力和干扰抑制能力,并且对信号方向向量的偏差具有更强的鲁棒性. 相似文献
14.
陈伯龙 《兰州大学学报(自然科学版)》2009,45(4)
考虑了两台平行机的排序问题,其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的,而且每一个任务带有一个运输时间,目标函数是最小化最大运输完工时间.这个问题是强NP-难的.提出一个最坏情况比是8/5的多项式时间近似算法,并指出这个界是紧界.同时还用动态规划方法求解该问题. 相似文献
15.
16.
讨论了如下定义的带核元带拒绝装箱问题:设有许多等长的箱子,给定一个带核元的物品集,每个非核元有2个参数:大小和罚值.非核元物品可以放入箱子也可被拒绝放入箱子.如果某物品被拒绝放入箱中,则产生惩罚值,同时要求核元不允许被拒绝且每只箱子中所装核元个数不超过1,问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,在多处理器任务调度及内部互联网信息管理等问题中有着广泛的应用背景.提出了一个求解该问题的局外近似算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果. 相似文献
17.
讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界. 相似文献