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

Man Xiao; Xiaoqiao Liu; Weidong Li; Xin Chen; Małgorzata Sterna; Jacek Błażewicz

Scientific Information System of the Poznań University of Technology

PL EN

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

Submit a comment

Article

Download BibTeX

Title

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

Authors

Man Xiao
Xiaoqiao Liu
Weidong Li
Xin Chen
Małgorzata Sterna (WIiT) ^{[ 1 ][ 2.3 ][ P ]}
Jacek Błażewicz (WIiT) ^{[ 1 ][ 2.3 ][ P ]}

^{[ 1 ]} Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | ^{[ P ]} employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication

2024

Published in

International Journal of Applied Mathematics and Computer Science

Journal year: 2024 | Journal volume: vol. 34 | Journal number: no. 2

Article type

scientific article

Publication language

english

Keywords

EN

online and semi-online
early work
hierarchical scheduling
competitive ratio

Abstract

EN 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 √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 √5 − 1 if the largest job is a higher-hierarchy one.

Pages (from - to)

253 - 261

URL

https://www.amcs.uz.zgora.pl/?action=paper&paper=1750

License type

CC BY-NC-ND (attribution - noncommercial - no derivatives)

Open Access Mode

open journal

Open Access Text Version

final published version

Date of Open Access to the publication

at the time of publication