Optimal preemptive semi-online scheduling on two uniform processors

被引：8
|
作者：
Du, DL [1 ]
机构：
[1] Univ New Brunswick, Fac Adm, Fredericton, NB E3B 5V4, Canada
来源：
INFORMATION PROCESSING LETTERS | 2004年 / 92卷 / 05期
基金：
加拿大自然科学与工程研究理事会;
关键词：
on-line algorithms; uniform processor; scheduling; preemption;
D O I：
10.1016/j.ipl.2004.09.003
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We investigate a preemptive semi-online scheduling problem. Jobs with sizes within a certain range [1, r] (r greater than or equal to 1) arrive one by one to be scheduled on two uniform parallel processors with speed 1 and s greater than or equal to 1, respectively. The objective is to minimize makespan. We characterize the optimal competitive ratio as a function of both s and r by devising a deterministic on-line scheduling algorithm along with a matching lower bound, which also holds for randomized algorithms. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：219 / 223
页数：5
相关论文
共 50 条
  • [41] Extension of algorithm list scheduling for a semi-online scheduling problem
    Yong He
    György Dósa
    Central European Journal of Operations Research, 2007, 15 : 97 - 104
  • [42] Optimal algorithms for semi-online machine covering on two hierarchical machines
    Wu, Yong
    Cheng, T. C. E.
    Ji, Min
    THEORETICAL COMPUTER SCIENCE, 2014, 531 : 37 - 46
  • [43] Extension of algorithm list scheduling for a semi-online scheduling problem
    He, Yong
    Dosa, Gyoergy
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2007, 15 (01) : 97 - 104
  • [44] Several semi-online scheduling problems on two identical machines with combined information
    Cao, Qian
    Cheng, T. C. E.
    Wan, Guohua
    Li, Yi
    THEORETICAL COMPUTER SCIENCE, 2012, 457 : 35 - 44
  • [45] Semi-online scheduling problems on two identical machines with inexact partial information
    Tan, Zhiyi
    He, Yong
    THEORETICAL COMPUTER SCIENCE, 2007, 377 (1-3) : 110 - 125
  • [46] Semi-online Machine Covering on Two Uniform Machines with Known Total Size
    Z. Y. Tan
    S. J. Cao
    Computing, 2006, 78 : 369 - 378
  • [47] Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios
    Epstein, L
    OPERATIONS RESEARCH LETTERS, 2001, 29 (02) : 93 - 98
  • [48] Semi-online machine covering on two uniform machines with known total size
    Tan, Z. Y.
    Cao, S. J.
    COMPUTING, 2006, 78 (04) : 369 - 378
  • [49] An optimal on-line algorithm for preemptive scheduling on two uniform machines in the lp norm
    Shuai, Tianping
    Du, Donglei
    Jiang, Xiaoyue
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, PROCEEDINGS, 2008, 5034 : 316 - +
  • [50] On-line and semi-online scheduling for flow shop problems on two machines
    Yang, Ming
    Lu, Xiwen
    OPTIMIZATION, 2013, 62 (04) : 499 - 507
12345