Online and Semi-Online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work

被引：1
作者：
Xiao, Man [1 ]
Liu, Xiaoqiao [1 ]
Li, Weidong [1 ]
Chen, Xin [2 ]
Sterna, Malgorzata [3 ]
Blazewicz, Jacek [3 ,4 ]
机构：
[1] Yunnan Univ, Sch Math & Stat, Kunming 650504, Peoples R China
[2] Liaoning Univ Technol, Sch Elect & Informat Engn, Shiying 169, Jinzhou 121001, Peoples R China
[3] Poznan Univ Tech, Inst Comp Sci, Ul Piotrowo 2, PL-60965 Poznan, Poland
[4] Polish Acad Sci, European Ctr Bioinformat & Genom, Ul Piotrowo 2, PL-60965 Poznan, Poland
来源：
INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE | 2024年 / 34卷 / 02期
基金：
中国国家自然科学基金;
关键词：
online and semi-online; early work; hierarchical scheduling; competitive ratio; IDENTICAL MACHINES; PARALLEL MACHINES;
D O I：
10.61822/amcs-2024-0018
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this study, we investigate several online and semi-online scheduling problems related to two hierarchical machines with a common due date to maximize the total early work. For the pure online case, we design an optimal online algorithm with a competitive ratio of root 2. Additionally, for the cases when the largest processing time is known, we give optimal algorithms with a competitive ratio of 6/5 if the largest job is a lower-hierarchy one, and of root 5 - 1 if the largest job is a higher-hierarchy one.
引用
收藏
页码：253 / 261
页数：9
相关论文
共 24 条
  • [1] Online scheduling with migration on two hierarchical machines
    Akaria, Islam
    Epstein, Leah
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (05) : 3535 - 3548
  • [2] On-line load balancing in a hierarchical server topology
    Bar-Noy, A
    Freund, A
    Naor, JS
    [J]. SIAM JOURNAL ON COMPUTING, 2001, 31 (02) : 527 - 549
  • [3] Alternative algorithms for identical machines scheduling to maximize total early work with a common due date
    Chen, Xin
    Shen, Xuefeng
    Kovalyov, Mikhail Y.
    Sterna, Malgorzata
    Blazewicz, Jacek
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2022, 171
  • [4] Semi-online scheduling on two identical machines with a common due date to maximize total early work
    Chen, Xin
    Kovalev, Sergey
    Liu, Yuqing
    Sterna, Malgorzata
    Chalamon, Isabelle
    Blazewicz, Jacek
    [J]. DISCRETE APPLIED MATHEMATICS, 2021, 290 (290) : 71 - 78
  • [5] Exact and heuristic algorithms for scheduling on two identical machines with early work maximization
    Chen, Xin
    Wang, Wen
    Xie, Pengyu
    Zhang, Xingong
    Sterna, Malgorzata
    Blazewicz, Jacek
    [J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2020, 144
  • [6] Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date
    Chen, Xin
    Liang, Yage
    Sterna, Malgorzata
    Wang, Wen
    Blazewicz, Jacek
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 284 (01) : 67 - 74
  • [7] Scheduling on parallel identical machines with late work criterion: Offline and online cases
    Chen, Xin
    Sterna, Malgorzata
    Han, Xin
    Blazewicz, Jacek
    [J]. JOURNAL OF SCHEDULING, 2016, 19 (06) : 729 - 736
  • [8] A survey of the state-of-the-art of common due date assignment and scheduling research
    Gordon, V
    Proth, JM
    Chu, CB
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 139 (01) : 1 - 25
  • [9] Graham R. L., 1979, Discrete Optimisation, P287
  • [10] A common approximation framework for early work, late work, and resource leveling problems
    Gyorgyi, Peter
    Kis, Tamas
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 286 (01) : 129 - 137
123