【摘 要】
:
本文讨论了带服务器的两台平行机半在线排序问题,和经典的平行机排序不同,每个工件加工之前必须由服务器先将工件安装在机器上。我们讨论了以工件最大完工时间为目标函数时,四种
论文部分内容阅读
本文讨论了带服务器的两台平行机半在线排序问题,和经典的平行机排序不同,每个工件加工之前必须由服务器先将工件安装在机器上。我们讨论了以工件最大完工时间为目标函数时,四种不同条件的半在线排序模型,分别得到了问题的下界并设计了近似算法。
(1)对P2,S1 | s=1,Known largest job |Cmax问题,证明此问题的下界不小于(5-(5))/2≈1.382,并设计了一个竞争比为5/3的近似算法。
(2)对工件加工和安装时间之和∑ni=1(1+pi)=2P已知的P2,S1| s=1,Known sum | Cmax问题,证明了该问题的下界不小于4/3,给出了一个竞争比为5/3的近似算法。
(3)对所有工件的加工时间位于一个有限区间[P,rP]内的P2,S1|s=1,Intrerval |Cmax问题,这里P>0,r≥1,证明了当r≥2时,问题下界不小于3/2;当1≤r<2时,问题下界不小于(1+r)/2,并证明了用LS算法求解这个问题的竞争比为8/5。
(4)对带有一个缓冲区的P2,S1|s=1,buffer|Cmax问题,主要分析了此问题的下界,证明其下界不小于3/2。
其他文献
在轨道运输中,轨道端头处的车辆停车问题很难控制,矿车经常从轨道端头处出轨,给运输和生产造成很大的影响。吉林省珲春煤业有限公司八连
In rail transportation, the probl
对于只有加工时间的流水作业问题,已经进行了比较详细的研究,得出了一系列的结果。然而,在实际应用中,工件不是只有加工时间,而且还会有调整时间和移走时间。调整时间和移走时间从
本文主要研究了一维Tyson反应扩散方程的Hopf分支及小范围周期解产生的充分条件.在研究一维Tyson反应扩散方程之前,首先介绍了Tyson反应的化学背景,方程的建立,以及相应常微分方
荣优华占是2012年通过江西审定的中晚稻兼用优质杂交水稻新组合,根据其双亲特征特性,总结了该组合在赣南地区秋制高产技术。
Rongyouhuazhan is a new combination of good
最优化方法,就是为了使系统达到最优的目标所提出的各种求解方法,它是在第二次世界大战前后,在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。当今,该方法广泛应用于经济、
本文研究的是带服务器的平行机排序问题,它是经典平行机排序问题的一个推广,其中每个工件在由机器加工之前都必须由一个服务器安装在一台机器上,而一个服务器在同一时间只能安装
本文着重研究了如下Kirchhoff型强阻尼波动方程和热方程的耦合方程组:其中β,β为常系数,Ω为有界区域。 已往关于非线性Kirchhoff型强阻尼波动方程的结果中,关于解的整体存在
本文从著名的AKNS方程族的两个Darboux变换出发,获得一个新的含有两个离散变量的全离散可积偏差分方程,并构造了其有限亏格解. Darboux变换是求解孤立子方程精确解的有效
在我国,有相当数量的既有结构使用性能己严重退化或因设计疏忽或施工失误等导致其结构存在潜在隐患。这就要求我们对这些结构的安全性、实用性和耐久性给出客观的、定量的评价