【摘 要】
：
在传统排序问题中,总是假设工件信息在排序之初都已经全部知道.这些问题称之为离线(off-line)排序问题.在实际应用中,有些工件的信息在一开始往往是不知道的,而是随着时间的
论文部分内容阅读
在传统排序问题中,总是假设工件信息在排序之初都已经全部知道.这些问题称之为离线(off-line)排序问题.在实际应用中,有些工件的信息在一开始往往是不知道的,而是随着时间的推移而逐个释放.这些问题称之为在线(on-line)排序问题.本文研究带有链约束chains1,chains2,…,chainsn工件的平行机排序问题.链的到达时间为rj,j=1,2,…,n.工件一旦开始加工,就不能被打断,直到该工件被加工完毕。目标函数是最小化机器完工时间的平方和以及最小化最大延误时间.本文的主要结果如下: (1)研究了每一条链的长度都为1的离线排序问题.在0时刻,所有的工件已到达.目标函数是最小化两台机器的完工时间的平方和.用三参数法该问题可表示为P2||chaini|=1|.我们利用修改的LPT算法(Modified-LPTAlgorithm)求解该问题,并证明该算法的执行比不大于1+1/81。 (2)研究了单位长度工件且链在整数时刻到达的2台恒同机上的在线排序问题.目标函数是最小化两台机器的完工时间的平方和.用三参数表示为P2|pj=1,chainsi released at.证明了任一实例在任意算法下竞争比不小于5/4,而任意的稠密算法(Dense Algorithm)的竞争比都渐近地趋于2,并给出该问题的一个最好可能在线稠密算法。 (3)研究了等长工件在链约束下单机在线排序问题.每一个到达时刻ri到达的工件为一组链chainsi,其上面的工件Jj的加工时间pj和工期qj满足条件CD:若在链chainsi上工件Jj(i)为工件Jk(i)的前任,那么满足pj(i)=pk(i)=p≥qj≥qk.目标函数是最小化最大延误时间.用三参数可表示为1|pj=p,chainsi,releasedat ri,CD|Lmax.证明了任一实例在任意算法下竞争比不小于,并给出了一个最好可能在线算法。
其他文献
文章首先探讨了公共危机信息准备的内涵,然后将公共危机信息准备核心能力归纳为规划、态势感知、信息资源管理、执行四个大类共十七种具体能力,最后结合危机准备周期理论论述
The Hoek-Brown criterion was introduced in 1980 to provide input for the design of underground ex-cavations in rock. The criterion now incorporates both intact
Excavation damage under high in situ stress depends largely upon the potential block size associated with any violent ejection. The size and shape of the dynami
改革开放以来,我省外商投资企业迅猛发展,规模不断壮大,到2002年底,全省已开业、投产的外商投资企业达2.8万家,中方从业人员390多万人。近年来,我省各级党委和外商投资企业党
薛毅1923年出生于河北完县(今顺平县)城区一个贫民家庭。15岁投身到抗日战争的洪流,16岁加入中国共产党。他虽只求学至高小毕业,但勤奋好学,在战争年代就已写出不少生动的宣
分圆Temperley-Lieb代数[4],是Temperley-Lieb代数[6]的推广.这类代数既可以用生成元和关系定义,也可以用图来定义.受到J.Eyang[1]关于Temperley-Lieb代数工作的影响,我们将
Rock mechanics plays a critical role in the design and construction of hydroelectric projects including large cavs under high in situ stress, deep tunnels with
计数是组合分析的基本内容。在解决各种各样的计数问题中，人们引进了许多方法和工具，比如生成函数。建立计数序列的生成函数是解决计数问题的常用方法之一，它也有许多技巧和方法
本文首先研究了在BR=B（0,R）（?） RN,N≥3的球域上,形如的半线性椭圆方程在D’（BR）中解的存在性,其中常数β＞0,q＞1,0≤c≤c0,这里c0是Hardy不等式中的最佳常数.我们用变分法、山路引理
本文切合目前微分方程分支理论的研究状况，对连续的高维非线性动力系统分支理论中尚很少涉及却更一般的异维环分支问题进行了较深入的理论分析，并运用分支理论解释了一类癌症模