<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>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 
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amcs-2024-0018_ieq_001.png"></inline-graphic>
. 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 <inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_amcs-2024-0018_ieq_002.png"></inline-graphic> − 1 if the largest job is a higher-hierarchy one.</p>
</abstract>

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 

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

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

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

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...

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

Published Online: Jun 25, 2024

Page range: 253 - 261

Received: Oct 20, 2023

Accepted: Feb 02, 2024

DOI: https://doi.org/10.61822/amcs-2024-0018

Keywords
online and semi-online, early work, hierarchical scheduling, competitive ratio

© 2024 Man Xiao et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

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

Published Online: Jun 25, 2024

Page range: 253 - 261

Received: Oct 20, 2023

Accepted: Feb 02, 2024

DOI: https://doi.org/10.61822/amcs-2024-0018

Keywordsonline and semi-online, early work, hierarchical scheduling, competitive ratio

© 2024 Man Xiao et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
online and semi-online, early work, hierarchical scheduling, competitive ratio