Semi-online scheduling with known maximum job size on two uniform machines

摘要

In this paper, we investigate the semi-online scheduling problem with known maximum job size on two uniform machines with the speed ratio s≥1. The objective is to minimize the makespan. Two algorithms are presented, where the first is optimal for 1≤s≤√2, and the second is optimal for 1.559≤s≤2 and 1.559 ≤ S ≤ √2 and s ≥ 3+√17/2. In addition, the improvement on lower bounds is made for 2< s < 3+√17/2.