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 条
  • [31] Optimal non-preemptive semi-online scheduling on two related machines
    Epstein, L
    Favrholdt, LM
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2005, 57 (01): : 49 - 73
  • [32] Online and semi-online scheduling of two machines under a grade of service provision
    Park, Jongho
    Chang, Soo Y.
    Lee, Kangbok
    OPERATIONS RESEARCH LETTERS, 2006, 34 (06) : 692 - 696
  • [33] Preemptive semi-online algorithms for parallel machine scheduling with known total size
    He, Y
    Zhou, H
    Jiang, YW
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2006, 22 (02) : 587 - 594
  • [34] Preemptive Semi-online Algorithms for Parallel Machine Scheduling with Known Total Size
    Yong HE
    Hao ZHOU
    Yi Wei JIANG
    Acta Mathematica Sinica(English Series), 2006, 22 (02) : 587 - 594
  • [35] 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
  • [36] Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing
    Qi, Xianglai
    Yuan, Jinjiang
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2019, 36 (01)
  • [37] Semi-online scheduling problems on a small number of machines
    Lee, Kangbok
    Lim, Kyungkuk
    JOURNAL OF SCHEDULING, 2013, 16 (05) : 461 - 477
  • [38] Semi-online scheduling revisited
    Albers, Susanne
    Hellwig, Matthias
    THEORETICAL COMPUTER SCIENCE, 2012, 443 : 1 - 9
  • [39] Optimal Semi-Online Algorithm for Scheduling on Two Parallel Batch Processing Machines
    Liu, Ming
    Zheng, Feifeng
    Zhu, Zhanguo
    Chu, Chengbin
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2014, 31 (05)
  • [40] On-line and semi-online scheduling for flow shop problems on two machines
    Yang, Ming
    Lu, Xiwen
    OPTIMIZATION, 2013, 62 (04) : 499 - 507
12345