Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines

来源 :浙江大学学报A(英文版) | 被引量 : 0次 | 上传用户:LanceXulei
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
The paper investigates a semi on-line scheduling problem wherein the largest processing time of jobs done by three uniform machines M1, M2, M3 is known in advance. A speed si (s1=1, s2=r, s3=s, 1≤r≤s) is associated with machine Mi. Our goal is to maximize Cmin-the minimum workload of the three machines. We present a min3 algorithm and prove its competitive ratio is max {r+ 1,(3s+r+ 1)/(1 +r+s)}, with the lower bound being at least max {2,r}. We also claim the competitive ratio of min3 algorithn cannot be improved and is the best possible for 1≤s≤2, r=1.
其他文献
为了快速准确进行西洋参和人参的品种鉴别,从主根横断面入手,采集其横断面的近红外光谱,分别从物理结构因素和化学因素方面对光谱进行了分析,选定特定波段进行物理因素主导建
明清时期的俗语辞书数量很多,文献书证方面的不足主要表现在书证与词目、书证与释义不一致;书证不确;无书证出处。对其进行研究可以客观总结明清俗语辞书的不足,并为当代语文
开发智能化的输入法是维吾尔文输入技术的一个发展方向,也是维吾尔文自然语言信息处理的基础性研究课题.该文根据雏吾尔文自身特点,对用户输入过程中所犯各种错误进行分析,设
求解最小Steiner树是NP难题,在通信网络设计、交通规划等工程实际中有着广泛的应用.利用表面活性剂溶液的物化特性,将溶液的最小表面张力特性采用平行板结构转化成二维平面的
针对回归问题,通过对bagging集成中的每个个体进行重新排序给出了一种修剪bagging集成的方法.该方法使用回归树作为基学习机,从排序后的回归树中选择一部分预测性能较好的个
对比研究世界著名大地震的震前预防及震后应急措施,分析这些地震产生巨大危害的原因,对其恢复重建过程中存在的问题进行总结.在科学发展观的统领下,从和谐与均衡的角度,以综
介绍了光纤陀螺在实际应用过程中的环境适应性问题,并从光子晶体光纤的结构特点出发,总结了光子晶体光纤的独特应用优势,指出将光子晶体光纤应用于光纤陀螺中可很好地解决温
2011年6月13日,国家自然科学基金委在西安进行了重点项目“直接驱动Z箍缩负载的快脉冲功率源关键技术研究”项目验收,并组织专家就电工学科脉冲功率技术学科的发展方向进行了
In-situ stress measurement using the hydraulic fracturing technique was made at Wanfu Coal Mine in Shandong Province,China.To solve problems caused by great mea
利用椭圆偏振光谱进行薄膜样品的测量数据分析拟合时,薄膜厚度与介电常数通常具有一定的关联性.不同色散模型的选取也会对拟合结果产生明显的影响,引起较大误差.介绍了唯一性