Semi-Online Scheduling with Machine Cost

来源 :计算机科学技术学报 | 被引量 : 0次 | 上传用户:llz364088963
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
For most scheduling problems the set of machines is fixed initially and remainsunchanged for the duration of the problem. Recently Imreh and Nogaproposed to add theconcept of machine cost to scheduling problems and considered the so-called List Model problem.An online algorithm with a competitive ratio 1.618 was given while the lower bound is 4/3. Inthis paper, two different semi-online versions of this problem are studied. In the first case, it isassumed that the processing time of the largest job is known a priori. A semi-online algorithmis presented with the competitive ratio at most 1.5309 while the lower bound is 4/3. In thesecond case, it is assumed that the total processing time of all jobs is known in advance. Asemi-online algorithm is presented with the competitive ratio at most 1.414 while the lowerbound is 1.161. It is shown that the additional partial available information about the jobsleads to the possibility of constructing a schedule with a smaller competitive ratio than that ofonline algorithms.
其他文献
The copolymerization of styrene (St) with maleic anhydride (MAh) under gamma radiation at room temperature inthe presence of benzyl dithiobenzoate (BDTB) was fo
A highly regioselective O-deacetylation of taxanes at C-5 position was accomplished by treatment with t-BuOK and a possible mechanism was proposed.
Mononuclear complex {[Cu(N-men)2(cda)2]([Cu(N-men)2]((ClO4)2} was synthesized by sodium carbamyldicyanomethanide Na(cda), N-methylethylenediamine and hydrate co
A new phase, the rare earth complex oxide SnDy2O4 was synthesized by the thermal decomposition of its oxalate precursor that was prepared by rheological phase r
用450W高压汞灯照射H3PMo12O40·5H2O和(Bu4N)Br(TBA)的DMF(N,N-二甲基甲酰胺)溶液,合成了12-钼磷酸四丁基铵杂多蓝(Bu4N)4[PMo12O40]·2DMF·H2O,用元素分析,IR,固体漫反射电子光谱,
The quantum correspondence of the very peculiar phenomenon of classical chaos-the exponential instability of motion can be characterized by the initially expone
A scheme for probabilistic teleporting an unknown two-particle state of general formation by partly pure entangled four-particle state is proposed. It is shown
从贯叶连翘( Hypericum perforatum L.)地上部分的80%乙醇提取物中分离得到1个新的黄酮苷和6个已知黄酮类化合物.采用红外光谱、紫外光谱、质谱和核磁共振光谱等波谱技术测得
Polysiloxane bearing pendant quatemary ammonium groups (PSI) was used to modify the surface properties ofepoxy resins. In the cured resin, PSI formed the disper
The phthalate esters such as DMP, DEP, DBP and DEHP in air, soil and plant samples in plastic film greenhouse were clean up with fine silica gel column and dete