online read us now
Paper details
Number 2 - June 2024
Volume 34 - 2024
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, Malgorzata Sterna, Jacek Blazewicz
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 √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.
Keywords
online and semi-online, early work, hierarchical scheduling, competitive ratio