共查询到19条相似文献，搜索用时 187 毫秒
1.
考虑极小化加权总完工时间的单机分族分批排序问题,给出了最优排序的性质和算法,并加以证明,对工件有k个到达时间的情形,给出了一个复杂性为O(2k-1nlogn)的启发式算法. 相似文献
2.
曹国梅 《常熟理工学院学报》2009,23(4):22-24
考虑极小化加权总完工时间的一类无界的不相容工件族分批排序问题,给出了最优排序的性质和算法,并加以证明．对工件有k个到达时间的情形,给出了一个复杂性为D（2^k-1nlogn）的启发式算法． 相似文献
3.
考虑了在工件具有学习效应的条件下,目标函数为最大完工时间和总完工时间的单机成组排序问题.对这两个问题分别给出了多项式时问算法并证明了其算法的最优性. 相似文献
4.
曹国梅 《周口师范学院学报》2008,25(5)
讨论了单机成组排序问题的加权总完工时间和最大延迟时间的极小化问题.并分别给出了算法.对于单杌成组排序误工总数问题,通过构造函数,利用动态规划方法给出其算法. 相似文献
5.
韩翔凌 《廊坊师范学院学报(自然科学版)》2010,10(6)
讨论了分批排序中工件具有学习效应、目标函数为极小化加权总完工时间的几个问题,分别就所有工件的基本加工时间都相等的情况给出了几种算法,并证明了算法的最优性. 相似文献
6.
考虑了两台同类机极小化总完工时间的分批排序问题,给出了计算复杂性为O(n3)的动态规划算法,并将此算法推广到了工件具有学习效应的情况. 相似文献
7.
8.
9.
主要研究了一种带拒绝费用的排序问题。目标函数是在不超过总拒绝费用阀值的前提下使最大完工时间最小。首先,证明了该问题是N P-难的;然后我们针对这个问题设计出了伪多项式时间的动态规划算法,并给出了FPTAS。 相似文献
10.
研究一类带批安装时间的平行机排序问题。工件按时间到达,在任何时刻,只知道当前已经就绪工件的信息。工件成批加工,同一批中工件的完工时间为批中最后一个工件的完工时间,每批开工前有一个固定的批安装时间。目标函数为极小化所有工件的总完工时间。主要考虑两个到达时间且工件加工时间都相等的特殊情形,给出竞争比为3/2的在线算法,并且有实例说明此界为紧致的。 相似文献
11.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p＞1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine's load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented. 相似文献
12.
13.
为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的. 相似文献
14.
Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications.
For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task
arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine
scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems
are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further
information about the tasks is available, which allows the improvement of the performance of the best possible algorithms.
Problems of this class are called semi-online ones. In this paper, the semi-online problemP2|decr|l
p (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum
of thel
p norm of every machine's load. It is shown thatLS algorithm is optimal for anyl
p norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problemsP2|online|l
p andP2|decr|l
p are presented.
Project supported by the National Natural Science Foundation of China (Nos. 10271110, 10301028) and the Teaching and Research
Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE, China 相似文献
15.
互联网技术的发展，硬件技术和通信技术的进步 共同加快了计算机领域前进的步伐。20世纪80年代 出现了并行计算，支持同步的算法、程序和体系结构相 继被开发。随后出现了分布计算，它要求各个处理机 之间能够协同计算，通过处理机间的通信共同解决问 题。网格计算技术的发展适 相似文献
16.
基于固定多出口链路网络,根据多目标优化理论方法,提出一种分割调度模型作为负载平衡的优化方法。动态选择最优路径,得到相应的网络链路多目标优化解。推导出了基于多约束条件下的循环择优路径算法。实验表明,算法适用于多链路各种负载下的流量优化,有效解决了宽带网络的大量用户接入及负载均衡问题。 相似文献
17.
对排课问题进行了描述,给出了解决排课问题的多种排课方法,并且对这些排课方法进行了分析和比较。在排课模型中运用本体知识创建了OWL排课本体,运用本体映射方法达到数据的同步,运用SWRL语法对本体进行约束,运用规则推理引擎JESS进行推理,结合排课算法给出了整体的排课模型架构。 相似文献
18.
Eucalyptus中基于能量消耗的调度算法研究 总被引：1，自引：0，他引：1
能量消耗是云计算研究中一个十分重要的问题,介绍了开源云项目Eucalyptus,分析了其核心调度算法及在考虑能量消耗的应用场景中存在的问题,利用虚拟机在线迁移技术提出了基于能量消耗的调度算法。实验证明,基于能量消耗的调度算法性能优于Eucalyptus现有的核心调度算法。最后总结了需要进一步提高的方面。 相似文献
19.
Under high loads, a multimedia cluster server can serve many hundreds of connections concurrently, where a load balancer distributes the incoming connection request to each node according to a preset algorithm. Among existing scheduling algorithms, round-Robin and least-connection do not take into account the difference of service capability of each node and improved algorithms such as weighted round-Robin and weighted least-connection. They also do not consider the fact that the ratio of number of TCP connections 相似文献