排序方式: 共有24条查询结果,搜索用时 0 毫秒
21.
时凌 《西南民族学院学报(自然科学版)》2003,29(3):258-263
研究流水作业时间表问题,在具有延迟时间的条件下证明该问题是强NP-困难的.给出一种新的启发式算法,并证明该算法的最坏性能比是(m 1)/2,且上界是紧的. 相似文献
22.
时凌 《湖北民族学院学报(自然科学版)》2002,20(4):62-65
研究具有准备时间的自由作业问题,给出一种简单的启发式算法,证明 在此启发式算法上,最坏性能比是2-1/m(其中m是机器的参数),且上界是紧的。从而证明了对该问题的猜想:即在贪婪算法的情况下其最坏性能比是2-1/m(其中m是机器的台数),且上界是紧的。特别当m=2时,具有准备时间的自由作业问题,利用该启发式算法得到最坏性能比是3/2,其上界也是紧的。 相似文献
23.
时凌 《中南民族大学学报(自然科学版)》2002,21(4):82-84,87
研究了具有准备时间和延迟时间的自由作业问题,通过引入虚拟工作,证明该问题是强NP-困难的,提出了解决这个问题的一种方法--贪婪算法,并证明了在只有2台机器的情况下,具有准备时间和延迟时间的自由作业问题使用贪婪算法,其最坏性能比是3/2。 相似文献
24.
时凌 《湖北民族学院学报(自然科学版)》2001,19(4):48-50
讨论具有延迟时间的流水作业问题,并提出了解决该问题的一种启发算法,证明了其最坏性能比是(m 1)/2,并且上界是紧的,特别当m=2,即两台机器上具有延迟时间的流水作业问题时,其最坏性能比是3/2,最后将所得结论推广到FmID2问题,即加工时间相等且延迟时间只取两上值的流水作业问题,其最坏性能比也是m 1/2。 相似文献