期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors 被引量：1

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors
原文传递
导出
摘要 In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound. In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.
作者 Dong-lei Du
机构地区 Faculty of Administration
出处 《Acta Mathematicae Applicatae Sinica》 SCIE CSCD 2005年第3期485-488,共4页 应用数学学报（英文版）
关键词 On-line algorithm randomized algorithm SCHEDULING PREEMPTION On-line algorithm, randomized algorithm, scheduling, preemption
分类号 O211.5 [理学—概率论与数理统计]
  • 相关文献

参考文献10

  • 1Bartal, Y., Fiat, A., Karloff, H., Vohra, R. New algorithms for an ancient scheduling problem. J. Comput.Syst. Sci., 51(3): 359-366 (1995).
  • 2Chen, B., Vliet, A.V., Woeginger, G.J. A lower bound for randomized on-line scheduling. Information Processing Letters, 51:219-222 (1994).
  • 3Chen, B.,Vliet, A.V., Woegingerl G.J. An optimal algorithm for preemptive on-line scheduling. Operations Research Letters, 18:127-131 (1995).
  • 4Graham, R.L. Bounds for certain multiprocessing anomalities. Bell System Tech. 45:1563-1581 (1966).
  • 5He, Y. Private communication, 2004.
  • 6He, Y., Zhang, G. Semi on-line scheduling on two identical machines. Information Processing Letters,62(3): 179-187 (1999).
  • 7Keilerer, H., Kotov, V., Speraaza, V., Tuza, M.R. Semi on-line algorithms for the partition problems.Operations Research Letters, 21:235-242 (1997).
  • 8Lawler, E.L., Lenstra, J.K., Rinnooy Kan,A.H.G., Shmoys, D.B. Sequencing and scheduling: Algorithms and complexity. Logistics of Production and Inventory, (S.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin,eds.), North-Holland, 445 522 (1993).
  • 9Liu, W.P., Sidney, JiB.,Vliet, A.V. Ordinal algorithms for parallel machine scheduling. Operations Research Letters, 18:223-232 (1996).
  • 10Mcnaughton, R. Scheduling with deadlines and loss functions. Management Sciences, 6:1-12 (1959).

同被引文献3

引证文献1

二级引证文献3

Acta Mathematicae Applicatae Sinica
2005年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部