首页 | 本学科首页   官方微博 | 高级检索  
    检索          
共有20条相似文献,以下是第1-20项 搜索用时 187 毫秒

1.  流水作业两台机器的成组排序的一个新问题  
   谷会昆《浙江大学学报(理学版)》,2005年第32卷第3期
    研究了两台流水作业机器有调整时间的成组排序问题.首先对NP-难的F2|S,GT|∑WijCij给出了一个近似算法,证明了它的最坏情况界为2.然后讨论了F2|5,GT|Cmax在线排序,并给出了一个最坏情况界为2的近似算法,并证明不可能存在最坏情况界小于2的在线近似算法.    

2.  有使用限制的二台机器流水作业问题  
   杨名  鲁习文《运筹学学报》,2011年第15卷第3期
   研究有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断.讨论两台机器上均有使用限制离线问题的可近似情形,并给出性能比为3/2的近似算法.同时还考虑在第二台机器上存在一个不可用时间段情况下的半在线问题,给出一个竞争比为3/2的半在线算法.    

3.  平行机中关于关于同类机近似算法的研究  
   陈祥伟《应用数学学报》,2004年第27卷第4期
   我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.    

4.  带准备时间的两台同类机已知工件总加工时间的半在线排序问题的近似算法  
   华荣伟  洪哲《浙江大学学报(理学版)》,2008年第35卷第4期
   主要研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,目标函数极小化最大机器完工时间和极小化最大工件完工时间.对此问题给出了竞争比为√2的近似算法,并证明了不存在竞争比小于1+√3/2的近似算法.    

5.  机器带准备时间的三台平行机排序问题的线性时间算法  被引次数:11
   范静  杨启帆《浙江大学学报(理学版)》,2005年第32卷第3期
    对于机器带准备时间的平行机排序问题,研究了3台机器的情况,给出了线性时间的对偶阈值算法族DA3(ε)(其中ε为可选参数),并证明了当ε=1/5时,对偶阈值算法DA3(1/5)的近似比为6/5,且该界为紧的.这是到目前为止最小且时间复杂性为线性时间的算法.    

6.  带准备时间的两台同类机半在线排序的近似算法  被引次数:1
   华荣伟《浙江大学学报(理学版)》,2007年第34卷第5期
   研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,分别讨论了极小化最大机器完工时间和极小化最大工件完工时间这两个目标函数,对这两个目标函数给出了竞争比为3/2的近似算法,并证明了不存在竞争比小于√2的近似算法    

7.  带准备时间的自由作业排序问题—最坏性能比分析  被引次数:2
   杜玉祥 杜东雷《高校应用数学学报(A辑)》,1997年第2期
   本文研究了一类自然的排序问题,带准备时间的自由作业排序。在机器台数任意的情况下,证明了一个简单的贪婪算法的最坏性能比不超过2,并猜想该算法的临界为2-1/m,其中m为机器台数。特别当m=2时,证明了该算法的最坏性能比恰为3/2。    

8.  带机器准备时间的已知工件总加工时间半在线问题  
   罗润梓  孙世杰  何龙敏《南昌大学学报(理科版)》,2010年第34卷第1期
   考虑带机器准备时间的已知工件总加工时间半在线问题。首先考虑P2,ri|sum|Cmin问题,给出Prsum算法并证明此算法的竞争比为23,且是最优算法;然后考虑Q2,ri|sum|Cmax问题,给出Qrsum算法并证明此算法的竞争比为2,同时给出此问题的一个下界1+3~(1/2)/2。显然Qrsum算法的竞争比与最优算法的竞争比之差小于0.048 2。    

9.  单台机以总完工时间为目标的批排序问题  
   严羽洁《高校应用数学学报(A辑)》,2017年第32卷第4期
   研究单台机,工件加工时间相等,大小不同的批排序问题,给出了一个最坏情况界为9+√3/6≈1.7817的多项式时间近似算法,并证明了即使工件总大小不超过2,该问题也不存在FPTAS,除非P=NP.    

10.  资源有限的加权总完工时间单机排序问题  被引次数:1
   唐恒永  赵琨《运筹与管理》,2004年第13卷第3期
   本讨论资源有限的加权总工时间单机排序问题,对现在仍为OPEN问题1|pj=bj-ajuj,∑uj≤U|∑wjCj给出了一个有关最优解中最优资源分配的重要性质,并利用该性质分别给出了三种情况bj=b,wj=w,aj=a;bj=b,wj=w,uj=u;aj=a,wj=w,uj=u的最优算法。    

