首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到18条相似文献,搜索用时 109 毫秒
1.
因实际生产中调度问题的规模很大,分析其近似算法的绝对性能比很难,有时甚至不可行,所以研究近似算法的渐近性能比就很有必要,本文针对多机Flowshop加权完成时间调度问题,使用单机松弛和概率分析方法,证明了基于加权最短处理时间需求的启发式算法是渐近最优的.  相似文献   

2.
最近Chou、Queyranne和Simchi—Levi,Liu分别证明了恒速平行机调度问题和Flow shop调度问题的基于有效作业加权最短处理时间的启发式算法是渐近最优的。本文使用分组机器模型的方法证明:即使对于多机Flow shop加权完成时间调度问题,基于有效作业加权最短处理时间的启发式算法也是渐近最优的。关键词调度,多机Flow shop调度,启发式算法,渐近最优分析  相似文献   

3.
局内装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用.提出一个新的局内线性算法MAMOV, 算法中采用"物品移动模型",当新物品到达时,允许首次入箱后的固定数目的物品再次移动;证明MAMOV算法的最坏情况渐近性能比1.25,该算法最坏情况渐近性能比低于同类算法最坏情况渐近性能比的下界值.  相似文献   

4.
主要研究双层无线传感网络模型,即数据信息流只能在传感器和中继器或中继器和中继器之间传输,而不能在传感器之间传输。近似算法基于两个子问题:k圆盘覆盖问题和单层传感网络的k连通问题,而后在部分中继器周围设置“等六边形”结构的中继器点,最终达到整个网络的3-连通水平。该算法的最终性能比为8α+β,其中α为k圆盘覆盖近似算法的性能比,β为单层传感网络的k连通近似算法的性能比。  相似文献   

5.
本文研究有n个作业需在5个处理机中心进行加工,处理机中心i由l1个恒速机组成的非抢占式多机flow shop调度最小和问题.每个作业有s个工序,每个工序需在对应的处理机中心的任一台机器上加工处理,作业到达前不能加工,所有作业通过处理机中心的路径相同.目标是确定一个作业在每个处理机中心机器上的可行调度序列,使所有作业在最后处理机中心的加权完成时间总和最小化.在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时,通过特殊flow shop调度松弛方法,我们证明该问题在作业数趋于无穷时,一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的.  相似文献   

6.
建立了多参数最小支撑树问题(RMST)的模型,并证明该问题是NP-完全的。利用经典Greedy算法,给出了该问题的一个近似算法,并分析了该近似算法的性能比,证明了所给出的界是紧的。  相似文献   

7.
互联网信息组织和规划中的带拒绝装箱问题   总被引:4,自引:0,他引:4  
何勇  谈之奕  任峰 《计算机学报》2003,26(12):1765-1770
讨论如下定义的带拒绝装箱问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和罚值.物品可以放入箱子也可被拒绝放入箱子.如果将物品放入箱子,则使该箱剩余长度减少.一旦需将某一物品放入某一箱中,而该箱的剩余长度不够时,则需启用新箱子.如果物品被拒绝放入任何箱中,则产生惩罚.问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小.该问题是一个新的组合优化问题,来源于内部互联网的信息组织和规划.该文首先给出一个最优解值的下界估计,它可用于分枝定界法求最优解.由于该问题是强NP-难的,该文进一步研究它的离线和在线近似算法的设计与分析.文中给出一个离线算法,其绝对性能比为2;同时给出一个在线算法,其绝对性能比不超过3,渐近性能比为2,还对算法性能比的下界进行了讨论.  相似文献   

8.
讨论了多服务中心设置问题的局部搜索近似算法及其在实际计算中表现出的新性质。首先对局部搜索算法求解多服务中心设置问题的实际近似性能比给出了一个针对性分析结果,然后编程实验对局部搜索求解算法的求解时间和求解质量进行了探讨。  相似文献   

