Online algorithms for scheduling with machine activation cost on two uniform machines

来源 :浙江大学学报A(英文版) | 被引量 : 0次 | 上传用户:anysion888
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated,and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.
其他文献
连动结构间的“来、去”似乎很多情况下可以换用,实际上却有较为明显的倾向性。陈贤在曹艳芝认识的基础上,对人称代词宾语与“来、去”的关系做了进一步的考察,讨论了时态、
该文根据语音合成与识别等语音应用研究的需求,从文本分析模块入手,利用“雏吾尔语语音声学参数库”,选择了包含鼻音m、n和(n)的单音节以及多音节词,提取它们的声学参数并进
作为一种不可逆的热力学过程,腐蚀疲劳的点蚀演化受到体系应变能、表面能和电化学能的共同影响.基于能量学原理,对腐蚀疲劳点蚀演化过程中的能量问题进行探索性研究.引入双变
在确保安全的前提下,经济性是核电厂的重要目标之一.VVER-1000型反应堆某些非并网运行的工况,如换料后重新临界、热停堆及临界、试验后返临界等操作,在操作所占用的时间、原
For intelligent transportation surveillance, a novel background model based on Mart wavelet kernel and a background subtraction technique based on binary discre
In order to investigate the temperature distribution, a three-dimensional finite element model (FEM) was developed to simulate the temperature regime in the cha
Mechanism interaction between cracks with different orientation angles is analyzed based on the principle of superposition and a flattening method. It is found
By using the theory of planar dynamical systems to the ion acoustic plasma equations, we obtain the existence of the solutions of the smooth and non-smooth soli
This paper presented the methods of reducing the compaction segregation of asphalt layer by improving the operating characteristics of roller and paver. The fit
Cu-based powder metallurgy brake materials are used for aircraft widely and successfully. The characteristics of worn surface of Cu-based powder metallurgy brak