11.  已知工件最大加工时间的平行机排序问题  被引次数:1
   吴用  黄宜坤  杨启帆《浙江大学学报(理学版)》,2008年第35卷第1期
   研究了已知工件最大加工时间,目标为极小化最大机器负载的半在线平行机排序问题.证明了对于一般的m(〉6)台机器,任意的半在线算法的竞争比至少是(√33+3)/6.同时还设计了一个半在线算法,算法的竞争比为2-1/(m-1).    

12.  无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案  被引次数:1
   李曙光  李国君  赵浩《运筹学学报》,2004年第8卷第4期
   本文考虑n个工件的无限批量机器调度问题.一台机器可以同时加工B≥n个工件.每个工件具有一个正权因子、一个释放时间和一个加工时间.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.对于最小化加权完工时间和问题,本文给出了第一个多项式时间近似方案(PTAS).对任意给定精度,该算法的运行时间为线性的.    

13.  具有服务等级的三台平行机排序问题  被引次数:1
   周萍  蒋义伟  华荣伟《浙江大学学报(理学版)》,2007年第34卷第4期
   考虑带服务等级的三台平行机排序问题.预先赋予每台机器和每个任务一个服务等级(grade of service)标号.每个任务只能被某台服务等级不高于该任务服务等级的机器加工.目标是最小化最大机器完工时间.本文给出了求解这个问题的算法.并证明算法的最坏情况界不超过5/4+(1/2)^k,其中k是算法中预先给定的迭代次数.已有的算法仅为3/2.    

14.  关于平行机排序问题的两点注记  
   陈志龙  赵小平《运筹学学报》,1992年第1期
   本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,[_i≡p|∑w_ic_i 提出 O(n~2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m})上加工.已知每个工件必须且仅须在一台机器上加工一次,并且加工时不允许中断.工件 i(i∈N)在不同机器上加工时间不变,设为 p_i,罚权 w_i 也与机器无关,p_i 和 w_i 皆为非负实数.我们将多台机器加工工件的一个安排称为一个时间表.当时间表π确定后,记工件 i 的完工时间为 c_i(π    

15.  带机器准备时间的平行机ordinal排序及近似算法  被引次数:1
   谈之奕  何勇《应用数学学报》,2002年第25卷第2期
   本文研究带机器准备时间的m台平行机ordinal在线排序问题。讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法。对第一个目标,我们得到了3/2的下界和最坏情况界为2-1/m的近似算法。对第二个目标,我们得到了最坏情况为m的最好近似算法。我们还对一些特殊情况进行了分析。    

16.  带机器故障的两台机带权误工数排序问题  
   胡觉亮  张玮虹  蒋义伟《高校应用数学学报(A辑)》,2010年第25卷第4期
   讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.    

17.  极小化最大完工时间的单机分批加工问题  
   李曙光  杨振光  亓兴勤《运筹学学报》,2006年第10卷第1期
   本文考虑极小化最大完工时间的单机分批加工问题.设有n个工件和一台批加工机器.每个工件有一个释放时间和一个加工时间.批加工机器可以同时加工b(b    

18.  带机器准备时间的平行机排序问题  
   李伟东  李建波  李建平  张同全《系统科学与数学》,2010年第30卷第4期
   研究了带机器准备时间的$m$台平行机排序问题,设计出了一个多项式时间近似方案(PTAS),并给出了一个机器数$m$为固定常数的情形下的全多项式时间近似方案 (FPTAS).    

19.  一类带平行机的两阶段柔性流水调度近似算法  
   张明会  韩鑫《应用数学学报》,2018年第3期
   本文研究一类柔性流水调度与平行机调度相结合的两阶段流水调度模型,模型中第1阶段有1台机器,第2阶段有m台同构并行机,每个任务在第2阶段需要size_i台机器同时并行执行.目标是所有任务都完成的完工时间最小化.该模型已被证明出是强NP难的,并给出了在某种特定情况下近似比为3的近似算法.本文首先详细分析了前人近似算法基本过程,给出该算法近似比分析的局限性;接着给出了一个近似比为3的算法,摒弃了前人给出的近似比为3时的约束条件;最后研究了当第2阶段机器数为2和3时的两种特定情况,采用列表调度思想,给出了近似比为2.5和2.67的近似算法.    

20.  带复合信息的三台平行机半在线排序问题  
   闵啸《运筹学学报》,2006年第10卷第1期
   本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题. Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5/4的最优半在线算法.本文将其情况推广到三台机器,给出竞争比为4/3的半在线算法,并得到一个11/9的问题下界.    

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

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