论文部分内容阅读
本文研究的是若干平行机排序问题的算法设计和分析，主要内容分为六章。第1章至第4章讨论了四个机器有使用限制的两台同型机半在线排序问题，其在线模式为列表在线。第5章讨论了机器有使用限制的两台同类机排序问题。第6章分析了经典的平行机排序问题的AKK算法。
第1章讨论了已知工件最大加工时间的半在线问题。首先研究了只有一台机器有使用限制的情况。令机器M1上[B，F]时间段不可用，工件最大加工时间为Pmax。通过比较Pmax和B的大小关系，考虑PmaxB三种情况，分别证明了此问题的下界为3/2、4/3和1+a(其中a=(√5-1)/2)。然后对应这三种情况分别给出了三个半在线算法，并证明了其竞争比都达到了问题的下界，因此都是最优算法。其次研究了两台机器上各有一段不可用时间，且不可用时间互不重叠的情况。令机器M1、M2分别在[B1，F1]、[B2，F2]时间段不可用，其中B2≥F1。本文考虑了Pmax≤B1、B1B2的三种情况，分别证明了此问题的下界为2、5/3和7/5。然后对应这三种情况分别给出了三个半在线算法，证明了算法的竞争比都是2，因此在Pmax≤B1时该算法是最优算法。
第2章讨论了已知工件总加工时间的半在线问题。令机器M1上[B，F]时间段不可用，工件总加工时间P=2。通过比较B和总加工时间的关系，本文考虑了B≥4/3和B<4/3两种情况，证明了问题的下界分别是4/3和5/3。对于B≥4/3的情况本文构造了一个半在线算法，并证明其竞争比为4/3。对于B<4/3的情况，本文进一步讨论了三种子情况，分别给出了三个半在线算法并证明了其竞争比均为5/3。因此综合这四个算法可得此问题的最优算法。
第3章讨论了已知工件加工时间在一个区间内的半在线问题。令工件的加工时间所属的区间为[1，r](r≥1)，机器M1上[B，F]时间段不可用。通过比较B和加工区间的关系，证明了当B≥1时问题的下界为2-1/(r+1)，当B<1时如果r≥2，则问题的下界为3/2，如果1≤r<2则问题的下界为(r+1)/2。我们将经典的LS算法应用到此问题，证明了除了B<1且1≤r<2的情况之外，LS算法都是最优的半在线算法。
第4章讨论了带有缓冲区的半在线问题，其中一台机器上有使用限制，而缓冲区可容纳一个工件。对此问题本文证明了其下界为2，并给出了一个最优的半在线算法。
第5章讨论了机器有使用限制的两台同类机排序问题。令机器M1、M2的速度分别为s1=1和S2∈(0，1)。对于只有机器M1上[B，F]时间段不可用的情况，证明了离线的LPT算法的最坏情况界为max{3/2，1/S2}。对于相应的在线问题，证明了当(√5-1)/2≤s2<1时问题的下界为(2+s2)/(1+s2)，当0
其他文献
非单调推理是人工智能中重要的知识表示及推理方法，主要处理不完全知识下的推理问题。但非单调推理系统不能完全解决自身存在的冲突以及由新知识引入的冲突问题，这使得一个非单
本论文由三个主要部分组成。
第一部分是预备知识。
先介绍一些基本概念.包括熵数与特征值,lp空间与niebel在Rn上定义的B型空间与F型空间,并阐述了熵数与特征值之
创新是一个民族的灵魂,是一个国家兴旺发达的不竭动力。随着企业改革的不断深入和发展,要求企业及其员工所必备的重要能力之一就是创新能力,作为一名政工干部,如果不思进取
北京:出台“平安示范社区”标准为深入贯彻社会治安综合治理“预防为主”方针,进一步严密基层治安防范工作,给广大市民创造安全、稳定、和谐的人居环境,首都综治委在全市启动
3月22日,赤峰市红山区新华路商业步行街热闹非凡,全国“百城万店无假货”活动示范街挂牌仪式在这里隆重举行。采访中,记者看见赤峰购物城几家商户高悬“共产党员诚信户”红
已经知道，对左-右Noetherian环R和S，如果Rωs是一个余倾斜双模，则Rω和ωs的内射维数均不大于n当且仅当每个有限生成左R-模和每个有限生成右S-模的广义Gorenstein维数均不大于n
崔泽贤今年已经72岁,在晋西北黄土高原国家级贫困县岢岚从教四十多年,先后担任教师和联校校长等职务。1989年退休后,在岢岚办起图书室,并建起文化长廊,辟有“新书介绍”、“
在1923年，F.G.Tricomi开始研究Tricomi方程，处理混合椭圆和双曲的边值问题。在1945年，F.I.Frankl把Tricomi问题推广到Chaplygin方程。在1953年，M.H.Protter使用基于Friedrichs的a
本文中，我们给出一个算法用来计算H10空间中一个非凸函数的凸投影.在一维的情况下，我们给出了一个快速的贪心算法，并且证明了该算法得到的结果就是原泛函的最小值，同时也是目标函
投射模和平坦模是同调代数中经常遇到的研究对象，它们在同调代数的研究中起着非常重要的作用。Gorenstein投射模和Gorenstein平坦模分别是投射模和平坦模的推广，它们也是同调代