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

Online scheduling of two type parallel jobs on identical machines

Online scheduling of two type parallel jobs on identical machines
下载PDF
导出
摘要 In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using ＂temporary schedule＂. In this paper we consider an online scheduling of parallel jobs with preemption on identical machines, where jobs arrive over time. The objective is to minimize the makespan. For the problem that jobs have only two possible widths mj = 1 or m, we present an optimal online algorithm by using ＂temporary schedule＂.
作者 郭首玮 康丽英
机构地区 Department of Mathematics
出处 《Journal of Shanghai University(English Edition)》 CAS 2010年第6期396-399,共4页 上海大学学报（英文版）
基金 Project supported by the National Natural Science Foundation of China (Grant No.10971131) the Shanghai Leading AcademicDiscipline Project (Grant No.S30104) the Innovation Foundation of Shanghai University (Grant No.SHUCX091077)
关键词 SCHEDULING parallel jobs PREEMPTION online algorithm competitive analysis scheduling parallel jobs preemption online algorithm competitive analysis
分类号 O223 [理学—运筹学与控制论]
  • 相关文献

参考文献11

  • 1GRAHAM R L,LAWLER E L,LENSTRA J K,RINNOOYKAN A H G.Optimization and approximation in deterministic sequencing and scheduling:A survey[J].Annals of Discrete Mathematics,1979,5(2):28-326.
  • 2DROZDOWSKI M.On the complexity of multiprocessor task scheduling[J].Bulletin of the Polish Academy of Sciences,Technical Sciences,1994,43(3):381-392.
  • 3JOHANNES B.Scheduling parallel jobs to minimize the makespan[J].Journal of Scheduling,2006,9(5):433 452.
  • 4BLA(Z)EWICZ J,DELL'OLMO P,DROZDOWSKI M,MACZKA P.Scheduling multiprocessor tasks on parallel processors with limited availability[J].European Journal of Operational Research,2003,149(2):377389.
  • 5BLA(Z)EWICZ J,DRABOWSKI M,W?GLARZ J.Scheduling multiprocessor tasks to minimize schedule length[J].IEEE Transactions on Computers,1986,35(5):389393.
  • 6NAROSKA E,SCHWIEGELSHOHN U.On an on-line scheduling problem for parallel jobs[J].Information Processing Letters,2002,81(6):297-304.
  • 7SHMOYS D,WEIN J,WILLIAMSON D.Scheduling parallel machines on-line[J].SIAM Journal on Computing,1995,24(6):1313-1331.
  • 8CHEN B,VESTJENS A P A.Scheduling on identical machines:How good is LPT in an on-line setting[J].Operations Research Letters,1997,21(4):165-169.
  • 9YE D,ZHANG G.On-line scheduling of parallel jobs in a list[J].Journal of Scheduling,2007,10(6):407-413.
  • 10HURINK J L,PAULUS J J.Online scheduling of parallel jobs on two machines is 2-competitive[J].Operations Research Letters,2008,36(1):51-56.
Journal of Shanghai University(English Edition)
2010年 第6期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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