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 条
  • [31] Semi-online Hierarchical Scheduling for Bag-of-tasks on Two Machines
    Dai, Bingfei
    Li, Jianping
    Li, Weidong
    PROCEEDINGS OF 2018 THE 2ND INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND ARTIFICIAL INTELLIGENCE (CSAI 2018) / 2018 THE 10TH INTERNATIONAL CONFERENCE ON INFORMATION AND MULTIMEDIA TECHNOLOGY (ICIMT 2018), 2018, : 609 - 614
  • [32] Semi-online scheduling with combined information on two identical machines in parallel
    Qian Cao
    Guohua Wan
    Journal of Combinatorial Optimization, 2016, 31 : 686 - 695
  • [33] Semi-online scheduling with combined information on two identical machines in parallel
    Cao, Qian
    Wan, Guohua
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (02) : 686 - 695
  • [34] Optimal semi-online scheduling algorithms on two parallel identical machines under a grade of service provision
    Wu, Yong
    Ji, Min
    Yang, Qifan
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2012, 135 (01) : 367 - 371
  • [35] Optimal Semi-online Scheduling Algorithms on Two Parallel Identical Machines under a Grade of Service Provision
    Wu, Yong
    Yang, Qifan
    ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, 2010, 6124 : 261 - +
  • [36] An optimal semi-online algorithm for 2-machine scheduling with an availability constraint
    Hongying Li
    Chunjie Su
    Journal of Combinatorial Optimization, 2011, 22 : 153 - 165
  • [37] An optimal semi-online algorithm for 2-machine scheduling with an availability constraint
    Li, Hongying
    Su, Chunjie
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 22 (02) : 153 - 165
  • [38] Semi-online scheduling with “end of sequence” information
    Leah Epstein
    Deshi Ye
    Journal of Combinatorial Optimization, 2007, 14 : 45 - 61
  • [39] A Near-Optimal Semi-Online Algorithm for Maximizing Throughput Scheduling Problem
    Tao, Ye
    Chao, Zhijun
    Xi, Yugeng
    IMECS 2009: INTERNATIONAL MULTI-CONFERENCE OF ENGINEERS AND COMPUTER SCIENTISTS, VOLS I AND II, 2009, : 453 - 458
  • [40] Semi-online scheduling with "end of sequence" information
    Epstein, Leah
    Ye, Deshi
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2007, 14 (01) : 45 - 61
12345