1. Semi-online algorithms for hierarchical scheduling on three parallel machines.
- Author
-
XIAO Man, DING Lu, and ZHANG Yi
- Abstract
This paper studies a semi-online hierarchical scheduling problem on three identical machines. In the problem, there is only one machine with hierarchy 1 and two machines with hierarchy 2, and the goal is to minimize the makespan. When the total size of low-hierarchy is known, an online algorithm with the competitive ratio of 5/3 and the lower bound of 3/2 is given. When the total size of high-hierarchy is known, an online algorithm with the competitive ratio of 9/5 and the lower bound of 3/2 is given. When the total size of each hierarchy is known, an online algorithm with the competitive ratio of 3/2 and the lower bound of 4/3 is given. When the total size of jobs is known, a best possible online algorithm with the competitive ratio of 3/2 is given. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF