共查询到20条相似文献，搜索用时 15 毫秒
1.
讨论任务的加工是不可中断,处理机是同速机的排序问题Pm,ai||Cmax,证明了用Ls算法求解该问题的误差界是2-1/m． 相似文献
2.
讨论任务具有相关调整时间的排序问题，首先把[2]中关于LPT算法的结论推广到一般算法，然后又进一步将新的结论推广到处理机为恒速机的情况。 相似文献
3.
提出一类有准备时间的排序问题；分析了ＬＳ算法解此问题的最坏情况；个性了ＬＰＴ算法，使最差性能指标由４－２／ｍ改进到８／３－２／３ｍ。 相似文献
4.
讨论任务具有相关调整时间的排序问题 .首先把 [2 ]中关于LPT算法的结论推广到一般算法 ,然后又进一步将新的结论推广到处理机为恒速机的情况 . 相似文献
5.
平行机器的分批排序问题 总被引：1，自引：0，他引：1
本文研究一类具有分批约束的平行机排序问题.在恒同机情形导出Greedy算法,在m=2情形建立了匹配算法,在两台一致机器情形讨论了2-交换算法,并得到若干计算复杂性结果。 相似文献
6.
研究了两台平行机上目标为开工时间的在线排序问题,即目标函数为极小化最大工件开工时间。首先给出了问题的下界,然后证明了贪婪算法的上界等于问题的下界,从而是最优的在线算法。 相似文献
7.
对二台机器流水生产中的ＬＳ问题，以往的研究多为固定分批数，寻找最优分批大小；本文对机器引入调整时间，研究同时决定最优分批数及最优分批大小，并给出了相应最优算法． 相似文献
8.
9.
王新刚 《青岛大学学报(自然科学版)》1999,12(1):9-14
本文给出一种有限次分组快速排序算法并证明该排序算法处理均匀分布数据记录,正态分布数据记录及一般概率分布数据记录的平均时间复杂性为Ｏ（Ｎ）;给出四种快速 序算法分别关于均匀分布数据记录,正态分布数据记录,均匀波浪式分布数据记录和异常分布数据记录,进行排序的实验结果,表明有限次分组排序算法具有更快的效率。 相似文献
10.
11.
提出了一种新的排序方法－影射排序法,在很多问题的应用中使用此方法可提高程序的运行效率,其时间复杂度为Ｏ（Ｎ）。 相似文献
12.
带约束的平行机排序问题 总被引：1，自引：0，他引：1
讨论了带资源约束和机器准备时间的平行机排序问题,资源约束是指每个机器最多加工κ个工件．首先对一般情况下的同型机的PLPT排序进行了讨论;并首次对同类机排序进行了研究,给出了一个FLPT近似算法,同时对m=2时证明了PLPT排序的最坏情况紧界是2． 相似文献
13.
14.
15.
工件具有指数学习效应的流水作业排序问题 总被引：1，自引：0，他引：1
程明宝 《暨南大学学报(自然科学与医学版)》2008,29(1):48-53
讨论了工件具有学习效应的流水作业排序问题.目标函数为极小化最大完工时间和极小化总完工时间和.利用Gonzalez和Sahni提出的STPT算法规则估计了此两目标函数的最坏情况界,同时举例说明了对于两台机器流水作业的Johnson规则对于本研究问题并不适用.另外,对所讨论的问题的一些特殊情况分别给出了多项式时间算法. 相似文献
16.
为缩短工件的完工时间,研究目标为极小化最大完工时间的可拆分恒速机排序问题.在这个问题中,对工件拆分方式进行了限制,要求尽量少拆分工件,且拆分后子工件长度不小于给定阀值.该问题是NP难的.借助LPT算法的思想,提出了一个近似算法.多个实例的数值结果表明,本文算法可行、性能良好,能获得好的近似最优解. 相似文献
17.
18.
研究一类单台机器具有速度可选择约束的排序问题。引进了有关记号，给出了该问题解的概念。ｍ＝１的情形问题１｜ｓｐｅ．｜ΣＣ＿ｊ和问题１｜ｓｐｅ．｜Σｗ＿ｊＣ＿ｉ具有多项式时间算法，即为所谓的Ｐ问题，但对ｍ为一般情形其计算复杂性尚未解决。 相似文献
19.
本文给出了一种改进的起泡排序算法．改进后的起泡排序算法与经典的起泡排序算法相比,通常可以减少排序过程中总的比较次数．用ＰＡＳＣＡＬ语言描述的与算法有关的类型定义和变量说明如下：ＴＹＰＥｎｏｄｅ＝ＲＥＣＯＲＤｋｅｙ：ｉｎｔｅｇｅｒ;ｉｎｆｏ：ｄａｔａｔ... 相似文献
20.
杨宪泽 《西南民族学院学报(自然科学版)》1995,21(4):384-390
提出了一类问题的映射排序算法，其特点是附加一定的存储开销，在内排序中关键字与数组下标作映射或链接处理，不实施反复比较与交换关键字的操作，时间复杂性达到Ｏ（Ｎ），在外排序中，文件输入／输出次数减少，提高了效率，这类算法适宜今后的大规模信息处理中广泛采用。 相似文献