9.
随着网络技术的不断发展,网络上可供共享的资源越来越丰富,集群技术的兴起更是扩展了并行计算的环境.这种环境下系统中很多任务依赖于多种资源(或多个处理机),称这样的任务为多处理机任务.本文研究基于多处理机任务的调度模型Pm{fix}Cmax,当m≥3时,这类调度问题是强NP—难的,所以只能寻求有好的逼近性能的多项式时间近似算法.文中给出了当m=4或5时线性时间的近似调度算法,优于目前已有的最好结果,最后我们还讨论了当k≥3时的一般调度问题.  相似文献   

10.
多处理机任务调度问题P4|fix|Cmax(m≥=)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.  相似文献   

11.
We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.  相似文献   

12.
宋强 《控制理论与应用》2020,37(10):2242-2256
以异构并行机调度问题为研究对象,考虑了一类以优化总加权完工时间和加权延误总和的调度问题。首先,基于问题描述构建了该问题的混合整数规划模型。其次,提出了混合多目标教-学优化算法。在算法设计中,结合问题的特点设计序列编码方法,并采用分解技术来实现多目标调度问题的求解。此外,该算法通过融合多种交叉算子来定义个体进化过程,并通过与变邻域搜索算法的混合来提升其优化效果。最后,给出了仿真实验与分析,测试结果验证了多目标教-学优化算法求解该调度问题的优越性。  相似文献   

13.
We point out an error in the algorithm for the Load Balanced Semi-Matching Problem presented by C.P. Low [C.P. Low, An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs, Information Processing Letters 100 (2006) 154-161]. This problem is equivalent to a parallel machine scheduling problem subject to eligibility constraints, in which each job has a pre-determined set of machines capable of processing the job.  相似文献   

14.
一种自适应的动态网格任务调度算法   总被引:1,自引:0,他引:1  
张秋余  柴进 《计算机应用》2006,26(10):2267-2269
GRACE网格资源框架是一个分布式、可计算的经济学体系框架,针对框架中分配网格资源问题,引入近视算法,提出了一种自适应的动态网格任务调度算法。该算法通过在调度过程中动态监测系统的负载平衡度,自适应地选择任务调度策略。经模拟试验证明,该调度算法提高了任务的调度成功率。  相似文献   

15.
This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.  相似文献   

16.
We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.  相似文献   

17.
随着大规模定制的市场需求日趋显著,赛如生产系统(Seru production system,SPS)应运而生,逐渐成为研究和应用领域的热点.本文针对带有资源冲突的Seru在线并行调度问题进行研究,即需要在有限的空间位置上安排随动态需求而构建的若干Seru,以总加权完工时间最小为目标,决策Seru的构建顺序及时间.先基于平均延迟最短加权处理时间(Average delayed shortest weighted processing time,AD-SWPT)算法,针对其竞争比不为常数的局限性,引入调节参数,得到竞争比为常数的无资源冲突的Seru在线并行调度算法.接下来,引入冲突处理机制,得到有资源冲突的Seru在线并行调度算法,αAD-I(α-average delayed shortest weighted processing time-improved)算法,特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同.最后,通过实验,验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性.  相似文献   

18.
随着大规模定制的市场需求日趋显著,赛如生产系统(Seru production system,SPS)应运而生,逐渐成为研究和应用领域的热点.本文针对带有资源冲突的Seru在线并行调度问题进行研究,即需要在有限的空间位置上安排随动态需求而构建的若干Seru,以总加权完工时间最小为目标,决策Seru的构建顺序及时间.先基于平均延迟最短加权处理时间(Average delayed shortest weighted processing time,AD-SWPT)算法,针对其竞争比不为常数的局限性,引入调节参数,得到竞争比为常数的无资源冲突的Seru在线并行调度算法.接下来,引入冲突处理机制,得到有资源冲突的Seru在线并行调度算法,αAD-I(α-average delayed shortest weighted processing time-improved)算法,特殊实例下可通过实例归约的方法证明其竞争比与无资源冲突的情况相同.最后,通过实验,验证了在波动的市场环境下算法对于特殊实例与一般实例的优越性.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号