- Tytuł:
- Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work
- Autorzy:
-
Xiao, Man
Liu, Xiaoqiao
Li, Weidong
Chen, Xin
Sterna, Malgorzata
Blazewicz, Jacek - Tematy:
-
online scheduling
semi online scheduling
early work
hierarchical scheduling
competitive ratio - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Oficyna Wydawnicza
- Powiązania:
- https://bibliotekanauki.pl/articles/59123802.pdf  Link otwiera się w nowym oknie
- Opis:
- 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.
- Dostawca treści:
- Biblioteka Nauki
Artykuł