Semi-online scheduling with known maximum job size on two uniform machines

被引：4
|
作者：
Cao, Qian [1 ]
Liu, Zhaohui [1 ]
机构：
[1] E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2010年 / 20卷 / 04期
基金：
中国国家自然科学基金;
关键词：
Scheduling; Uniform machines; Semi-online; PROCESSORS; BOUNDS;
D O I：
10.1007/s10878-009-9214-0
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
In this paper, we investigate the semi-online scheduling problem with known maximum job size on two uniform machines with the speed ratio s >= 1. The objective is to minimize the makespan. Two algorithms are presented, where the first is optimal for 1.559 <= s <= 2 and s >= 3+root 17/2 . In addition, the improvement on lower bounds is made for 2 < s < 3+root 17/2.
引用
收藏
页码：369 / 384
页数：16
相关论文
共 50 条
  • [41] 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
  • [42] Online scheduling on two uniform machines to minimize the makespan
    Liu, Ming
    Xu, Yinfeng
    Chu, Chengbin
    Zheng, Feifeng
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2099 - 2109
  • [43] On the optimality of list scheduling for online uniform machines scheduling
    Han, Fangqiu
    Tan, Zhiyi
    Yang, Yang
    OPTIMIZATION LETTERS, 2012, 6 (07) : 1551 - 1571
  • [44] Online Hierarchical Scheduling on Two Uniform Machines with Bounded Job Sizes
    Lu, Xinrong
    Liu, Zhaohui
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2015, 32 (05)
  • [45] Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling
    Dosa, Gyoergy
    Speranza, M. Grazia
    Tuza, Zsolt
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 21 (04) : 458 - 480
  • [46] Semi-online scheduling with machine cost
    Yong He
    Shengyi Cai
    Journal of Computer Science and Technology, 2002, 17 : 781 - 787
  • [47] Scheduling job classes on uniform machines
    Gerstl, Enrique
    Mosheiov, Gur
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (09) : 1927 - 1932
  • [48] Semi-Online Scheduling on Two Identical Parallel Machines with Initial-Lookahead Information
    Zheng, Feifeng
    Chen, Yuhong
    Liu, Ming
    Xu, Yinfeng
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2024, 41 (01)
  • [49] Semi-online scheduling with machine cost
    He, Y
    Cai, SY
    JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2002, 17 (06) : 781 - 787
  • [50] 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
12345