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

System Informacji Naukowej Politechniki Poznańskiej

PL EN

Strona główna / Publikacje / Online and Semi-online Scheduling on Two Hierarchical Machines with a Common Due Date to Maximize the Total Early Work

Zgłoś uwagę

Artykuł

Pobierz BibTeX

Tytuł

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

Autorzy

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 ]} pracownik

Dyscyplina naukowa (Ustawa 2.0)

[2.3] Informatyka techniczna i telekomunikacja

Rok publikacji

2024

Opublikowano w

International Journal of Applied Mathematics and Computer Science

Rocznik: 2024 | Tom: vol. 34 | Numer: no. 2

Typ artykułu

artykuł naukowy

Język publikacji

angielski

Słowa kluczowe

EN

online and semi-online
early work
hierarchical scheduling
competitive ratio

Streszczenie

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.

Strony (od-do)

253 - 261

URL

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

Typ licencji

CC BY-NC-ND (uznanie autorstwa - użycie niekomercyjne - bez utworów zależnych)

Tryb otwartego dostępu

otwarte czasopismo

Wersja tekstu w otwartym dostępie

ostateczna wersja opublikowana

Czas udostępnienia publikacji w sposób otwarty

w momencie opublikowania