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 条
  • [21] Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
    György Dósa
    Armin Fügenschuh
    Zhiyi Tan
    Zsolt Tuza
    Krzysztof Węsek
    Central European Journal of Operations Research, 2018, 26 : 161 - 180
  • [22] Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
    Dosa, Gyorgy
    Fuegenschuh, Armin
    Tan, Zhiyi
    Tuza, Zsolt
    Wesek, Krzysztof
    CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 2018, 26 (01) : 161 - 180
  • [23] Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines
    Min, Xiao
    Liu, Jing
    Wang, Yuqing
    INFORMATION PROCESSING LETTERS, 2011, 111 (09) : 423 - 428
  • [24] Online Preemptive Hierarchical Scheduling on Two Uniform Machines with Rejection
    Min, Xiao
    Liu, Jing
    Dong, Yanxia
    Jiang, Ming
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2015, 32 (04)
  • [25] Semi-online scheduling with decreasing job sizes
    Seiden, S
    Sgall, J
    Woeginger, G
    OPERATIONS RESEARCH LETTERS, 2000, 27 (05) : 215 - 221
  • [26] Optimal preemptive online scheduling to minimize lp norm on two processors (vol 1, pg 345, 2005)
    Du, Donglei
    Shuai, Tianping
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2008, 4 (02) : 339 - 341
  • [27] ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES
    Zhang, An
    Jiang, Yiwei
    Tan, Zhiyi
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2011, 28 (02) : 163 - 182
  • [28] Semi-online scheduling with machine cost
    Yong He
    Shengyi Cai
    Journal of Computer Science and Technology, 2002, 17 : 781 - 787
  • [29] Semi-online scheduling with machine cost
    He, Y
    Cai, SY
    JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2002, 17 (06) : 781 - 787
  • [30] Improved semi-online makespan scheduling with a reordering buffer
    Sun, Hongyang
    Fan, Rui
    INFORMATION PROCESSING LETTERS, 2013, 113 (12) : 434 - 439
12345