Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines

In this paper, we consider semi-online minimum makespan scheduling problem with reassignment on two identical machines. Two versions are discussed. In the first version, one can reassign the last job of one machine that is based on the problem proposed by Tan and Yu (2008) [1], in which case the last job of each machine is allowed to be reassigned. An optimal algorithm which has the same competitive ratio is presented. In the second version we consider the combination of the next two conditions: the total size of all jobs is known in advance and one can reassign the last job of one machine. For this problem an optimal algorithm with competitive ratio is also given.