共查询到18条相似文献,搜索用时 62 毫秒
1.
赵玉芳 《辽宁大学学报(自然科学版)》1998,25(4):309-311,315
本文对n个任务,2台同类处理机的排序问题Q2∥Cmax进行讨论,提出一个算法,用该算法得到的排序表长的界是2b+1/2bM,算法的复杂性为O(nlogn)。 相似文献
2.
考虑一类Qm|rj|Cmax的on_line问题的LS算法 (m台机器 ,速度分别为s1,s2 ,… ,sm,且s1≤s2 ≤…≤sm) ,证明了这个算法性能指标上的上界是 1+ m - 1i =1si sm . 相似文献
3.
本文给出处理机具有不同的开始加工时间的Q,ai|pmitn|Cmax排序问题的一个最优算法,算法的复杂性为O(m^2n^2)。 相似文献
4.
考虑同类机随机在线排序问题.假设有m台同类机,工件在线到达,问题的目标是使总加权完工时间的期望值最小.考察该随机在线问题,首先利用线性规划松弛的方法,得到问题最优解的一个下界;然后给出解决该问题的一个在线算法,并分析了该算法的竞争比. 相似文献
5.
针对带有惩罚费用的工件在同类平行机上的在线排序问题,目标函数为极小化被接收工件的最大完工时间加上被拒收工件的总拒绝费用,给出了一在线算法,证明了该算法的竞赛比不超过,有Z^on/Z^OPT≤1+ρ。 相似文献
6.
7.
8.
带机器准备时间的同类机在线与半在线排序问题 总被引: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)。 相似文献
9.
研究了两台平行机上目标为开工时间的在线排序问题,即目标函数为极小化最大工件开工时间。首先给出了问题的下界,然后证明了贪婪算法的上界等于问题的下界,从而是最优的在线算法。 相似文献
10.
11.
时序安排或任务调度算法广泛应用于计算机的各个领域,如Linux进程调度算法,排课表算法等。本文使用无向图模型.得到一种改进的时序安排或任务调度算法。通过对比,显示该算法在实际应用中可大大提高工作效率。 相似文献
12.
提出了基于遗传算法的面向动态异构多处理器的调度算法(Heterogeneous Scheduling Genetic Algorithm,HSGA),该算法利用连续的多个调度时间片完成遗传算法的迭代计算,在保证计算效率的同时获得较好的调度结果,从而为每个应用选择符合其计算特性的处理器内核.仿真实验表明,本文算法在4核、8核和16核的平台上相比较于经典的匈牙利算法ED2仅分别增加了0.4%,1.1%和1.3%,新的调度算法相比于匈牙利算法和Local调度算法具有更好的调度效果及更好的动态适应性. 相似文献
13.
并行加工设备组生产调度的一般模型及算法 总被引:4,自引:0,他引:4
给出了一个描述并行加工设备组生产调度问题的一般模型及两个启发式算法,对ELPT方法,另提供了一个误差分析结果,对极大消去法给出了个数值计算实例. 相似文献
14.
丁伟 《中山大学学报(自然科学版)》2010,49(1)
研究的目的在于解决实践中对多组任务的优化排序问题,即在最短的时间内完成所有给定的任务。由于这类问题往往都是NP完全问题,人们通常寻求其近似算法。提出了一种改进的LPT算法,利用"最大相对加工时间"准则和"首先空闲"准则,讨论了将n组工件安排在n台速度不同的专用机,一台速度小于专用机的通用机上的Cmax问题,得到了利用该近似算法所得的解T与最优解T*的一个估计:T/T*≤1+1/∑i∈Isi,其中I表示在最后完工的工件完工之前,在通用机上至少安排了一个工件的工件组的下标集合。由此得出采用该近似算法对工件排序,在最差情况下要比最优排序多出1/∑i∈Isi的时间。 相似文献
15.
对多处理机调度问题P∥Cmax,给出一种近似算法,大量实例的计算结果表明,本文的算法是非常有效的。 相似文献
16.
数据传输资源调度是空间资源管理的重要内容之一。为了有效求解数据传输资源调度问题,基于蚁群算法构建了一种数据传输资源调度方法。实验结果表明,蚁群算法能有效求解数据传输资源调度问题。本文方法可推广应用到其他资源调度领域。 相似文献
17.
18.
丁伟 《中山大学学报(自然科学版)》2010,49(6)
对于实践中存在的具有两组任务的优化排序问题进行了讨论,在经典的LS算法的基础上提出了一种改进的LS算法,利用"首先空闲"准则选择机器,按照工件的到达顺序安排工件,讨论了将两组工件安排在两台速度相同的专用机,m-2台同速度的通用机上的Cm ax问题,其中工件具有准备或到达时间,且工件的准备或到达时间均不超过其加工时间的α倍。目标是在最短的时间内完成所有给定的任务。得到了利用该近似算法所得的解TLS与最优解T*的一个估计(1+α)(2-1/m),并且证明了对任意的α此界是紧的。 相似文献