Online and Semi-online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] pracownik
2024
artykuł naukowy
angielski
- online and semi-online
- early work
- hierarchical scheduling
- competitive ratio
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.
253 - 261
CC BY-NC-ND (uznanie autorstwa - użycie niekomercyjne - bez utworów zależnych)
otwarte czasopismo
ostateczna wersja opublikowana
w momencie opublikowania
100
1,9 [Lista 2022]